# Graph

📊Graph

Tree구조와 비슷하게 Node와 edge로 구성

Graph에서는 node(정점) -> vertex, edge(간선) -> arc으로도 지칭

Graph는 vertex간 여러 개의 edge를 가질 수 있다.

Tree는 사실 Graph의 특수한 형태

- 하나의 부모 노드에서부터 아래 방향으로 내려오는 Graph. 즉 트리는 루트가 있고, In-degree가 1인 방향 그래프라고 말할 수 있다.

Graph의 용어

1. Vertex : 위치라는 개념(=Node)
2. Edge : 위치 간의 관계, Node를 연결하는 선(link, branch라고도 부른다)
3. Degree : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

• 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배

3. In-degree : 다른 Vertex에서 오는 간선의 수
4. Out-degree : 다른 Vertex로 가는 간선의 수

Graph 특징

그래프는 네트워크 모델 | 순회는 DFS나 BFS로 이루어진다.

부모-자식 관계라는 개념이 없다. | 2개 이상의 경로가 가능하다.

Graph 사용

버스노선도, 지도, 길찾기, Social Networks 등

Graph의 종류

• 방향 그래프

  	- 간선에 방향성이 존재하는 그래프

  • A -> B로만 갈 수 있는 간선은 <A, B>로 표시 // <B, A>와 다른 경로

• 무방향 그래프

  	- 방향성이 없는 그래프로 간선을 통해서 양방향으로 갈 수 있다.

  • <A, B> = <B, A> 같은 경로

• 가중치 그래프(Weighted Graph)

  	- 간선에 비용이나 가중치가 할당된 그래프

  • Network 라고도 한다. ex) 도시 - 도시의 연결, 도로의 길이 등

    고속도로 톨게이트비용?

• 연결/비연결 그래프

  	- 연결 : 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우

  • 비연결 : 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우

• 순환/비순환 그래프

  	- 순환 : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

  단순경로 : 경로 중에서 반복되는 정점이 없는 경우

  	- 비순환 : 순환이 없는 그래프

• 완전 그래프

  	- 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프

Graph의 탐색

깊이 우선 탐색(DFS, Depth-First Search)

- 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 즉, 넓게 탐색하기 전에 깊게 탐색하는 것이다.

- 사용하는 경우 : 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택(DFS가 BFS보다 간단)

DFS 개념 Link https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

너비 우선 탐색(BFS, Breadth-First Search)

- 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

- 깊게 탐색하기 전에 넓게 탐색하는 것이다.

- 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때

: 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴본다.

: 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

BFS 개념 Link https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

Graph의 Pseudo Code