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 2009-05-27 07:09:19
Processing time 0.0928 sec