[자료구조] 9주차 - 그래프 탐색 (Graph search)

Graph Search - DFS, BFS

그래프의 탐색 문제 : 그래프의 모든 vertex를 방문하는 문제

탐색하는 과정에서 중요한 요소

• 탐색 과정에서 이미 방문한 노드를 기록
  • visit을 저장하는 배열
• 탐색 과정에서 노드를 방문하는 순서를 기억
  • stack or queue

깊이 우선 탐색(DFS)

• 각 vertex V에서
  • V를 방문한 것으로 표시 (visit[V] = 1)
  • v에 연결된 vertex w 중에서 아직 방문하지 않은 w를 방문
  • 더 이상 방문할 vertex가 없으면 return
• 방문 순서를 stack을 이용해서 저장

void dfs(vertex u){
    visit[u] = TRUE;

    for(w = graph[u]; w != NULL; w = w->link){
        if(!visit[w])
            dfs(w);
    }
}
void dfs(graph G){
    for all v in G
        visit[v] = FALSE;

    for all v in G
        if(visit[v] == FALSE)
            dfs(v);
}

• 인접 행렬 : O(n), 인접 리스트 : O(1) ~ O(n)
• 성능 분석
  • 시간 복잡도 : O(m + n)
  • m : edge의 수, n : vertex의 수
    • Edge가 없는 그래프 : O(n)
    • 희소 그래프 : O(n)
    • 밀집/완전 그래프 : O(n^2)

넓이 우선 탐색 BFS

• 방문할 v의 리스트를 queue를 이용해서 관리
• queue로부터 pop해서 방문할 vertex V를 선택
• V에 이웃한 아직 방문하지 않은 vertex W에서
  • W 방문한 것으로 표시(visit[w] = 1)
  • queue에 추가
• queue가 empty가 아닌 동안 반복

void bfs(vertex v){
    vertex w;
    visit[v] = TRUE;
    push(v);

    while(!emptyQ()){    // queue가 empty가 아닌 동안 반복
        v = pop ();        // 방문할 vertex v 선택
        for(w = graph[v]; w!=NULL; w = w->link){
            if(visit[w] == FALSE){
                visit[w] = TRUE;    //방문한 것으로 표시
                push(w);
            }
        } 
    }
}

• 인접 행렬 : O(n), 인접 리스트 : O(1) ~ O(n)
• 성능 분석
  • 시간 복잡도 : O(m + n)

Graph Search 응용

연결 성분 찾기

void connected(){
    int i;
    int idx = 1;
    for(i = 0; i < n; i++){
        if(!visit[i]){
            dfs(i, idx);
            idx++;
        }
    }
}

신장 트리

void dfst(int v){
    nodePointer w;
    visit[v] = TRUE;

    for(w = graph[v]; w; w = w->link){
        if(!visit[w->vertex]){
            add(v, w) to the depth-first spanning tree;
            dfst(w->visit);
        }
    }
}

이중 연결 성분

분절점(Articulation point)

• 한 그래프의 vertex
• 이 vertex와 연결된 edge를 제거하면 그래프가 2개 이상의 연결 성분으로 분해되는 vertex

이중 연결 그래프(Biconnected graph)

• 분절점이 없는 그래프

이중 연결 성분(Biconnected component)

• A maximal biconnected subgraph

그래프의 이중 연결 성분을 찾는 방법 : dfs를 이용

• dfn : 깊이 우선 번호 (depth-first number)
  • 깊이 우선 탐색을 수행하는 차례대로 방문한 vertex에 부여하는 번호
• G = 신장 트리에 속한 edge + 속하지 않은 edge(nontree edge)
  • Back edge : 무방향 그래프의 깊이 우선 신장 트리에선 nontree edge = back edge

분절점 구하기

• 2개 이상의 자식 노드를 갖는 dfst의 root node는 분절점

• "u->자식w->w의 후손->back edge->u의 조상"인 경로가 없으면 u는 분절점

• low(u)

  • u에서 후손에 연결된 한번의 back edge를 통해서 갈 수 있는 vertex 중에서 가장 낮은 dfn

• 분절점 조건

  • u가 2개 이상의 child node를 갖는 신장 트리의 root node
  • u가 root node가 아니면서 다음의 조건을 만족시키는 자식 node w를 갖는 경우
    • low(w) >= dfn(u)
    • (w가 back edge를 통해서 u dnf 미만의 low를 가질 수 없다는 것)

DFS(1) : dfn 계산

int dfn[MAX_VERTEX]; //-1로 초기화
int low[MAX_VERTEX]; //-1로 초기화
void dfs1(u, v){ // v는 u의 부모
    dfn[u] = num++;

    for(w = graph[u]; w; w = w->link){
        if(dfn[w] < 0)
            dfs1(w, u);
    }
}

DFS(2) : low 계산

void dfs1(u, v){ // v는 u의 부모
    dfn[u] = low[u] = num++;

    for(w = graph[u]; w; w = w->link){
        if(dfn[w] < 0){
            dfs2(w, u);
            low[u] = min(low[u], low[w]);
        }
        else if(w != v)
            low[u] = min(low[u], low[w]);
    }
}

DFS(3) : 분절점 계산

void dfs1(u, v){ // v는 u의 부모
    dfn[u] = low[u] = num++;

    for(w = graph[u]; w; w = w->link){
        if(dfn[w] < 0){
            dfs2(w, u);
            low[u] = min(low[u], low[w]);
            if(low >= dfn[u])
                print("u: articulation point");
        }
        else if(w != v)
            low[u] = min(low[u], low[w]);
    }
}

DFS(4) : 이중 연결 성분 계산

void dfs1(u, v){ // v는 u의 부모
    dfn[u] = low[u] = num++;

    for(w = graph[u]; w; w = w->link){
        if(dfn[w] < 0){
            push(u, w);
            dfs2(w, u);
            low[u] = min(low[u], low[w]);
            if(low >= dfn[u]){
                print("new bicon:");
                do{
                    pop(&x, &y);
                    print(<x,y>);
                }while(x != u || y != w);
            }
        }
        else if(w != v)
            low[u] = min(low[u], low[w]);
    }
}

시간 복잡도

• BCC : O(n+m)