8강. 그래프 (1)

1. 그래프

• 그래프 G → G = (V, E)
  • V : 정점(vertex)의 집합 ( 원 )
  • E : 간선(edge)의 집합 ( 정점을 연결하는 선 )
    • 간선에 방향이 없으면 무방향 그래프
      • ex ) 간선표시 : (1,4), (4,1)
    • 간선에 방향이 있으면 방향 그래프
      • ex ) 간선표시 : <1,4> ( 1 → 4 )
      • ex ) 간선표시 : <4,1> ( 4 → 1 )
    • 간선에다가 의미나 값( 가중치 )을 부여하면 가중 그래프
• 트리
  • 트리가 되는 조건
    • 무방향 그래프일 것
    • 모든 정점이 연결되어있을 것
    • 사이클이 존재하지 않을 것
• 그래프 표기 예시
  • V(G₂) = {1, 2, 3, 4, 5}
  • E(G₂) = {(1,2), (1,4), (2,5), (3,5)}

2. 그래프의 주요 용어

• 인접( adjacent ), 부수( incident )
• 부분 그래프( subgraph )
• 경로( path ), 경로의 길이( length )
• 차수( degree )
  • 진입차수( in-degree ), 진출차수( out-degree )
• 단순 경로( simple path ), 사이클( cycle ), 루프( loop )
• 연결( connected )
• 강하게 연결( strongly connected ), 약하게 연결( weakly connected )

3. 그래프의 구현 방법

• 인접 행렬 ( adjacency matrix )
  • 2차원 행렬로 표시
    • 가중 그래프 X
      • 대각선을 0으로 표시
      • 연결된 간선의 개수대로 값을 채움
    • 가중 그래프
      • 대각선을 0으로 표시
      • 간선의 가중치에 따라서 값을 채움
      • 연결된 간선이 존재하지 않는 경우 ∞로 표시
• 인접 리스트 ( adjacency list )
  • 연결 리스트로 표시
    • 가중 그래프 X
      • 연결 리스트로 인접한 정점을 표시
    • 가중 그래프
      • 연결 리스트로 인접한 정점과 각 가중치를 표시

4. 그래프 순회

• 그래프의 모든 정점을 체계적으로 한 번씩 방문하는 것
  • 그래프 탐색 방법
• 순회 방법
  • 깊이 우선 탐색 ( DFS, Depth First Search )
    • 최근의 주변 정점을 우선 방문
  • 너비 우선 탐색 ( BFS, Breadth First Search )
    • 주변 정점 중에서 오래된 것을 우선 방문
• 탐색 과정에서의 정점의 구분
  • 방문 정점
    • 방문이 완료된 정점
  • 주변 정점
    • 방문 정점에 인접한 정점 중에서 아직 방문하지 않은 정점
  • 미도달 정점
    • 방문 정점도 주변 정점도 아닌 전혀 접근하지 못한 정점

5. 깊이 우선 탐색

• 한 정점을 시작으로 매번 인접한 정점 중 한 곳으로 이동하며 탐색하는 방법
  • 최근의 주변 정점을 우선으로 방문하는 탐색 방법
• 스택 구조를 사용해서 구현
  • 현재 정점에 인접한 정점이 없어서 더 이상 탐색을 진행할 수 없으면 거꾸로 되돌아가면서 아직 탐색하지 않은 인접한 정점을 찾아서 탐색을 진행
• 처리 과정
  • ① 시작 정점을 스택에 삽입
  • ② 스택의 top에 있는 정점에 대한 주변 정점이 존재하면 그중 하나의 정점을 스택에 삽입하고 방문한 정점으로 처리. 주변 정점이 없다면 스택의 top에 있는 정점을 제거
  • ③ 스택에 더 이상의 정점이 없을 때까지 ②의 과정을 반복
• 깊이 우선 트리
  • DFS( 깊이 우선 탐색 )를 수행하는 과정에서 방문한 정점과 그때 사용된 간선으로 구성되는 트리

