Representation
1. Adjacency Matrix (인접 행렬)
: 2차원 배열로 각 vertex간의 연결유무를 표현한다. undirected graph라면 symmetric 형태이다.
: (단점) 공간이 낭비될 수 있고, "몇개의 edge가 있나?" 같은걸 해결하는데 최소 O(n^2)이 걸린다.
2. Adjacency List (인접 리스트)
: 각 vertex를 array의 elements로 나타낸 후, 해당 vertex에 연결된 vertex들을 각 elements의 linked list로 연결한다.
: undirected graph라면 두 vertex 모두에 각각 하나씩 만들어서 연결해야한다.
: 쌩 1차원 배열로 나타낼 수도 있다. n+2e+1만큼 공간 필요. 0~i까지는 vertex i의 adjacency vertex를 저장할 공간의 starting point를 저장한다. 즉 vertex i에 대한 정보는 사실 node[node[i]]~node[node[i+1]-1] 에 저장된다.
3. Adjacency Multilist
: 위 두가지 방법은 vertex 기준으로 표현했지만, 여기선 edge를 기준으로 표현한다.
: 음.. 쓸일이 크게 없을 것 같아 나오면 공부하는걸로...
Graph Operations
1. DFS
: preorder traversal도 dfs의 한 종류라 둘이 비슷하다.
둘의 차이는 DFS는 graph이니 cycle이 있을 수 있어서 "방문한 node인지 확인" 작업 필요
"Stack을 이용"한다. 재귀써서 system stack쓰든, 코드내 stack 쓰든... 다시 올라올 방법 필요
2. BFS
: 마찬가지로 cycle이 있어서 같은 node 방문할 수 있으니 "방문했는지 확인" 필요 + "Queue"를 이용한다.
3. Connected components 찾기
: 그냥 node 하나 잡고 dfs/bfs 돌리면 연결된 놈들 다 출력된다.
loop 돌리면서 node들 visited 확인해서 방문안했으면 dfs에 넣고 하는 식으로 connected components끼리 출력할 수 있다.
Minimum Cost Spanning Tree (MST)
Spanning Tree : 쉽게말해 n개 vertex가 있는 모두 연결된 graph가 있을때, 그 subgraph 중 n개 vertices와 n-1개 edges를 가지는 graph(tree)를 말한다.
(general한 경우를 말한 것이고, 엄밀한 정의는 아니라 좀 오류가 있을 수도..)
DFS로 spanning tree를 depth first spanning tree, BFS로 찾은 spanning tree를 breadth first spanning tree라고 한다.
▶ Minimum cost spanning tree 찾는 법
아래 셋 다 Greedy Method이다. 각 방법이 MST를 찾아낸다는 증명은 DS책 참고.
1. Kruskal
: cost가 가장 작은 edge부터 더한다. 해당 edge가 cycle을 형성하면 무시하고 다음 놈을 본다. n-1개 edges 찾을때까지..
2. Prim
: 한 vertex로부터 시작해 가장 적은 cost의 edge를 더해나간다. 마찬가지로 cycle pass하고 n-1개 edge 찾을때까지..
kruskal VS prim
vertex에 비해 edge가 많은 dense graph라면 Prim이 낫고,
edge가 간간히 있는 sparse graph라면 Kruskal이 낫다.
Shortest Path & Transitive Closure
셋 다 특정 출발지(혹은 전체 출발지)로부터 모든 다른 vertex까지의 최단거리를 구하는 알고리즘이다.
2번과 3번은 음수 가중치가 있어도 동작하지만, 음수 사이클이 있으면 안된다.
셋 다 보통 adjacency matrix를 이용해 가중치를 표현하는데(각각이 구해야하는 최단거리 데이터는 이것과 별개로 저장),
time complexity 줄이고 싶으면 adjList 같은 것도 가능하다.
1. Dijkstra
: Single 출발지 -> All 목적지
: 양수 가중치
: greedy method
: 집합 S를 가정한다. S에는 최단거리가 결정난 vertex들이 들어간다.
출발 vertex부터 dist 배열을 통해 최단 거리인 애들을 찾아서 S에 넣는다.
S에 새로운 vertex가 추가될때마다 S 밖의 vertex들까지 거리(dist)는 추가된 새로운 vertex를 이용한 경로와 비교해 업데이트돼야한다. dist[u]+length(<u,w>)와 기존 dist[w]를 비교해 더 짧은 값으로 갱신한다. 그리고 다시 최솟값을 찾고.. 반복!
더 자세한 논리 과정은 여기 참고(좀 길긴한데 밑에 찾아보면 있음..)
2. Bellman-Ford
: Signle 출발지 - > All 목적지 (all cost)
: 음수 가중치도 허용(음수 사이클은 안됨)
: DP method
: 최단거리를 찾는데 사용하는 edge 개수를 늘려가며 최단 거리를 찾는다. 자세한 식은 여기 참고 (edge n-1개까지 반복)
3. Floyd-Warshall
: All 출발지 -> All 목적지 (all cost)
: 음수 가중치도 허용(음수 사이클은 안됨)
: DP method
: 최단거리를 찾는데 사용하는 vertex 개수를 늘려가며 최단 거리를 찾는다. 자세한 식은 여기 참고 (vertex n개까지 반복)
▶ Transitive Closure
directed graph의 특정 vertex에서 다른 vertex로 가는 길이 있는지 확인할 수 있다.
가중치들을 edge 존재 유무만을 이용해 1과 0으로 세팅한 뒤, 바로 위 floyd-warshall algorithm을 이용하면 모든 pairs에 대해 길 존재 유무를 알 수 있다.