[공부] 인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고 4주차

본 포스팅은 강의를 바탕으로 공부하기 위해 작성되었습니다.

http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2022_T2/course/ 

강좌 | SKKU_46 | K-MOOC

 

그래프 순회(graph traversal)

• 그래프에 있는 노드들을 방문하는 과정 
• 순회(traversal)이라는 말 대신 검색(serach)라고 표현하기도 한다.
• 그래프 순회는 크게 너비우선탐색(breadth-first search), 깊이우선탐색(depth-first search)로 두 가지 예로 들 수 있다.

 

Breadth-First Search(BFS)

• 임의의 vertex를 하나 선택한다. 
• 임의의 vertex를 visit했음을 알기 위하여 queue에 push한다. 
• queue가 채워져 있는 동안 지속적으로 아래의 과정을 반복한다.
• 1. queue의 vertex v를 pop한다. 
• 2. v에 인접한 각각의 vertex들 중 visit하지 않은 vertex들을 visit했음을 알리기 위하여 큐에 push한다.
• 이 과정을 반복적으로 큐가 빌 때까지 수행한다면, 그래프에 있는 모든 vertex들을 방문할 수 있게 된다.
• 그러나, 큐가 비었는데도 그래프상에서 visit 되지 않은, push되지 않은 vertex가 존재한다면 그 그래프는 connect 되어있지 않다고 말한다.

 

Depth-First Search(DFS)

• DFS의 알고리즘은 BFS와 같으나, 자료구조는 스택을 사용하게 된다.
• 스택이 비지 않을 때까지, vertedx 하나를 꺼내서 인접한 vertex들 중 visit하지 않은 vertex들을 stack에 push한다.

 

중요한 점

• DFS 및 BFS 알고리즘이 항상 유니크한 순회순서를 만들어 주지 않는다. 
• 그 이유는 우리가 어떤 vertex에 방문하였을 때, neighbor(adjacent vertex)를 자료구조에 추가하는 순서가 항상 같지 않을 수 있기 때문이다.

 

Connected components

component들이 connected 되어있는지 DFS 혹은 BFS를 이용하여 확인할 수 있다. 

 

코드로 구현

//Edge 정보
// 총 13개의  vertex, 그러면 edge는 12개 
// AB AH BC BE HI HM CD EF EG IJ IK IL

#include <cstdio>
#include <vector>
#include <queue>
using namespace std; 


class Graph
{
public:
    int nV, nE; //number of vertex, number of edge 
    vector<int> *edges;
    
    void Init(const char *_filename)
    {
        FILE *input = fopen(_filename, "r");
        fscanf(input, "%d", &nV);
        fscanf(input, "%d", &nE);
        edges = new vector<int> [nV];
        
        for(int i = 0; i< nE; i++)
        {
            char a, b;
            fscanf(input, "%c %c", &a, &b);
            int x, y;
            x = a - 'A';
            y = b - 'A';
            edges[x].push_back(y); 
        }
        fclose(input);
    }
}

void BFS(Graph &_g, int _stIdx = 0)
{
   queue<int> q;
   bool *visit = new bool[_g.nV];
   for(int i = 0; i<_g.nV; i++)
   {
       visit[i] = false;
   }
   
   q.push( _stIdx );
   visit[_stIdx] = true;
   
   while (!q.empty())
   {
       int x = q.front();
       q.pop();
       printf("visited %c", x + 'A');
       
       for(int i = 0; i< _g.edges[x].size(); i++)
       {
           if(!visit[_g.edges[x][i]])
           {
               q.push(_g.edges[x][i]);
               visit[_g.edges[x][i]] true;
           }
       }
   }
   
   delete [] visit;
}

int main(int argc, char **argv)
{
    Graph g;
    g.Init(argv[1]);
    
    BFS( g );
    return1;
}