6. 깊이 우선 탐색 알고리즘

DepthFirstSearch(G, s) {      // G: 입력 그래프, s: 시작 정점
    Push(Stack, s); // 시작 정점을 스택에 삽입
    while (Stack != NULL) { // 2단계 반복
        c = Stack의 top에 있는 정점;
        c.visited = TRUE;
        정점 c를 방문 정점으로 출력;
        do {
            for (v ← c의 모든 인접한 정점) {
                if (v.visited == FALSE) { // 주변 정점
                    Push(Stack, v) 후 while문으로 이동;
                }
            }
            c = Pop(Stack);
        } while (Stack != NULL);
    }
}

7. 깊이 우선 탐색의 성능과 특징

• 인접 리스트 → O(|V| + |E|) ( 정점의 개수 + 간선의 개수 )
• 인접 행렬 → O(|V|²) ( 정점의 개수의 제곱 )
• 순환 알고리즘

DFS_recursion(G, current) {
    current.visited = TRUE;
    방문 정점으로 current 출력;
    for (next ← current의 모든 인접한 정점) {
        if (next.visited == FALSE)
            DFS_recursion(G, next);
    }
}

8. 너비 우선 탐색

• 시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문한 후 시작 정점과의 거리가 점점 멀어지는 순서로 인접 정점들을 탐색하는 방법
  • 거리 : 시작 정점으로부터의 경로의 길이
  • 주변 정점 중에서 가장 오래된 것부터 우선 방문하는 방법
• 큐를 사용하여 주변 정점을 관리

9. 너비 우선 탐색 알고리즘

BreadthFirstSearch(G, s){
    Enqueue(Queue, s);
    s.flag = TRUE;
    while (Queue != NULL) {
        c = Dequeue(Queue);
        정점 c를 방문 정점으로 출력;
        for (v ← c의 모든 인접한 정점) {
            if (v.flag == FALSE) {
                Enqueue(Queue, v);
                v.flag = TRUE;
            }
        }
    }
}

10. 너비 우선 탐색의 성능

• 인접 리스트 → O(|V| + |E|) ( 정점의 개수 + 간선의 개수 )
• 인접 행렬 → O(|V|²) ( 정점의 개수의 제곱 )

11. 위상 정렬

• 무사이클 방향 그래프( DAG, Directed Acyclic Graph )에서 모든 간선이 한 방향으로만 향하도록 정점을 한 줄로 나열하는 것
• 깊이 우선 탐색을 활용하여 구현
  • DFS를 수행하다가 더 이상 주변 정점이 없어서 되돌아갈 때, 스택에서 삭제되는 정점을 역순으로 나열하면 됨

12. 그래프의 연결성

• 정점 간의 연결 관계를 다루는 것
  • 연결 성분 ( connected component )
  • 강연결 성분 ( strongly connected component )

13. 연결 성분

• 무방향 그래프에서 임의의 두 정점 간의 경로가 존재하는 최대 부분 그래프
• 너비 우선 탐색 또는 깊이 우선 탐색을 활용하여 구함
  • while ( 아직 탐색하지 않은 정점이 존재 ) 탐색을 수행하다가 큐/스택이 비게 되면 그때까지 탐색한 정점들을 하나의 연결 성분으로 구성

14. 강연결 성분

• 방향 그래프에서 임의의 두 정점 사이에 양방향의 경로가 존재하는 최대 부분 그래프
  • ① 깊이 우선 탐색을 적용하여 정점의 방문 완료 순서(방문 순서의 역순)를 구함
  • ② G=(V,E)에 대해 ER={<v,u>|<u,v>∈E}을 사용한 GR=(V, ER)을 구함
  • ③ GR에 대해서 방문 완료 번호가 큰 것부터 DFS를 수행하여 갈 수 있는 정점들의 각 리스트가 강연결 성분이 됨