Graph
Vertex(정점)와 Vertex를 연결하는 Edge(간선)들의 집합으로 tree와 마찬가지로 비선형 자료구조이다. (tree도 grahp의 한 종류라고 볼 수 있다!)
V = {0, 1, 2, ,3, 4, 5, 6}
E = {(0,1), (1,2), (1,3), (2,5), (2,6), (3,4), (3, 5)}
Graph 용어
다음은 그래프에서 자주 사용되는 용어이다.
정점(vertex): node라고 부르며, data를 저장하고 있음
간선(edge): vertex간의 연결 관계를 나타냄 (vertex의 쌍으로 표현)
(무향 간선: 방향이 없는 간선 / 유향 간선: 방향이 있는 간선)
인접(Adjacent): 정점 u,v에 대해 간선 e = (u, v)가 존재하면, 정점 u와 v는 인접
부속(Incident): 정점 u,v에 대해 간선 e = (u, v)가 존재하면, 간선 e는 정점 u와 v에 부속
차수(Degree): 정점에 부속된 간선 수
(in-degree: 방향 그래프에서 들어오는 간선 수 / out-degree: 방향 그래프에서 나가는 간선 수)
경로(Path): 정점과 간선이 교대로 구성된 시퀀스 ex) [V1, e1, V2]
단순 경로(Simple Path): 정점과 간선이 중복되지 않는 경로
회로(Cycle): 시작 정점과 끝 정점이 같은 경로
연결(Connected): 정점 u에서 정점 v로의 경로가 존재하면, 정점 u와 v는 연결
Graph 종류
Undirected Graph (무향 그래프)
무향 간선으로 이루어진 그래프 
Directed Graph(유향 그래프)
유향 간선으로 이루어진 그래프 
Weighted Graph(가중치 그래프)
가중치를 갖는 간선으로 이루어진 그래프 
Regular Graph(정규 그래프)
모든 정점이 동일한 차수를 가지는 그래프 
Complete Graph(완전 그래프)
임의의 두 정점 u, v에 대해서 u, v를 잇는 간선이 존재하는 그래프 
Connected Graph(연결 그래프)
임의의 두 정점 u, v에 대해 경로가 존재하는 그래프
Graph 구현
Edge List
- 정점의 개수가 V개, 간선의 개수가 E개인 그래프 정보를 E x 2 (or E x 3) 이차원 배열에 저장
- E x 3 => 가중치를 함께 저장하는 경우
Adjacency Matrix
- 정점의 개수가 V개, 간선의 개수가 E개인 그래프 정보를 V x V 이차원 배열에 저장
- 간선이 존재하면 1(or 가중치), 존재하지 않는다면 0
Adjacent List
- 정점의 개수가 V개, 간선의 개수가 E개인 그래프 정보를 V개의 연결 리스트에 저장
listorvector로 구현
