오랜만ì�˜ 공백ì�„ ê¹¨ê³ ! ìž�료 구조 ì •ë¦¬ë¥¼ 계ì†� 하ë�„ë¡� í•˜ê² ìŠµë‹ˆë‹¤.^^;
1. 기본 ê°œë…� ¶
- Vertex( ì � )
- Edge( ì„ )
- Directed Graph - Edge� 방향� 있는 그래프
- Undirected Graph - Edge� 방향� 없는 그래프
2. 한붓 그리기 ¶
- ëª¨ë“ Vertexì�˜ Edgeê°€ ì§�수개 ì�¼ë•Œ
- Vertex� Edge� 수가 홀수개� 것� 2개�때
3. 표현 ¶
~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 대ê°�ì„ ì�„ 기준으로 대ì¹ì�´ 아님
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가 있나요?
- ë°°ì—´ : θ(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