[자료구조] 그래프

그래프: G = (V, E)

정점(node, vertices): 객체

V(G) - 그래프 G의 정점들의 집합

꼭 있어야 함, 중복 불가, order 없음

 

간선(edge, link): 정점들 간의 관계

E(G) - 그래프 G의 간선들의 집합

없어도 됨, 중복 불가, order 없음

---

Undirected graph: 방향성이 없는 그래프

Directed graph: 방향성이 있는 그래프

 

Weighted graph: 간선에 가중치가 할당된 그래프

- 작은 걸 고르는 알고리즘이 많아서 보통 좋은 걸 작게 표현

 

Subgraph: 부분 그래프

V(G)와 E(G)의 부분 집합으로 이루어진 그래프

---

인접 정점(adjacent vertex)

하나의 정점에서 간선에 의해 직접 연결된 정점

조상 아니고 부모

 

정점의 차수(degree)

- 무방향 그래프: 하나의 정접에 연결된 다른 정점의 수

- 방향 그래프

    - 진입 차수(in-degree): 정점으로 들어오는 간선의 수

    - 진출 차수(out-degree): 정점에서 나가는 간선의 수

---

경로(Path): 정점/간선들의 sequence, 간선이 없으면 경로가 아님

단순 경로(Simple path): 반복되는 node가 없는 경로

 

Cycle: 시작 정점과 종료 정점이 동일한 경로 (s == e)

Simple Cycle:  반복되는 node가 없고, 시작 정점과 종료 정점이 동일 

eg) Hamiltonian Cycle

 

Euler Cycle

모든 간선을 한번씩만 지나서 출발 정점으로 돌아오기 

모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로가 존재 

 

Hamiltonian Cycle

모든 정점을 한번씩만 방문하여 출발 정점으로 돌아오기

---

연결 그래프(Connected / Spanning / Meshed graph)

무방향 그래프에 있는 모든 정점 쌍에 대하여 항상 경로 존재

bridge: 없어지면 그래프의 연결이 끊겨 비연결 그래프가 되는 간선

 

완전 그래프(Complete graph)

모든 정점이 연결되어 있는 그래프

n개의 정점을 가진 무방향 완전 그래프의 간선의 수: n(n-1)/2

---

그래프의 표현

인접행렬 방법

간선 ( i , j )가 존재하면 M[i][j] = 1, 없으면 0

 

out_degree: i번째 행의 값을 모두 더한 값

in_degree: j번째 열의 값을 모두 더한 값

 

인접리스트 방법

각 정점에 인접한 정점들을 연결리스트로 표현

---

그래프 탐색

하나의 정점(Source node)에서 시작하려 차례대로(order) 모든 정점들을 한번씩 방문

 

DFS(Depth First Search: 깊이 우선 탐색)

- Source node에서 멀어지는 한 방향으로 갈 수 있을 떄까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색 진행

- 돌아가기 위해 스택(Last in First Out) 필요

 

DFS-tree: DFS 중 방문한 노드를 순서대로 연결하면 트리가 됨 

- DFS-tree의 임의 노드에서 조상으로의 간선이 있으면 Cycle이 존재

- 그래프에 DFS-tree에 포함되지 않는 간선이 있으면 Cycle이 존재

void dfs_mat(GraphType* g, int v){
    visited[v] = TRUE;
    printf("정점 %d->", v);
    
    for(int w = 0; w < g->n; w++)
        if(g->adj_mat[v][w] && !visited[w])
             dfs_mat(g, w);
}

O(n^2)

void dfs_list(GraphType* g, int v){   
    GraphNode* w;
    visited[v] = TRUE;
    printf("정점 %d->", v);
    
    for(w = g->adj_list[v]; w; w = w->link)
        if(!visited[w->vertex])
            dfs_list(g, w->vertex);
}

O(n+e)

---

BFS(Breath First Search: 너비 우선 탐색) 

- Source node에서 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문

- 큐(First In First Out) 필요

void bfs_mat(GraphType* g, int v){
    QueueType q;    
    queue_init(&q);
    
    visited[v] = TRUE;
    printf("%d 방문 ->", v);
    enqueue(&q, v);
    
    while(!is_empty(&q)){
        v = dequeue(&q);
        for(int w = 0; w < g->n; w++){
            if(g->adj_mat[v][w] && !visited[w]){
                visited[w] = TRUE;
                 printf("%d 방문 ->", w);
                 enqueue(&q, w);
            }
        }
    }
}

O(n^2)

