C ++でBFSを使用して、特定のソースから宛先までのすべてのパスを出力します
この問題では、有向グラフが表示され、幅優先探索（BFS）を使用してグラフのソースから宛先までのすべてのパスを印刷する必要があります。
有向グラフ は、頂点aからbに向けられたエッジを持つグラフです。
問題を理解するために例を見てみましょう-
ソース=K宛先=P
出力
K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P
ここで、KからPへのパスを見つけました。パスをトラバースし、KからPに向かうすべてのパスを出力しました。
ソースから宛先までのすべてのパスを印刷するには、グラフをトラバースしてパスを保存してから、有効なパスを印刷する必要があります。
DFSを使用する場合、プロセスは簡単ですが、この場合、実装には少し注意が必要です。
この問題を解決するには、パスを格納するキューが必要になります。ソースノードから開始して、BFSを使用してアレイのトラバースを開始します。トラバース
ツリーを作成し、キューにチェックインします。宛先の頂点に到達した場合は、キュー要素を出力します。それ以外の場合は無視します。
#include <bits/stdc++.h>
using namespace std;
void printPath(vector<char>& path) {
int size = path.size();
for (int i = 0; i < size; i++)
cout<<path[i]<<" ";
cout<<endl;
}
int isVertexVisited(char x, vector<char>& path) {
int size = path.size();
for (int i = 0; i< size; i++)
if (path[i] == x)
return 1;
return 0;
}
void pathSourceToDestination(vector<vector<char> >&g, char src, char dst, int v) {
queue<vector<char> > q;
vector<char> path;
path.push_back(src);
q.push(path);
while (!q.empty()) {
path = q.front();
q.pop();
char last = path[path.size() - 1];
if (last == dst)
printPath(path);
for (int i = 0; i < g[last].size(); i++) {
if (!isVertexVisited(g[last][i], path)) {
vector<char> newpath(path);
newpath.push_back(g[last][i]);
q.push(newpath);
}
}
}
}
int main() {
vector<vector<char> > g;
int v = 4;
g.resize(4);
g['X'].push_back('S');
g['X'].push_back('A');
g['X'].push_back('N');
g['A'].push_back('S');
g['N'].push_back('X');
g['N'].push_back('A');
char src = 'N', dst = 'S';
cout<<"path from src "<<src<<" to dst "<<dst<<" are \n";
pathSourceToDestination(g, src, dst, v);
return 0;
} 出力
path from src N to dst S are N X S N A S N X A S
-
C++で特定のノードから距離kにあるすべてのノードを出力します
この問題では、二分木、ターゲットノード、整数Kが与えられます。ターゲットノードから距離Kにあるツリーのすべてのノードを印刷する必要があります。 。 二分木 は、各ノードに最大2つのノード（1つまたは2つ/なし）を持つ特別なツリーです。 問題を理解するために例を見てみましょう K =2 ターゲットノード：9 出力 − 5 1 3. 説明 − 距離は、ノードの上位、下位、または同じレベルで取得できます。したがって、それに応じてノードを返します。 この問題を解決するには、ターゲットノードからK距離離れたノードのタイプを理解する必要があります。 上記の試験から、k個の離
-
特定のソースから宛先までのすべてのパスをC++で出力します
この問題では、有向グラフが与えられ、グラフのソースから宛先までのすべてのパスを印刷する必要があります。 有向グラフ は、頂点aからbに向けられたエッジを持つグラフです。 問題を理解するために例を見てみましょう ソース=K宛先=P 出力： K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P ここで、KからPへのパスを見つけました。パスをトラバースし、KからPに向かうすべてのパスを出力しました。 この問題を解決するために、深さ優先探索を使用してグラフをトラバースします。