Graph

<Graph>
- 비선형 구조 가운데 하나인 그래프
- 정점(node)와 간선(edge)으로 이루어진다
- 컴퓨터, 수학, 공학 등의 많은 분야(최단거리 분석, 연구계획/공정분석, 회로 분석 등)에서 객체 사이의 관계를 표현하는 도구로서 사용
- 기판, 컴퓨터 설계 : 수 만개 구멍을 레이저드릴로 천공
- 그래프(Graph)는 정점(vertex)와 간선(edge)의 집합으로 정의
- 정점의 집합 V는 정점들의 유한집합이고 간선의 집합 E는 정점들을 연결하는 선의 집합
- 그래프의 표기 : G=(V,E)
- 하나의 간선 E는 (Vi, Vi)로 두 개의 정점으로 표현된다

- 그래프는 간선의 양끝 정점사이의 순서를 고려에 따라
   - 방향 그래프(directed graph)
  - 무방뱡 그래프(undirected graph)

- 방향 그래프 : 간선의 순서가 고려된다
  - 즉, (V1, V2)에서 V1은 시작 정점이고, V2는 종점
  - n개의 정점으로 이루어진 간선(Vi, Vi)의 최대 수 : n(n-1)

- 무 방향 그래프 : 간선의 순서가 무관한 그래프
  - 즉, (V1, V2)와 (V2, V1)은 동일한 간선
  - n개의 정점으로 이루어진 간선(Vi, Vi)의 최대 수 : n(n-1)/2

- 한 정점에서 차수는 그 정점에 인접한 간선들의 수
- 방향그래프의 경우에는 정점으로 들어오는 간선(in_degree)과 정점에서 나가는 간선(out_degree)의 합으로 차수를 구한다

- 인접(adjacent) : 두 정점 V1과 V2사이에 간선이 존재할 때, V1과 V2는 인접

- 조인(V, W) : 정점 V와 W사이에 간선을 추가하는 것

- 조인가중(V, W, X) : 간선을 정점 V와 W사이에 추가 후 가중치 X를 부여하는 것

- 경로(Path) : 정점 V1, V2, ... , Vn이 간선 (V1, V2), (v2, V3), ... ,(V(n-1), Vn)을 가질 때 정점의 순서를 말한다

- 경로 길이(Path length) : 경로를 이루는 간선의 수

- 단순 경로 : 경로상의 시작과 끝 정점을 제외하고 모든 정점이 서로 다른 경로

- 사이클(Cycle) : 시작과 끝 정점이 같은 단순 경로

- cycle : Cycle이 포함된 그래프

- acyclic : Cycle이 없는 그래프

- dag : directed acyclic graph 

- 완전 그래프 : n개의 정점을 갖는 graph에서 모든 서로 다른 정점의 쌍 사이에 간선이 존재
  모든 정점의 차수가 n-1, 간선의 수는 n(n-1)/2

- 가중 그래프(weighed graph) : 간선에 가중치를 부여하는 그래프로서 무게, 거리, 시간 등의 수치를 나타내도록 한다

- 연결요소(Connected component) : 적어도 하나 이상의 경로로 연결된 정점들로 구성된 그래프

- 강력 연결그래프 : 방향 그래프에서 임의의 두 정점에서, 한 정점으로부터 다른 정점까지 간선의 방향에 따라 도달 가능한 그래프를 말한다

- 다중 그래프 : 임의의 정점 쌍에 두 개 이상의 간선이 존재하거나 루프(loop)가 존재하는 경우

- 부분 그래프(sub graph) : V1(G1) ⊆ V2(G2) 이고 E1(G1) ⊆ E2(G2)일 때 G1 ⊆ G2가 성립한다

- 정규 그래프(regular graph) : 모든 정점의 차수가 같은 그래프

- 동형 그래프(isomorphic graph) : 두개의 그래프간 정점, 차수, 간선의 수가 동일한 그래프이다

- 인접행렬(adjacenct matrix)와 인접리스트(adjacency list) 그리고 인접 다중 리스트(adjacency multi_list)가 주로 사용

- 인접행렬(adjacency matrix) 표현
  - 행렬을 사용하여 그래프 내의 정점들 간의 인접여부에 대한 정보를 표현한다

- 무 방향 그래프의 인접행렬
  - 무방향 그래프의 경우 M[i, j]와 M[j, i]가 동일하므로 행렬은 대각선을 중심으로 대칭
  - 행렬의 1의 수가 간선수의 2배
  - 임의의 간선 (Vi, Vj)에 대해 무방향 그래프의 경우 정점 Vi의 차수는 행의 합



<행렬의 구성>
- 행과 열이 정점의 수와 같도록 행렬식을 구성
- 그래프에 있는 정점의 개수가 n개이면 nxn의 행렬식 구성
- 초기 행렬은 모두 0으로 초기화
- 무방향 그래프이므로 간선(Vi, Vj)와 간선(Vj, Vi)는 동일한 의미를 갖는다
  따라서 모든 간선 (Vi, Vj)에 대해서 i행 j열과 j행 i열에 각각 1의 값을 설정
- 주어진 하나의 정점 Vi의 차수는 i행의 합이 된다
- 만일 가중 그래프(weighed graph)가 사용된다면 행렬의 값이 1대신 부여된 숫자 값으로 표현



<방향 그래프의 인접행렬>
- 방향 그래프의 경우 M[i,j]와 M[j,i]가 다를 수 있으므로 행렬은 대칭을 이루지 않는다
- 임의의 간선(Vi, Vj)에 대해 방향 그래프의 경우 정점 Vi의 진출차수(out_degree)는 i행의 합
- 진입차수(in_degree)는 i열의 합
- 따라서 정점 Vi의 차수는 진입차수와 진출차수의 합



<인접행렬의 단점>
- 정점의 수를 미리 알아야하고
- 정점에 대한 삽입 또느 삭제 연산이 수행될 때 인접행렬을 다시 작성해야 하는 단점
- 실제적인 응용에서 행렬은 정점의 크기가 늘어날수록 제곱으로 증가하므로 공간복잡도 측면(O(n^2))에서 상당히 비효율적인 구조
- 인접행렬은 배열의 형태로 구현되므로 배열의 단점 존재
- 하나의 정점에서 다른 정점으로 길이 1,2 또는 3 크기의 경로가 있다는 사실을 표현할 수 있으나 시제로 두 정점 사이에 거치는 경로를 표현하지는 못한다
- 인접행렬의 단점을 보완하는 방식이 인접리스트를 활용



<인접리스트>
- 인접리스트는 각 정점에 인접하는 다른 정점들을 노드의 데이터필드에 저장하고 노드들을 포인터로 연결
- 각 리스트에서 노드의 순서는 의미가 없다
- 하나의 정점에 각 노드에 표현된 정점들이 인접한다는 것을 표현
- 인접리스트는 단순 연결리스트로 구현된다
  - 하나의 데이터 필드와 하나의 연결필드로 노드가 구성
  - ex)
  struct node{
  int data;
  struct node *link;
  };
- 인접리스트의 Head를 배열로 표현하는 것은 인접행렬표기와 마찬가지로 배열의 단점에 의해 그래프의 확장을 표현할 수 없는 단점이 존재
- 따라서 Head를 배열이 아닌 연결리스트로 표현하는 것이 실제 구현에 효율적이다