Breadth First Search for a Graph - 그래프 넓이-우선탐색

안녕하세요 besforyou 입니다

 

이번 글에서는 그래프에서의 BFS에 대해 설명(번역)해보겠습니다

 

 

출처 : https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

Breadth First Search or BFS for a Graph - GeeksforGeeks

 

---

그래프의 BFS는 트리의 BFS와 매우 비슷합니다.

다른 점은 그래프는 cycle이 존재해 같은 노드에 다시 되돌아 올 수 있다는 점입니다.

이 때문에 한 노드를 한 번 이상 접근하는것을 피하기 위해 boolean visited array를 사용합니다.

편의를 위해 모든 정점이 탐색 시작 정점에서 방문 가능한걸로 가정하겠습니다.

 

예로 아래의 그래프에서 우리는 정점 2에서 탐색을 시작합니다. 정점 0으로 오면 주변 정점들을 확인합니다. 만약 이미 방문한 정점인것을 표시하지 않았다면 정점 2를 다시 탐색할것이고 무한반복 프로세스가 될것입니다. 

아래 그래프의 BFS는 2,0,3,1 입니다.

 

 

---

인접 리스트 구현 방법으로 구현한 그래프의 BFS 예시 코드

 

#include <iostream>
#include <list>
 
using namespace std;
 
class Graph
{
    int V; // vertex count
 
    list<int> *adj; // pointer to an array containing adjacency lists
 
    public:
        Graph(int V);   // constructor
 
        void addEdge(int v, int w);
        void BFS(int s);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
}
 
void Graph::BFS(int s)
{
    bool * visited = new bool[V];
 
    for ( int i = 0; i < V ; i++ )
        visited[i] = false;
 
    // Create a queue for BFS
    list<int> queue;
 
    visited[s] = true;
    queue.push_back(s);
 
    // 'i' will be used to get all adjacent vertices of a vertex
    list<int>::iterator i;
 
    while (!queue.empty())
    {
        s = queue.front();
        cout << s << " ";
        queue.pop_front();
 
 
        for ( i = adj[s].begin() ; i != adj[s].end(); ++i)
        {
            if (!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
}
 
// Driver program
int main()
{
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
 
    g.BFS(2);
 
    return 0;
}
 

중요하게 볼 부분은 당연하게도 BFS 멤버 함수 부분이죠

 

void Graph::BFS(int s)
{
    bool * visited = new bool[V];
 
    for ( int i = 0; i < V ; i++ )
        visited[i] = false;
 
    // Create a queue for BFS
    list<int> queue;
 
    visited[s] = true;
    queue.push_back(s);
 
    // 'i' will be used to get all adjacent vertices of a vertex
    list<int>::iterator i;
 
    while (!queue.empty())
    {
        s = queue.front();
        cout << s << " ";
        queue.pop_front();
 
 
        for ( i = adj[s].begin() ; i != adj[s].end(); ++i)
        {
            if (!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
}

 

정점에 접근한적이 있는지 없는지 기록할 배열 visited를 생성하고 모두 false로 초기화합니다.

 

큐를 생성하고 정점 s를 접근했다고 기록하고 큐에 push_back합니다.

 

iterator를 생성하고

 

정점 s와 연결된 정점들 중 아직 방문되지 않은 정점을 모두 큐에 push_back하고 큐의 front값을 s에 다시 할당하는 작업을

 

큐가 빌때까지 반복합니다.