[[TableOfContents]]

오랜만의 공백을 깨고! 자료 구조 정리를 계속 하도록 하겠습니다.^^;


= 기본 개념 =
 * Vertex( 점 )
 * Edge( 선 )
 * Directed Graph - Edge의 방향이 있는 그래프
 * Undirected Graph - Edge의 방향이 없는 그래프


= 한붓 그리기 =
 * 모든 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 ||  ||

== 배열로 표현한 Graph와 리스트로 표현한 Graph의 비교 ==
 * 두 Vertex 사이에 Edge가 있나요?
  * 배열 : θ(1) - 2차원 배열의 첨자로 ar[x][y] 단번에 접근 가능! 고로 배열이 좋단 말입니다.
  * 리스트 : θ(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를 넣어준다.
  * 리스트 : 필드를 하나 추가하자. (귀찮다)           
 * 결론 : 뭐가 더 낳다 꼴았다 할 그런건 없지만.. 구현의 편리성과 같은 부수적인 것을 따져볼때 배열을 애용하는게 좋을것 같단 말입니다!


= 기본 연산 =
 * Traversal(탐색) 
  * Depth First Search(우리말로 깊이 우선 탐색) : 한우물을 쭉 파나간다는 말입니다. 가다가 막히면 빽. 스택 이용(또는 재귀). 처음으로 돌아오면 쫑난답니다. 
  * Breadth First Search(우리말로 너비 우선 탐색) : 첨 Vertex를 큐에 넣습니다. 뺍니다. 거기에 이어진 Vertex를 큐에 다 넣습니다. 앞에서부터 빼면서 그 노드에 연결된 Vertex를 계속 추가시켜줍니다. Queue가 비게 되면 쫑나는 거랍니다. 너비 우선 탐색을 트리에 적용시키면 그게 바로 Level Order가 되는 것이란 말이져.

= 최소 비용 신장 트리(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중 가장 작은걸 선택한다.
  * 이짓을 반복한다.

= Shortest Paths =

== Single Source, All Destination(하나의 시작점에서 모든 곳으로의 Shortest Path를 구할수 있단말이다) ==
 * Dijkstra's Algorithm
  * 표현은 인접 행렬(Adjancey(??) Matrix)로 표현(그러니까 2차원 배열)
  * cost[i, j] : i -> j 로 가는 Cost
  * 초기값 : S = { V0 } V0 : Source, 
  * 중간 S : { 지금까지 Shortest Path가 결정된 Vertex들 } : 그러니까 결정되면 S에 넣는다는 말이다.
  * dist[w] : 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값 갱신 : dist[w] = min { dist[w], dist[u] + cost[u, w] }

== 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"]