U E D R , A S I H C RSS

Data Structure/Graph


오랜만� 공백� 깨고! �료 구조 정리를 계� 하�� 하겠습니다.^^;


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) }


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
  • 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. Shortest Paths


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

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:05
Processing time 0.0132 sec