[자료구조] 그래프(Graph)

그래프(Graph)

선형 자료구조나 트리 자료구조로 표현하기 어려운 관계를 가지는 원소들을 표현하기 위한 자료구조

그래프 G는 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다.

• V는 그래프에 있는 정점들의 집합
• E는 정점을 연결하는 간선들의 집합

무방향 그래프(Undirected Graph)

두 정점을 연결하는 간선의 방향이 없는 그래프이다.

정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현한다.

이때 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 의미한다.

위의 그래프를 집합으로 표현하면 다음과 같다.

V(G1) = {A, B, C, D}	E(G1) = {(A,B), (A,D), (B,C), (B,D), (C,D)}
V(G2) = {A, B, C}	V(G2) = {(A,B), (A,C), (B,C)}

 

방향 그래프(Directed Graph)

간선이 방향을 가지고 있는 그래프이다.

Vi와 Vj를 연결하는 간선 Vi -> Vj를 <Vi, Vj>로 표현한다.

이때 Vi를 꼬리(tail), Vj를 머리(head)라고 한다.

즉, <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선을 의미한다.

위의 그래프를 집합으로 표현하면 다음과 같다.

V(G3) = {A, B, C, D}	E(G3) = {<A,B>, <A,D>, <B,C>, <B,D>, <C,D>}
V(G3) = {A, B, C}	V(G2) = {<A,B>, <A,C>, <B,A>, <B,C>}

 

그래프의 제한 사항

• 자기 간선(self edge) 또는 자기 루프(self loop)가 없다.
• 동일 간선의 중복이 없다. (다중 그래프(multigraph)는 이 제한이 없음)

완전 그래프(Complete Graph)

각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프

• 정점이 n개인 무방향 그래프에서 최대 간선의 수: nC2개
• 정점이 n개인 방향 그래프의 최대 간선의 수: nP2개

부분 그래프(Subgraph)

원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프이다.

가중 그래프(Weight Graph)

정점을 연결하는 간선에 가중치(weight)를 할당한 그래프이다.

인접 행렬(Adjacency Matrix)

G = (V, E)를 정점의 수가 n(n>=1)인 그래프라 하자. G의 인접 행렬은 nXn의 2차원 배열로서, 이를 a라고 할 때 간선 (i, j)가 E(G)에 속하면 a[i][j] = 1이고 속하지 않으면 a[i][j]인 성질을 가지고 있다.

 

• 무방향 그래프: 어떤 정점 i의 차수는 그 행렬 또는 열의 합
• 방향 그래프: 행의 합은 진출차수, 열의 합은 진입차수
• 인접행렬의 수행시간: 최소한 O(n^2)
• 희소 그래프(sparse graph): O(e+n)

 

<단점>

• n개의 정점을 가지는 그래프를 항상 n X n 개의 메모리 사용한다.
• 정점의 개수에 비해서 간선의 개수가 적은 희소 그래프에 대한 인접 행렬은 희소 행렬이 되므로 메모리의 낭비가 발생한다.

인접 리스트(Adjacency List)

각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트이다.

임의의 정점에 대한 인접 리스트를 O(1) 시간에 접근할 수 있도록 배열 adjLists가 사용되었다.

연결 인접 리스트로 표현된 무방향 그래프에 대한 클래스라면, adLists는 이 클래스의 전용 데이타 멤버이고, 클래스 생성자는 다음과 같다.

Chain<int> *adjLists;
LinkedGraph(const int vertice = 0): n(vertices), e(0)
	{adjLists = new Chain<int>[n];}

 

n개의 정점, e개의 간선을 가진 무방향 그래프의 인접 리스트

• 헤드 노드 배열의 크기: n
• 연결하는 노드의 수: 2e
• 각 정점의 헤드에 연결된 노드의 수: 정점의 차수

 

n개의 정점, e개의 간선을 가진 방향 그래프의 인접 리스트

• 헤드 노드 배열의 크기: n
• 연결하는 노드의 수: e
• 각 정점의 헤드에 연결된 노드의 수: 정점의 진출 차수
• 진입 차수? -> 역인접리스트