랜만 공 깨고! 료 구 리를 록 겠다.^^;
3. ¶
~cpp
런 모 Undirected Graph가 다고 가다.
2
/ |
0 - 1 |
| /
3
볼 런..--;
V = { 0, 1, 2, 3 }
E = { (0,1), (1,3), (1,2), (2,3) }
3.1. 배 ¶
- 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 |
~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 |
3.2. 리 ¶
- 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가 나?
- 는 메모리 ( n개 Vertices, e개 Edges )
- 배 : θ(n^2) - n X n 개 배 당 n^2 --;
- 리 : 리로 된 그래 보면 Head Node 는 n개가 고 Head Node로부 뻗나는 Node 는 2*e 개가 다. θ(n+e) 고로 리가 리단 말다.
- 배 : θ(n^2) - n X n 개 배 당 n^2 --;
- 가더 : Weighted Graph 법
- 배 : 1대 Weight를 다.
- 리 : 드를 나 가. (귀다)
- 배 : 1대 Weight를 다.
- 결론 : 뭐가 더 낳다 꼴다 그런 만.. 구 리과 같 부 것 따볼때 배 는게 것 같단 말다!
4. 기본 ¶
- Traversal()
- Depth First Search(리말로 깊 ) : 물 나다는 말다. 가다가 막면 빽. (또는 귀). 로 돌면 난답다.
- Breadth First Search(리말로 ) : Vertex를 다. 뺍다. 기 Vertex를 다 다. 부 빼면 그 노드 결된 Vertex를 가다. Queue가 게 되면 나는 랍다. 리 면 그게 바로 Level Order가 되는 것란 말.
- Depth First Search(리말로 깊 ) : 물 나다는 말다. 가다가 막면 빽. (또는 귀). 로 돌면 난답다.
5. 리(Minimum Cost Spanning Trees) ¶
- Weighted Graph , Vertex 막 Vertex까 끊 게 그린다.
- Kruskal's Algorithm
- Edge들 Cost 로 Sort(것부)
- Edge들 따라 나 결다. 결다가 Cycle 기면 그것 말고 다. 다 면 그만둔다.
- Edge들 Cost 로 Sort(것부)
- Prim's Algorithm
- Vertex를 나 다.
- 기 Edge 가 것 다.
- 그 Edge Vertex Vertex Edge 가 다.
- 반복다.
- Vertex를 나 다.
6.1. Single Source, All Destination(나 모든 곳로 Shortest Path를 구 단말다) ¶
- Dijkstra's Algorithm
~cpp
Start Vertex : 4 -> S = {4}
dist[3] = 1500
dist[5] = 250 3,5 는 4 결되
dist[others] = 무대
-> dist[5]가 가 다. 5를 S 는다.
...
....
반복다.
