Graph

# Graph

 - 노드(node, vertex: 정점)와 그 노드들을 연결하는 간선(edge)으로 구성되는 자료구조

 - 서로 연결되어 있는 원소들 간의 다대다 관계를 표현

 - 그래프는 방향성이 없는 무방향(undirected) 그래프도 존재하지만, 방향성(directed)을 가질 수도 있음

 - 무방향 그래프의 경우는 연결된 두 개의 노드가 대칭, 방향성을 가진 그래프는 연결된 두 개의 노드가 비대칭 관계

 

무방향 그래프

 

방향성이 있는 그래프

 

 

 ## 진입차수(in-degree)와 진출차수(out-degree)

   - 진입차수: 방향 그래프의 경우 외부에서 해당 노드로 들어오는 간선의 수

   - 진출차수: 방향 그래프의 경우 해당 노드에서 다른 노드로 향하는 간선의 수

   - 그래프의 진입차수와 진출차수를 모두 더하면 그래프에 존재하는 모든 간선의 수가 됨

 

 

 ## 그래프의 구현

 

 1. 인접 행렬 방식

 

 

	1	2	3	4
1	0	1	1	0
2	1	0	1	0
3	1	1	0	1
4	0	0	1	0

 

   - 그래프의 연결 관계를 이차원배열을 이용해 나타낸 방식

   - 노드 a에서 노드 b로 가는 간선이 있으면 1, 없으면 0으로 나타냄

   - 인접 행렬 방식을 나타내는 이차원 배열은 대칭 행렬이 됨

   - 인접 행렬 방식으로 그래프를 구현할 때는 vertex의 갯수만큼의 길이를 가지는 배열이 vertex의 갯수만큼 필요하므로

       :  V^2 의 메모리를 차지 (간선의 수와는 무관)

 

 

 2. 인접 리스트 방식

 

 

   - 그래프에 존재하는 모든 정점을 리스트에 저장한 방식

   - 노드 a와 노드 b, c가 연결되어 있다면 노드 a의 리스트에 노드 b, c를 저장해 서로 연결되어 있음을 나타냄

   - 인접 리스트 방식으로 그래프를 구현할 때 무방향 그래프의 경우 V+2E 의 메모리를 차지 (각 정점의 수 + 연결된 간선들을 양쪽 노드에 모두 저장)

   - 방향성이 있는 그래프의 경우 V+E 의 메모리를 차지 (각 정점의 수 + 간선들의 수)

 

 

 ## Graph의 Method

 

 - addNode :  그래프에 노드를 추가

/* 무방향 그래프 기준 */

addNode 연산
  1. 그래프에 노드를 추가
  2. 추가된 노드에 간선들을 저장할 리스트 생성
  

 

 - contains :  그래프에 해당 값을 가지는 노드가 있는지 판별

/* 무방향 그래프 기준 */

contains 연산
  1. 그래프에 해당 값을 가지는 노드가 존재하는지 검사
  2. 존재한다면 true / 없다면 false 리턴
  

 

 - removeNode :  그래프에서 노드를 제거

/* 무방향 그래프 기준 */

removeNode 연산
  1. 제거할 노드가 존재하는지 검색
      존재한다면
        해당 노드와 연결된 간선들을 제거
        해당 노드를 제거
      존재하지 않는다면
        함수 종료
      

 

 - hasEdge :  그래프에 특정 노드와 노드 사이를 잇는 간선이 존재하는지 판별

/* 무방향 그래프 기준 */

hasEdge 연산 (fromNode, toNode)
  1. 리스트에서 fromNode, toNode와 일치하는 노드를 검색
  2. fromNode에서는 toNode의 간선, toNode에서는 fromNode의 간선이 존재하는지 검사
  

 

 - addEdge :  특정 노드와 노드 사이를 잇는 간선을 추가

/* 무방향 그래프 기준 */

addEdge 연산 (fromNode, toNode)
  1. 리스트에서 fromNode, toNode와 일치하는 노드를 검색
  2. fromNode에서는 toNode의 간선, toNode에서는 fromNode의 간선을 추가
  

 

 - removeEdge :  간선을 제거

/* 무방향 그래프 기준 */

removeEdge 연산 (fromNode, toNode)
  1. 리스트에서 fromNode, toNode와 일치하는 노드를 검색
  2. fromNode에서는 toNode의 간선, toNode에서는 fromNode의 간선을 제거
  

 

 

 

 

오일러 경로