[Data Structure] 그래프 (Graph)

그래프 정의

정점(Vertex)과 그 정점을 연결하는 간선(Edge)을 모아놓은 자료구조

활용 : 네트워크, 지하철, 지도 등

그래프 용어

정점(vertex)	위치라는 개념(node 라고도 부름)
간선(edge)	위치 간의 관계. 노드를 연결하는 선(link, branch 라고도 부름)
인접 정점(adjacency vertex)	간선에 의해 직접 연결된 정점
차수(degree)	정점에 연결된 다른 정점의 개수 => 진입 차수(in-degree), 진출 차수(out-degree)
경로(path)	정점의 나열로 표현
경로의 길이(path length)	경로를 구성하는 데 사용된 간선의 수
단순 경로(simple path)	경로 중에서 반복되는 정점이 없는 경우
완전 그래프(complete graph)	그래프에서 간선의 수가 최대인 그래프를 말함

그래프 종류

무방향 그래프

무방향 간선만 사용

간선을 통해 양방향으로 이동 가능

 

방향 그래프

방향 간선만 사용

간선을 통해 한 방향으로만 이동 가능

그래프 구현

인접 행렬(Adjaceny Matric)

2차원 배열 이용

정점과 간선으로 표현

인접 리스트(Adjacency LIst)

링크드 리스트 이용

정점과 인접 정점으로 표현

정점	인접 정점
0	2
1	4
2	3
3	3
4	2