오랜만의 공백을 깨고! 자료 구조 정리를 계속 하도록 하겠습니다.^^;
1. 기본 개념 ¶
- Vertex( 점 )
- Edge( 선 )
- Directed Graph - Edge의 방향이 있는 그래프
- Undirected Graph - Edge의 방향이 없는 그래프
2. 한붓 그리기 ¶
- 모든 Vertex의 Edge가 짝수개 일때
- Vertex의 Edge의 수가 홀수개인 것이 2개일때
~cpp
요런 모양의 Undirected Graph가 있다고 가정합시다.
2
/ |
0 - 1 |
| /
3
알아 볼수 있을런지..--;
V = { 0, 1, 2, 3 }
E = { (0,1), (1,3), (1,2), (2,3) }
- 2차원 배열로 표현합니다. 정식 이름은 Adjacency Matrix(맞나?--;)
- 먼저 Undirected Graph
| | 0 | 1 | 2 | 3 |
| 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 0 |
- Vertex 사이에 Edge가 존재할때 그 곳의 값을 1로 셋팅
- LeftUpper -> RightLower 대각선을 기준으로 대칭
- 다음엔 Directed Graph
~cpp
2
/ |
0 <- 1 |
| /
3
* .... 화살표 표현하기가 암울하군요..--; 어쨌든 < Vertex1, Vertex2 > 요런 표현을 씁니다.
* 만약에 Vertex1 -> Vertex2의 방향으로 Edge가 있다면 < Vertex1, Vertex2 > 이렇게 쓴단 말입니다.
* 화살표를 그릴수 없는 관계로 순서쌍으로 표현하면
* <1,0>, <2,1>, <3,1>, <3,2>
| | 0 | 1 | 2 | 3 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 0 |
- | - 방향으로 Edge가 존재할때 1로 셋팅
- LeftUpper -> RightLower 대각선을 기준으로 대칭이 아님
- Adjacency List(Linked List로 표현)
| 0 | -> | 1 | X | | | | | | |
| 1 | -> | 0 | - | -> | 2 | - | -> | 3 | X |
| 2 | -> | 1 | - | -> | 3 | X | |
| 3 | -> | 1 | - | -> | 2 | X | |
3.3. 배열로 표현한 Graph와 리스트로 표현한 Graph의 비교 ¶
- 두 Vertex 사이에 Edge가 있나요?
- 배열 : θ(1) - 2차원 배열의 첨자로 arxy 단번에 접근 가능! 고로 배열이 좋단 말입니다.
- 리스트 : θ(n)
- 사용하는 메모리의 양 ( n개의 Vertices, e개의 Edges )
- 배열 : θ(n^2) - n X n 개의 배열을 잡으니 당연히 n^2 --;
- 리스트 : 위의 리스트로 된 그래프 표현을 보면 Head Node의 수는 n개가 필요하고 Head Node로부터 뻗어나오는 Node의 총 수는 2*e 개가 필요하다. θ(n+e) 고로 리스트가 유리하단 말입니다.
- 한가지더 : Weighted Graph의 표현법
- 배열 : 1대신 Weight를 넣어준다.
- 리스트 : 필드를 하나 추가하자. (귀찮다)
- 결론 : 뭐가 더 낳다 꼴았다 할 그런건 없지만.. 구현의 편리성과 같은 부수적인 것을 따져볼때 배열을 애용하는게 좋을것 같단 말입니다!
4. 기본 연산 ¶
- Traversal(탐색)
- Depth First Search(우리말로 깊이 우선 탐색) : 한우물을 쭉 파나간다는 말입니다. 가다가 막히면 빽. 스택 이용(또는 재귀). 처음으로 돌아오면 쫑난답니다.
- Breadth First Search(우리말로 너비 우선 탐색) : 첨 Vertex를 큐에 넣습니다. 뺍니다. 거기에 이어진 Vertex를 큐에 다 넣습니다. 앞에서부터 빼면서 그 노드에 연결된 Vertex를 계속 추가시켜줍니다. Queue가 비게 되면 쫑나는 거랍니다. 너비 우선 탐색을 트리에 적용시키면 그게 바로 Level Order가 되는 것이란 말이져.
5. 최소 비용 신장 트리(Minimum Cost Spanning Trees) ¶
- Weighted Graph에 적용, 첫 Vertex에서 마지막 Vertex까지 끊어지지 않게 한번에 그린다.
- Kruskal's Algorithm
- Edge들을 Cost 순으로 Sort(작은것부터)
- Edge들을 순서에 따라 하나씩 연결한다. 연결하다가 Cycle이 생기면 그것은 잇지말고 제거한다. 다 이어지면 그만둔다.
- Prim's Algorithm
- Vertex를 하나 선택한다.
- 거기에 이어진 Edge중 가장 작은것을 선택한다.
- 그 Edge에 이어진 Vertex와 처음의 Vertex에 이어진 Edge중 가장 작은걸 선택한다.
- 이짓을 반복한다.
6.1. Single Source, All Destination(하나의 시작점에서 모든 곳으로의 Shortest Path를 구할수 있단말이다) ¶
- Dijkstra's Algorithm
- 표현은 인접 행렬(Adjancey(??) Matrix)로 표현(그러니까 2차원 배열)
- costi, j : i -> j 로 가는 Cost
- 초기값 : S = { V0 } V0 : Source,
- 중간 S : { 지금까지 Shortest Path가 결정된 Vertex들 } : 그러니까 결정되면 S에 넣는다는 말이다.
- distw : v0에서 출발하여 w까지의 Shortest Path의 값. 단 w를 제외하고는 S집합내에 있는 Vertex들만 거쳐야 한다.
- 예를 들자면
~cpp
Start Vertex : 4 -> S = {4}
dist[3] = 1500
dist[5] = 250 3,5 는 4에 연결되어 있음
dist[others] = 무한대
-> dist[5]가 가장 작다. 5를 S에 넣는다.
...
....
반복한다.
- 이걸 알고리즘화 하면,
- for n-1 번 반복
- dist 값중에서 최소가 되는 Vertex u 찾기
- S = S U {u}
- dist값 갱신 : distw = min { distw, distu + costu, w }
6.2. All Pairs Shortest Path ¶
- Floyd - Warshall Algorithm
- 역시 표현은 2차원 배열로 한다. 그런데 이 알고리즘은 (-) Weight 도 허용한다.(그리로 가면 이득이 된다는 말이다.) 하지만 Negative Cycle은 안된다.
- Negative Cycle? 그 사이클을 돌면 - 가 나오는길을 말한다.
- 초기 행렬을 A(-1)i, j 로 한다. 반복할수록 괄호 안의 값을 올려준다. 이걸 n-1까지 반복한다.
- A(k)i, j 라고 하면 i에서 j로 가는 Shortest Path 의 잠정적인 값이다.단 모든 길은 0 ~ k의 vertex만을 중간에 지날수 있다.
- A(k)i, j = min { A(k-1)i,j, A(k-1)i, k + A(k-1)k, j }
DataStructure
