[자료구조] 그래프 Graph

Language/Algorithm

[자료구조] 그래프 Graph

migrationArc 2021. 6. 13. 16:29

[자료구조] 그래프 Graph

그래프 Graph

정점 (vertex / node) , 간선 (edge / link) 로 이루어진 자료구조

정점과 간선은 집합이기 때문에 중복된 값을 가지지 않는다.
그래프는 꼭 연결되어 있을 필요도 없고, 간선이 반드시 서로 다른 두 정점을 연결해야 할 필요도 없다.
비선형 자료구조이다. 즉, 선형 자료구조와 다르게 하나의 원소 다음에 여러개의 원소가 올 수 있다. (1:M , 0 <= M)

그래프(G) = 정점 집합 (V) + 간선 집합 (E)

G = (V, E)

정점 (vertex / node): 여러가지 특성을 가질 수 있는 객체
간선 (edge / link): 정점들간의 관계

그래프 기본 용어

인접(adjacent) : 간선에 의해 두 정점이 연결되어 있을 경우 인접한다고 한다.

인접 정점(adjacent vertex) : 한 정점에 인접한 정점

차수(degree) : 정점에 연결된 간선의 수(정점이 부속하는 간선 수)

진입 차수(in-degree) : 해당 정점을 끝으로 하는 간선의 수(=내차수) => 외부에서 오는 간선 수

진출 차수(out-degree) : 해당 정점을 시작으로 하는 간선의 수 (=외차수) => 외부로 나가는 간선 수

루프(loop) : 간선 하나에 동일 노드가 연결(부속)되어 있는 경우

경로(path) : 간선을 따라 갈 수 있는 길. 정점의 나열로 표시

ex) <s,v1>, <v1, v2>, ... , <vk, e> 또는 (s, v1, v2, ... , vk, e) 와 같이 표시 (나열된 정점의 수 = 간선수 + 1)

나열된 정점 사이에는 반드시 간선이 존재해야한다. 즉, 나열된 정점 사이에 간선이 없을 경우 경로가 아니다

경로의 길이(path length) : 경로를 구성하는 간선의 수

단순 경로(simple path) : 중복 간선이 없는 경로

사이클(cycle) : 단순 경로의 시작과 종료 정점이 같은 경로 => 중복 간선이 없고 시작 노드와 마지막 노드가 같음

최단 경로(shortest path) : 두 정점 사이의 경로 중 가중치 또는 비용이 최소인 경로

두 정점 사이의 거리(distance) : 두 정점의 최단 경로의 경로의 길이 : d(u,v)

연결(Connected) : 두 정점 사이에 경로가 존재하면 연결 되었다고 한다.

그래프와 트리의 차이

	Graph	Tree
정의	Node 와 그 Node 를 연결하는 Edge 를 하나로 모아놓은 자료구조	그래프의 한 종류, DAG(Directed Acyclic Graph, 방향성이 있는 비 순환 그래프) 의 한 종류
방향성	방향 그래프 (Directed), 무방향 그래프 (Undirected) 모두 존재	방향 그래프 (Directed Graph)
사이클	사이클(Cycle) 가능, 자체 간선(Self-loop) 가능, 순환 그래프 (Cycle) / 비 순환 그래프(Acyclic) 모두 존재	사이클(Cycle) 불가능, 자체 간선(Self-loop) 불가능, 비 순환 그래프(Acyclic) 만 존재
루트 노드	루트 노드의 개념이 없음	한개의 루트 노드만이 존재, 모든 자식 노드는 한개의 부모 노드만을 가짐
부모-자식	부모-자식 개념이 없음	부모-자식 관계 top-bottom / bottom-top 으로 이루어짐
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS 안의 pre-, in-, post-order
간선의 수	그래프에 따라 간선의 수가 다름, 간선이 없을 수도 있음	노드가 N인 트리는 항상 N-1 의 간선을 가짐
경로	-	임의의 두 노드 간의 경로는 유일