サーチ…
ソースから他のノードへの最短経路の発見
幅優先検索 （BFS）は、ツリーまたはグラフのデータ構造を走査または検索するためのアルゴリズムです。それはツリールート（またはグラフの任意のノード、時には「検索キー」と呼ばれる）から始まり、隣のノードを最初に探索してから次のレベルの隣人に移動します。 BFSは1950年代後半にEdward Forrest Mooreによって発明されました。彼は迷路から最短経路を発見するためにそれを使用し、1961年にCY Leeがワイヤリングアルゴリズムとして独自に発見しました。
BFSアルゴリズムのプロセスは、次の前提の下で機能します。
- ノードを何度も通過することはありません。
- ソースノードまたは開始するノードはレベル0にあります。
- ソースノードから直接到達できるノードはレベル1のノードであり、レベル1のノードから直接到達できるノードはレベル2のノードであり、以下同様である。
- レベルは、ソースからの最短パスの距離を示します。
例を見てみましょう： 
このグラフが複数の都市間の接続を表しているとしましょう。各ノードは都市を表し、2つのノード間のエッジはそれらをリンクする道路を表します。我々は、 ノード1からノード10に行きたい。したがって、 ノード1はレベル0の ソースです。訪問されたノード1に印を付ける。ここからノード2 、 ノード3 、 ノード4に行くことができます。したがって、それらはレベル（0 + 1） = レベル1のノードになります。ここでは訪問したものとしてマークし、それらと一緒に作業します。
色付けされたノードが訪問されます。現在作業しているノードにはピンク色のマークが付けられます。同じノードを2度訪れることはありません。 ノード2 、 ノード3 、 ノード4から、 ノード6、 ノード7 、 ノード8に行くことができます 。それらを訪問したものとしてマークしましょう。これらのノードのレベルはレベル（1 + 1） = レベル2になります。 
気づいていない場合、ノードのレベルはソースからの最短パス距離を単に表します 。たとえば、 レベル2の ノード8が見つかりました。 ソースからノード8までの距離は2です。
まだノード10に到達していません。それでは、次のノードを見てみましょう。我々はノード6 、 ノード7およびノード8から直接行くことができる。 
これを見ると、 レベル3の ノード10が見つかりました。 ソースからノード10までの最短経路は3です。グラフのレベルをレベルごとに検索し、最短経路を見つけました。次に、使用しなかったエッジを消去しましょう。 
使用しなかったエッジを削除した後、BFSツリーと呼ばれるツリーが取得されます。このツリーには、 ソースから他のすべてのノードまでの最短パスが表示されます。
だから私たちの仕事は、 ソースからレベル1のノードに行くことです。次に、 レベル1からレベル2のノードまで、それ以降は目的地まで到達します。 キューを使用して、処理しようとしているノードを格納することができます。つまり、作業する各ノードについて、直接トラバースでき、まだトラバースされていない他のすべてのノードをキューにプッシュします。
この例のシミュレーション：
まず、ソースをキューにプッシュします。私たちの待ち行列は次のようになります：
front
+-----+
| 1 |
+-----+
ノード1のレベルは0になります。level [1] = 0 。今度はBFSを開始します。まず、キューからノードをポップします。 ノード1を取得します 。このノードからノード4 、 ノード3 、 ノード2に行くことができます 。 ノード1からこれらのノードに到達しました。したがって、 レベル[4] = レベル[3] = レベル[2] = レベル[1] + 1 = 1 。ここでは、それらを訪問済みとしてマークし、キューにプッシュします。
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
今度はノード4をポップし、それを使って作業します。 ノード4からノード 7に行くことができます 。 レベル[7] = レベル[4] + 1 = 2 。 ノード7を訪問したものとしてマークし、それをキューにプッシュします。
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
ノード3から、 ノード7とノード8に行くことができます 。すでにノード7を訪問したとマークしているので、 ノード8を訪問したとマークし、 レベル[8] = レベル[3] + 1 = 2を変更します 。 ノード8をキューにプッシュします。
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
このプロセスは、宛先に達するかキューが空になるまで続きます。 レベル配列は、 ソースからの最短経路の距離を私たちに提供します 。 無限大の値を持つレベル配列を初期化することができます。これはノードがまだ訪問されていないことを示します。私たちの疑似コードは次のようになります：
Procedure BFS(Graph, source):
Q = queue();
level[] = infinity
level[source] := 0
Q.push(source)
while Q is not empty
u -> Q.pop()
for all edges from u to v in Adjacency list
if level[v] == infinity
level[v] := level[u] + 1
Q.push(v)
end if
end for
end while
Return level
レベル配列を反復することによって、各ノードのソースからの距離を知ることができます。たとえば、 ノード10とソースとの距離はレベル[10]に格納されます 。
最短距離だけでなく、 ソースから目的ノードに移動するためのパスも印刷する必要がある場合があります。このためには、 親配列を保持する必要があります。 parent [source]はNULLになります。 レベル配列の各更新については、forループ内の疑似コードにparent[v] := uを単に追加します。 BFSを終えた後、パスを見つけるために、NULL値で示されるソースに達するまで親配列をたどります。疑似コードは次のようになります。
Procedure PrintPath(u): //recursive | Procedure PrintPath(u): //iterative
if parent[u] is not equal to null | S = Stack()
PrintPath(parent[u]) | while parent[u] is not equal to null
end if | S.push(u)
print -> u | u := parent[u]
| end while
| while S is not empty
| print -> S.pop
| end while
複雑：
私たちはすべてのノードを一度、すべてのエッジに一度訪問しました。したがって、複雑さはO（V + E）であり、 Vはノードの数であり、 Eはエッジの数である。
2Dグラフのソースからの最短経路の探索
ほとんどの場合、単一のソースから他のすべてのノードまたは2Dグラフの特定のノードまでの最短経路を見つける必要があります。たとえば、チェス盤のある広場に騎士が到達するために必要な移動数や、いくつかのセルがブロックされている配列がある場合、あるセルから別のセルへの最短経路を見つけなければなりません。私たちは水平方向と垂直方向にのみ移動できます。斜めの動きも可能です。これらの場合、ノード内の四角形またはセルを変換し、BFSを使用して簡単にこれらの問題を解決できます。今私たちの訪問先 、 親とレベルは2D配列になります。各ノードについて、可能なすべての動きを考慮します。特定のノードまでの距離を見つけるには、目的地に到達したかどうかもチェックします。
方向配列と呼ばれる追加のものが1つあります。これは、私たちが行くことのできるすべての可能な組み合わせを単に保存するだけです。たとえば、水平方向と垂直方向の移動の場合、方向配列は次のようになります。
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
ここで、 dxはx軸の移動を表し、 dyはy軸の移動を表します。この部分もまたオプションです。また、すべての組み合わせを個別に書き込むこともできます。しかし、方向配列を使って扱う方が簡単です。斜めの動きや騎士の動きには、さらに多くの組み合わせがあります。
私たちが念頭に置く必要がある追加の部分は次のとおりです。
- いずれかのセルがブロックされている場合、可能なすべての移動について、セルがブロックされているかどうかを確認します。
- 境界から外れているかどうかを確認します。つまり、配列の境界を超えています。
- 行と列の数が与えられます。
私たちの疑似コードは次のようになります：
Procedure BFS2D(Graph, blocksign, row, column):
for i from 1 to row
for j from 1 to column
visited[i][j] := false
end for
end for
visited[source.x][source.y] := true
level[source.x][source.y] := 0
Q = queue()
Q.push(source)
m := dx.size
while Q is not empty
top := Q.pop
for i from 1 to m
temp.x := top.x + dx[i]
temp.y := top.y + dy[i]
if temp is inside the row and column and top doesn't equal to blocksign
visited[temp.x][temp.y] := true
level[temp.x][temp.y] := level[top.x][top.y] + 1
Q.push(temp)
end if
end for
end while
Return level
前に説明したように、BFSは重み付けされていないグラフに対してのみ機能します。加重グラフの場合、 Dijkstraのアルゴリズムが必要です。負のエッジサイクルでは、 Bellman-Fordのアルゴリズムが必要です。ここでも、このアルゴリズムは単一ソース最短経路アルゴリズムである。各ノードから他のすべてのノードまでの距離を調べる必要がある場合は、 Floyd-Warshallのアルゴリズムが必要です。
BFSを使用した無向グラフの接続コンポーネント。
BFSを使用すると、 無向グラフの接続コンポーネントを見つけることができます。与えられたグラフが接続されているかどうかを調べることもできます。以降の議論では、無向グラフを扱っていると仮定しています。接続グラフの定義は次のとおりです。
すべての頂点のペアの間にパスがある場合、グラフが接続されます。
以下は接続されたグラフです。
次のグラフは接続されておらず 、2つの接続コンポーネントがあります。
- 接続されたコンポーネント1：{a、b、c、d、e}
- 接続されたコンポーネント2：{f}
BFSはグラフトラバーサルアルゴリズムです。ランダムソースノードから開始し、アルゴリズムの終了時にすべてのノードが訪問された場合、グラフは接続され、そうでない場合は接続されません。
アルゴリズムの疑似コード。
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
無向グラフが接続されているかどうかを調べるためのC実装：
#include<stdio.h>
#include<stdlib.h>
#define MAXVERTICES 100
void enqueue(int);
int deque();
int isConnected(char **graph,int noOfVertices);
void BFS(char **graph,int vertex,int noOfVertices);
int count = 0;
//Queue node depicts a single Queue element
//It is NOT a graph node.
struct node
{
int v;
struct node *next;
};
typedef struct node Node;
typedef struct node *Nodeptr;
Nodeptr Qfront = NULL;
Nodeptr Qrear = NULL;
char *visited;//array that keeps track of visited vertices.
int main()
{
int n,e;//n is number of vertices, e is number of edges.
int i,j;
char **graph;//adjacency matrix
printf("Enter number of vertices:");
scanf("%d",&n);
if(n < 0 || n > MAXVERTICES)
{
fprintf(stderr, "Please enter a valid positive integer from 1 to %d",MAXVERTICES);
return -1;
}
graph = malloc(n * sizeof(char *));
visited = malloc(n*sizeof(char));
for(i = 0;i < n;++i)
{
graph[i] = malloc(n*sizeof(int));
visited[i] = 'N';//initially all vertices are not visited.
for(j = 0;j < n;++j)
graph[i][j] = 0;
}
printf("enter number of edges and then enter them in pairs:");
scanf("%d",&e);
for(i = 0;i < e;++i)
{
int u,v;
scanf("%d%d",&u,&v);
graph[u-1][v-1] = 1;
graph[v-1][u-1] = 1;
}
if(isConnected(graph,n))
printf("The graph is connected");
else printf("The graph is NOT connected\n");
}
void enqueue(int vertex)
{
if(Qfront == NULL)
{
Qfront = malloc(sizeof(Node));
Qfront->v = vertex;
Qfront->next = NULL;
Qrear = Qfront;
}
else
{
Nodeptr newNode = malloc(sizeof(Node));
newNode->v = vertex;
newNode->next = NULL;
Qrear->next = newNode;
Qrear = newNode;
}
}
int deque()
{
if(Qfront == NULL)
{
printf("Q is empty , returning -1\n");
return -1;
}
else
{
int v = Qfront->v;
Nodeptr temp= Qfront;
if(Qfront == Qrear)
{
Qfront = Qfront->next;
Qrear = NULL;
}
else
Qfront = Qfront->next;
free(temp);
return v;
}
}
int isConnected(char **graph,int noOfVertices)
{
int i;
//let random source vertex be vertex 0;
BFS(graph,0,noOfVertices);
for(i = 0;i < noOfVertices;++i)
if(visited[i] == 'N')
return 0;//0 implies false;
return 1;//1 implies true;
}
void BFS(char **graph,int v,int noOfVertices)
{
int i,vertex;
visited[v] = 'Y';
enqueue(v);
while((vertex = deque()) != -1)
{
for(i = 0;i < noOfVertices;++i)
if(graph[vertex][i] == 1 && visited[i] == 'N')
{
enqueue(i);
visited[i] = 'Y';
}
}
}
無向グラフのすべての接続されたコンポーネントを見つけるために、BFS関数に2行のコードを追加するだけです。この考え方は、すべての頂点が訪れるまでBFS関数を呼び出すことです。
追加する行は次のとおりです。
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
そして
printf("%d ",vertex+1);
add this as first line of while loop in BFS
次の関数を定義します。
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}