void bfs_list(GraphType* g, int v){
    GraphNode* w;
    QueueType q;
    init(&q);
    
    visited[v] = TRUE;
    printf("%d 방문->",v);
    enqueue(&q,v);
    
    while(!is_empty(&q)){
        v = dequeue(&q);
        for(w = g->adj_list[v]; w; w = w->link){
            if(!visited[w->vertex]){
                visited[w->vertex] = TRUE;
                 printf("%d 방문->",w->vertex);
                 enqueue(&q,w->vertex);
            }     
        }
    }    
}

O(n+e)

---

Spanning(Connected) Tree(No Cycle) - 신장 트리

- 그래프 내의 모든 정점을 포함하는 트리

- n개의 정점을 가지는 그래프의 신장 트리는 n-1개의 간선을 가짐

 

- 그래프가 connected graph가 아니면 DFS 결과 여러 개의 sub spanning tree를 찾게 된다

 

MST(Minimum Spanning Tree)

모든 정점들을 가장 적은 수의 간선/비용으로 연결 

---

Union-find 연산

원소가 어떤 집합(연결된 그래프)에 속하는지 알아냄

-각 그룹의 대표 노드를 설정하고 edge를 이루는 노드의 대표노드를 비교하여 같은 그룹에 있는지 검사

Kruskal's MST에서 사이클 검사에 사용

 

Find: 대표노드 찾기

parent[root1] = -1이면 root1이 대표노드 

int set_find(int curr){
    if(parent[curr] == -1) return curr;
    
    while(parent[curr] != -1) curr = parent[curr];
    
    return curr;
}

 

Union: 대표노드가 다르면 합치기 (edge 추가)

edge를 연결하면 root1의 대표노드의 parent를 root2의 대표노드로 바꿔라

void set_union(int a, int b){
    int root1 = set_find(a);
    int root2 = set_find(b);
    
    if(root1 != root2) parent[root1] = root2;
}

 

Kruskal's MST

loop이 안 생기는 가장 짧은 edge를 계속 연결

(greedy method - 각 단계에서 최선의 답을 선택하는 과정 반복, 최종도 최적인지 확인 해야함)

 

wieght가 적은 edge부터 non-decreasing order로 sort Time complexity: O(E * logE)

 

Disconnected graph에서도 동작

Forest(disconnected components)를 생산

 

void kruskal(GraphType* g){
    int edge_accepted = 0; //지금까지 선택된 간선의 수
    int uSet, vSet; 
    
    struct Edge e;
    
    set_init(g->nv); //nv는 정점의 개수, n은 간선의 개수
    qsort(g->edges, g->n, sizeof(struct Edge), compare);
    
    int i = 0;
    while(edged_accepted < (g->nv -1)){ //tree의 조건
        e = g->edges[i]; //최소 비용 간선
        
        uSet = set_find(e.start);
        vSet = set_find(e.end);
        
        if(uSet != vSet){
            printf("간선 (%d, %d) %d 선택\n", e.start, e.end, e.weight);
            edge_accepted++;
            set_union(uSet, vSet);
        }        
        i++;
    }    
}

---

Prim's MST 

지금까지 만든 MST에서 가장 가까이에 있는 정점 선택하여 MST에 추가

edge 기준이 아니라 정점 기준이라 loop 확인이 필요 없음

 

Time Complexity: O(n^2) 

 

Connected graph에서만 동작

한 개의 Connected components를 생산

int selected[MAX_VERTICES]; //MST에 포함
int distance[MAX_VERTICES]; //MST와 직접 연결된 간선 중 최소값

int get_min_vertex(int n){
    int v;
    
    for(int i = 0; i < n; i++){
        if(!selected[i]){
            v = i;
            breakl
        }
    }
    
    for(int i = v+1; i < n; i++){
        if(!selected[i] && (distance[i] < distance[v])) v = i;
    }
    
    return v;
}

void prim(GraphType* g, int s){
    int u;
    for(u = 0; u < g->n; u++) distance[u] = INF;
    
    distance[s] = 0;
    
    for(int i = 0; i < g->n; i++){
        u = get_min_vertex(g->n); //최소 distance를 가지는 정점
        selected[u] = TRUE;
        
        if(distance[u] == INF) return; //disconnected graph
        
        printf("정점 %d 추가\n", u);
        
        for(int v = 0; v <g->n; v++){ 
            if(g->weight[u][v] != INF){
                //아직 MST에 포함되지 않은 노드 v
                //방금 들어온 u랑 연결하는 게 더 짧으면 업데이트
                if(!selected[v] && g->weight[u][v] < distance[v]) 
                    distance[v] = g->weight[u][v];
            }
        }
    }
}

 

 

