[C] Search in Graph

* 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다.

우리는 이전 graph에서 path를 살펴보았다.

Path: edge로 연결된 vertices의 sequence를 의미한다.

 

두개의 vertices는 path가 있다면 connected 되었다고 말할 수 있다. 

V1과 V2가 connected되었다면 V2는 V1으로부터 reachable하다고 말할 수 있다.

 

이때 이렇게 connected 된 vertices의 maximal set을 connected component라고 부른다. 

 

두개의 vertices가 reachable한지 알기 위해서 우리는 path를 찾아야 한다.

우선 reachability를 수학적으로 정의해보자

만약 start == target 혹은 start와 vertex v사이에 edge가 있고 v 에서 target으로 path가 있다면 start과 target 사이에 path가 존재한다.

이를 우리는 induction을 활용해 recursive한 client-side함수로 만들 수 있다.

(이는 graph_print와 똑같은 structure를 가진다)

bool naive_dfs(graph_t G, vertex start, vertex target){
  REQUIRES(G!=NULL);
  REQUIRES(start<graph_size(G) && target<graph_size(G));
  
  //there is a path from start to target if
  //target== start
  if (target==start) return true;
  //or there is an edge from start to some vertex v
  neighbors_t nbors = graph_get_neighbors(G, start);
  while(graph_hasmore_neighbors(nbors)){
    vertex v = graph_next_neighbor(nbors);
    //and there is a path from v to target
    if (naive_dfs(G, v, target)){
      graph_free_neighbors(nbors);
      return true;
    }
  }
  graph_free_neighbors(nbors);
  return false;
 }

이게 실제로 작용하는가?  아래의 그래프를 통해 테스트해보자

start	target	nbors
3	0	2
2	0	1,3,4
1	0	0,2
0	0	ok!

start	target	nbors
0	3	1,4
1	3	0,2
0	3	1,4
1	3	0,2
...	...	...

항상 맞지 않다는 걸 알수 있다. 

이코드가 작동하지 않는 가장 큰 이유로는 이것이 이미 확인되었음에도 불구하고 항상 똑같은 첫 v로 시작한다는 점이다.

따라서 이는 2번째 neighbor를 절대 확인하지 않을 것이다. 

이를 해결하기 위해서는 한번이라도 방문한 vertices는 마크하는 것이다. 

이후 마크되지 않은 vertex만 확인하는 것이다. 

이는 boolean을 담은 array를 통해 각 vertices에 대한 mark를 저장할 수 있다. 

 

bool dfs_helper(graph_t G,bool* mark, vertex start, vertex target){
  REQUIRES(G!=NULL);
  REQUIRES(start<graph_size(G) && target<graph_size(G));
  REQUIRES(!mark[start]);  //오직 시작하는 vertex가 unmarked되어있을때만 시작한다. 
  
  mark[start] = true; //시작과 동시에 방문했으므로 mark한다. 
  //there is a path from start to target if
  //target== start
  if (target==start) return true;
  //or there is an edge from start to some vertex v
  neighbors_t nbors = graph_get_neighbors(G, start);
  while(graph_hasmore_neighbors(nbors)){
    vertex v = graph_next_neighbor(nbors);
    //and there is a path from v to target
    if (!mark[v] && dfs_helper(G, mark, v, target)){ //mark되지 않은 vertex만 확인한다.
      graph_free_neighbors(nbors);
      return true;
    }
  }
  graph_free_neighbors(nbors);
  return false;
 }

이후 wrapper를 통해 dfs_helper의 return을 해결한다.

 

bool dfs(graph_t G, vertex start, vertex target){
  REQUIRES(G!=NULL);
  REQUIRES(start <graph_size(G) && target<graph_size(G));
  
  bool* mark = xcalloc(graph_size(G), sizeof(bool));
  bool connected = dfs_helper(G, mark, start, target);
  free(mark);
  return connected;
}

이것역시 항상 작동하는지 확인해보자

start	target	nbors	marked
0	3	1,4	0
1	3	2,4	0,1
2	3	3	0,1,2
3	3	ok!

start	target	nbors	marked
2	3	1,3,4	2
1	3	0,2,4	1,2
0	3	1,4	0,1,2
4	3	0,1,2	0,1,2,4
3	3	ok!

4에 도달했을때 모든 neighbors가 marked되었기 때문에 다시 unmarked neighbor가 있는 vertex로 backtrack한다. 

 

위 dfs의 cost를 생각해보자면 mark array를 만드는 것이 O(v) cost가 필요하기 때문에

