algorithm
폭 넓은 우선 검색
수색…
소스에서 다른 노드로의 최단 경로 찾기
폭스 우선 검색 ( Breadth-First-Search , BFS)은 트리 또는 그래프 데이터 구조를 탐색하거나 검색하기위한 알고리즘입니다. 트리 루트 (또는 그래프의 임의 노드, 때로는 '검색 키'라고 함)에서 시작하여 다음 레벨의 이웃으로 이동하기 전에 먼저 이웃 노드를 탐색합니다. BFS는 1950 년대 후반 Edward Forrest Moore 가 발명했다. Edward Forrest Moore 는 미로에서 최단 경로를 찾는데 사용했으며 1961 년 CY Lee가 와이어 라우팅 알고리즘으로 독자적으로 발견했다.
BFS 알고리즘의 프로세스는 다음과 같은 가정하에 작동합니다.
- 노드를 두 번 이상 통과하지 않습니다.
- 소스 노드 또는 시작하려는 노드는 레벨 0에 있습니다.
- 소스 노드에서 직접 도달 할 수있는 노드는 레벨 1 노드이고 레벨 1 노드에서 직접 도달 할 수있는 노드는 레벨 2 노드입니다.
- 레벨은 소스에서 최단 경로까지의 거리를 나타냅니다.
예를 보자. 
이 그래프가 여러 도시 간의 연결을 나타내는 것으로 가정 해 봅시다. 각 노드는 도시를 나타내고 두 노드 사이의 모서리는 노드를 연결하는 도로가 있음을 나타냅니다. 노드 1 에서 노드 10 으로 이동하려고합니다. 따라서 노드 1 은 레벨 0 인 소스 입니다. 방문한 노드 1 을 표시 합니다 . 여기에서 노드 2 , 노드 3 및 노드 4 로 이동할 수 있습니다. 그래서 그들은 레벨 (0 + 1) = 레벨 1 노드가 될 것입니다. 이제 우리는 그들을 방문한 것으로 표시하고 그들과 함께 작업 할 것입니다.
색깔의 노드가 방문됩니다. 현재 작업중인 노드는 분홍색으로 표시됩니다. 우리는 동일한 노드를 두 번 방문하지 않을 것입니다. 노드 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 에서이 노드에 도달했습니다. 그래서 level [4] = level [3] = level [2] = level [1] + 1 = 1 . 이제 우리는 그들을 방문한 것으로 표시하고 대기열에 밀어 넣습니다.
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
이제 우리는 node 4를 pop하고 그것을 사용합니다. 노드 4 에서 노드 7 로 갈 수 있습니다. 레벨 [7] = 레벨 [4] + 1 = 2 . 노드 7 을 방문한 것으로 표시하고 대기열에 밀어 넣습니다.
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
노드 3 에서 노드 7 과 노드 8 로 이동할 수 있습니다. 이미 노드 7 을 방문한 것으로 표시했기 때문에 노드 8 을 방문한 것으로 표시하고 level [8] = level [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 배열이됩니다. 각 노드에 대해 가능한 모든 동작을 고려합니다. 특정 노드와의 거리를 찾기 위해 목적지까지 도달했는지 여부도 확인합니다.
direction array라는 또 하나의 것이있을 것입니다. 이것은 우리가 갈 수있는 방향의 모든 가능한 조합을 저장합니다. 예를 들어 수평 및 수직 이동의 경우 방향 배열은 다음과 같습니다.
+----+-----+-----+-----+-----+
| 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는 그래프 트래버 설 알고리즘입니다. 임의의 소스 노드에서 시작하여 알고리즘 종료시 모든 노드를 방문하면 그래프가 연결되고 그렇지 않으면 연결되지 않습니다.
알고리즘의 PseudoCode.
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);
}
}