sparse graph: 간선이 거의 없는 그래프 - Kruskal이 유리

dense graph: 간선이 많은 그래프 - Prim이 유리

---

Shortest Path

간선들의 가중치 합이 최소가 되는 경로

 

Dijkstra 

하나의 시작 정점에서 다른 모든 정점까지의 최단경로 계산

 

Time Complexity: O(n^2)

모든 정점 상의 최단 경로를 구하려면 n번 반복: O(n^3)

 

집합 s: 최단 경로가 이미 발견된 정점들의 집합

distance 배열: s 안의 정점들만 이용해서 다른 정점들까지의 최단경로

매번 가장 distance가 작은 정점을 s에 추가 후 distance 갱신

int distanc[MAX_VRTICES];
int found[MAX_VRTICES];

int choose(int distance[], int n, int found[]){
    int min, minpos;
    min = INF;
    minpos = -1;
    
    for(int i = 0; i < n; i++){
        if(distance[i] < min && !found[i]){
            min = distance[i];
            minpos = i;
        }
    }
    
    return minpos;
}

 

Time complexity: O(V), Using min heap: O(logV)

void shortest_path(GraphTyp* g, int start){
    int u;

    //초기화
    for(int i = 0; i < g->n; i++){
        distance[i] = g->weight[start][i];
        found[i] = FALSE;
    }
    
    found[start] = TRUE;
    distance[start] = 0;
    
    for(int i = 0; i < g->(n-1); i++){
        u = choose(distance, g->n, found); //O(logN)
        found[u] = TRUE;
        
        //diatance 업데이트
        for(int w = 0; w < g->n; w++){
            if(!found[w]){
                if(distance[u] + g->weight[u][w] < distance[w])
                    distance[w] = diatance[u] + g->weight[u][w];
            }
        }
    }
}

Time complexity: O(V^2), Using min heap: O(VlogV)

---

Floyd 

모든 정점에서 다른 모든 정점까지의 최단경로 계산 

 

Time Complexity: O(n^3)

 

A_k [i][j]: 0부터 k까지의 정점만을 이용한 정점 i에서 j까지의 최단 경로 길이

A_(-1) -> A_(0) -> A_(1) ... A_(n-1) 순으로 최단 경로를 구해감

A_k[i][j] = A_(k-1)[i][k]+A_(k-1)[k][j]: 정점을 하나씩 더하면서 계속 최단거리를 찾음, 즉 방금까지 찾은 최단 거리랑 새로운 정점을 지나는 경로들을 비교해서 최단거리 업데이트 

void floyd(GraphType* g){
    for(int i = 0; i < g->n; i++)
        for(int j = 0; j < g->n; j++)
            A[i][j] = g->weight[i][j];
            
    for(int k = 0; k < g->n; k++){
        for(int i = 0; i < g->n; i++){
            for(int j = 0; j < g->n; j++){
                if(A[i][k] + A[k][j] < A[i][j])
                    A[i][j] = A[i][k] + A[k][j];             
            }       
        }    
    }
}

---

Topological sort (위상정렬)

DAG(Directed Acyclic Graph) 에서만 가능 - 방향이 있는

선행 순서를 위배하지 않으면서 모든 정점을 나열 - 동일한 그래프에 여러 위상정렬 가능

int topo_sort(GraphType* g){
    StackType s;
    GraphNode* node;
    
    int* in_degree = (int*)malloc(g->n * sizeof(int));
    for(int i = 0; i < g->n; i++) in_degree[i] = 0; //초기화
    
    for(int i = 0; i < g->n; i++){
        node = g->adj_list[i]; //정점 i에서 나오는 간선들
        
        while(node != NULL){
            in_degree[node -> vertex]++;
            node = node -> link; 
        }       
    }
    
    init($s);
    for(int i = 0; i < g->n; i++){
        if(in_degree[i] == 0) push(&s, i); 
    }
    
    while(!is_empty(&s)){
        int w;
        w = pop(&s);
        printf("정점 %d->", w);
        node = g->adj_list[w]; //w에서 나오는 간선
        
        while(node != NULL){
            int u = node->vertex;
            in_degree[u]--;
            if(int_degree[u] == 0) push(&s, u);
            node = node -> link;
        }
    }
    
    free(in_degree);
    printf("\n");
    return(i == g->n) //1이면 성공, 0이면 실패       
}