총 cost는 O(v) + cost of dfs_helper가 된다. 

bool dfs_helper(graph_t G,bool* mark, vertex start, vertex target){
  REQUIRES(G!=NULL);
  REQUIRES(start<graph_size(G) && target<graph_size(G));
  REQUIRES(!mark[start]);  //오직 시작하는 vertex가 unmarked되어있을때만 시작한다. 
  
  mark[start] = true; //시작과 동시에 방문했으므로 mark한다.   //O(1)       O(v)
  if (target==start) return true;                      //O(1)       O(v)
  //or there is an edge from start to some vertex v
  neighbors_t nbors = graph_get_neighbors(G, start);   //O(1)       O(v)
  while(graph_hasmore_neighbors(nbors)){               //O(e)       O(v+e)
    vertex v = graph_next_neighbor(nbors);
    //and there is a path from v to target
    if (!mark[v] && dfs_helper(G, mark, v, target)){ //mark되지 않은 vertex만 확인한다.
      graph_free_neighbors(nbors);
      return true;
    }
  }
  graph_free_neighbors(nbors);                         //O(1)       O(v+e)
  return false;
 }

따라서 dfs_helper의 최종 cost는 O(e+v)가 된다. 

따라서 dfs의 최종 cost는 O(v+e)가 된다.

 

V개의 vertices와 e개의 edges를 가진 graph에서 

-adjacency list는 O(v+e)

-adjacency matrix는 O(v^2)의 cost를 가진다. 

list가 sparse graph에서 더 유용하다

 

 

위의 dfs의 경우 target vertex를 찾거나 혹은 더이상 unmarked neighbors가 없을때까지 돌아가는데 

이를 우리는 depth-first search라고 부른다. 

 

더 짧은 path를 찾기 위해서 우리는 start vertex에서 level별로 graph을 확인해야 한다.

이를 breadth-first search라고 부른다. 

 

우리는 level별로 가면서 다음에 확인할 vertex를 보아야 하는데 이를 우리는 queue형태의 work list에 저장해야한다. 

next	target	queue	marked
	4	0	0
0	4	1,4	0,1,4
1	4	4,2	0,1,4,2
4	4	ok!

이러한 bfs의 과정으로는 

-queue에 가장 오래있었던 vertex를 retrieve한다. 

-그 해당 vertex의 각 neighbor를 확인한다. 

--만약 neighbor가 unmarked라면 queue에 새로 추가하고 mark한다.

--그렇지 않으면 무시하고 넘어간다. 

 

만약 queue가 empty라면 path가 없다고 본다

 

bool bfs(graph_t G, vertex start, vertex target){
  REQUIRES(G!=NULL);
  REQUIRES(start<graph_size(G) && target <graph_size(G));
  
  if (start==target) return true;
  
  bool* mark = xcalloc(graph_size(G), sizeof(bool));
  mark[start] = true;
  
  queue_t Q = queue_new();
  enq(Q, start);
  
  while(!queue_empty(Q)){
     vertex v = deq(Q);
     if (v==target){
        queue_free(Q);
        free(mark);
        return true;
    }
    
    neighbors_t nbors = graph_get_neighbors(G,v);
    while(graph_hasmore_neighbors(nbors)){
       vertex w = graph_next_neighbor(nbors);
       if (!mark[w]){ //if w is not already marked
          mark[w] = true;
          enq(Q,w);
        }
      }
      graph_free_neighbors(nbors);
     }
     ASSERT(queue_empty(Q));
     queue_free(Q);
     free(mark);
     return false;
   }

이 역시 graph_print와 같은 structure를 가지고 있음을 알수있다. 

시간복잡도로는 

adjacency list: O(v+e)

adjacency matrix: O(v^2)

(dfs와 동일하다)

 

BFS의 정확도를 확인하기 위해서는

-start -> target에 path가 있을때 true 없으면 false가 된다. 

 

base case의 경우 true를 확인할 수 있다.

하지만 v가 target일때 true를 return 할 수 있는지 point할 수 없다. 

 

이에 따라 loop invariant가 필요하다

1) start로부터 모든 marked된 vertex까지 path가 있다.

2) queue에 있는 모든 vertex는 marked된다.

 

반대로 path가 없을때 false를 return하는 것이 맞는지 확인하기 위해서 추가적 loop invariant가 필요하다

 

queue에 있는 vertices는 frontier로 frontier이전 vertices는 marked되고 그렇지 않은 경우 marked되진 않을 것이다. 

 

Loop invariant -> start에서 target으로 가는 모든 path는 frontier를 지나친다.