[알고리즘][Graph] 그래프(Graph)의 개념과 표현

학습목표
1. (무방향) 그래프에 대해서 학습
2. 방향 그래프와 가중치 그래프에 대해서 학습
3. 그래프를 표현하기 위한 방법인 인접행렬과 인접리스트에 대해서 학습
4. 무방향 그래프에서 경로와 연결성에 대해서 학습

 

1. (무방향) 그래프란 무엇인가?

각각의 노드들을 링크로 연결한 집합입니다. 이때 무방향이라는 것은 정점과 정점 사이가 연결된 링크가 존재하면 방향성이 없다는 의미입니다. 그래프에서 데이터를 담고 있는 것을 노드(Node) 또는 정점(Vertex)이라고 부릅니다. 그리고 2개 이상의 정점들을 연결하는 링크를 에지(Edge) 혹은 링크(Link)라고 부릅니다.

V={1,2,3,4,5,6,7,8}
E={(1,2),(1,3),(2,3), ... , (7,8)}
n=|V|=8 (정점의 개수)
m=|E|=11 (에지의 개수)

 

2. 방향그래프와 가중치 그래프

방향그래프는 정점과 정점 사이에 링크가 방향성을 가지는 그래프입니다. 예를 들어 에지 (u,v)의 의미는 u로부터 v로의 방향성을 가진다는 의미입니다.

 

가중치 그래프는 에지마다 가중치(weight)를 가지는 그래프입니다. 아래의 그림은 방향성 그래프와 가중치 그래프를 같이 표현한 그래프입니다.

 

3. 그래프의 표현 : 인접 행렬(adjacency matrix)

정점들과 에지들을 표현하기 위해서 인접 행렬로 표현할 수 있습니다. 인접행렬은 2차원 배열기반으로 구현됩니다. 아래 그림에서 nxn 크기의 행렬 A가 존재한다고 했을때 정점 i와 정점 j가 링크로 연결되어 있다면 값을 1로 설정하고 링크로 연결되어 있지 않으면 0으로 설정하면 됩니다.

인접행렬의 공간 및 시간 복잡도는 다음과 같습니다.

• 저장 공간 : O(n²)
• 어떤 노드 v에 인접(연결된)한 모든 노드 탐색 : O(n) 시간
• 어떤 에지 (u,v)가 존재하는지 검사 : O(1) 시간

저장공간이 O(n²)이 나온 이유는 인접행렬이 2차원배열 기반이기 때문입니다. 따라서 n*n크기가 필요하므로 O(n²)의 저장공간이 필요합니다. 

 

어떤 노드 v에 인접한 모든 노드를 탐색하기 위해서는 한 행(row)을 순회하여 1인 값을 검사하면 됩니다. 행의 크기는 n이므로 O(n)시간이 걸리게 됩니다.

 

어떤 에지 (u,v)가 존재하는 검사한다는 의미는 두 정점사이에 연결이 있는지 검사한다는 의미입니다. 2차원 배열 기반이기 때문에 matrix[u][v]와 같은 방법으로 임의 접근할 수 있기 때문에 O(1) 시간이 소요됩니다.

 

4. 그래프의 표현 : 인접 리스트(adacency list)

인접리스트는 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결 리스트로 그래프를 표현하는 방법입니다. 아래의 그림은 한 무방향 그래프에 따른 인접리스트를 표현한 것입니다.

위의 그림에서 정점의 개수는 5개이고 에지의 개수는 7개입니다. 하나의 배열에는 각각의 정점들이 들어있고 각각의 정점들에는 연결리스트로 해당 정점과 연결된 노드들이 추가되어 있습니다. 추가된 노드들의 순서는 상관이 없습니다.

 

연결리스트에 연결된 노드들의 개수를 구하고 싶다면 2*m(에지의 개수)하여 구할 수 있습니다. 위의 그림에서는 에지의 개수가 7개이므로 연결리스트의 추가된 노드들의 개수는 2*7=14개임을 알 수 있습니다.

 

최대 가질 수 있는 에지의 개수

• (n(n-1))/2
• n은 정점의 개수를 의미합니다. 위의 그림을 예시로 하여 정점 1은 4개의 정점들(2,3,4,5)과 연결될 수 있습니다. 이는 n-1개임을 의미합니다.
• n개의 정점들이 n-1개의 에지를 가질 수 있으므로 n(n-1)개의 에지를 가질 수 있고 위의 예시에서는 무방향 그래프이므로 중복이 되므로 나누기 2를 통하여 최대 가질 수 있는 에지의 개수를 구할 수 있습니다.

 

인접리스트의 공간 및 시간 복잡도는 다음과 같습니다.

• 저장 공간 : O(n+2m) = O(n+m)
• 어떤 노드 v에 인접(연결된)한 모든 노드 탐색 : O(degree(v)) 시간
• 어떤 에지 (u,v)가 존재하는지 검사 : O(degree(u)) 시간

저장공간은 하나의 배열에 n개의 정점들이 저장되고 2m개의 노드들이 연결리스트에 추가되므로 O(n+2m)이지만 상수는 제거되므로 O(n+m)과 같이 표현할 수 있습니다.

 

어떤 노드 v에 인접한 모든 노드를 탐색한다면 v와 연결된 연결리스트의 모든 노드들을 탐색하면 됩니다. 이때 degree(v)의 의미는 v와 연결된 정점들의 개수를 의미합니다. 즉, 어떤 노드 v에 인접한 모든 노드를 탐색하는데 걸리는 시간은 v와 연결된 노드들의 개수만큼 소요됩니다.

 

어떤 에지 (u,v)가 존재하는지 검사하는데 소요되는 시간은 u와 연결된 연결리스트의 모든 노드의 개수만큼 소요됩니다.

 

5. 방향 그래프의 인접행렬, 인접리스트

방향 그래프를 인접행렬 기반으로 표현할 수 있습니다. 하지만 무방향 그래프와는 다르게 방향 그래프의 인접행렬은 비대칭하다는 점입니다.

 

방향 그래프의 인접리스트 기반으로도 표현할 수 있습니다. 이때 그래프에 방향이 있으므로 인접리스트는 m개의 노드를 가질 수 있다 말할 수 있습니다.

 

6. 가중치 그래프의 인접행렬 표현

가중치 그래프를 인접행렬로 표현하였을 때 에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장합니다.

 

에지가 없을때는 0을 넣습니다. 만약 가중치가 0인 경우를 대비하여 ∞를 넣기도 합니다.

7. 무방향 그래프의 경로와 연결성

무방향 그래프 G=(V,E)에서 노드 u와 노드 v를 연결하는 경로(path)가 존재할 때 v와 u는 서로 연결되어 있다고 말할 수 있습니다. 예를 들어 아래 그림에서 정점 4에서 정점 3까지 에지를 통해서 갈 수 있으므로 정점 4와 정점 3은 연결되어 있다고 말 할 수 있습니다.

 

그리고 모든 정점 쌍들이 서로 연결된 그래프를 연결된(connected) 그래프라고 합니다. 아래 그림에서는 연결 요소(connected component)가 3개의 연결된 그래프가 존재하는 것을 알 수 있습니다.

 

8. 무방향 그래프 구현

아래의 소스코드는 인접리스트 기반의 무방향 그래프 구현입니다.

import java.util.ArrayList;


// 인접리스트 기반 무방향 그래프
public class UndirectedGraph implements Graph{
	private int V;	// 노드들의 번호
	private ArrayList<ArrayList<Integer>> adj;	// 인접리스트
	
	public UndirectedGraph(int v) {
		V = v;
		adj = new ArrayList<ArrayList<Integer>>(v);
		
		for(int i=0;i<v;i++)
		{
			adj.add(new ArrayList<Integer>());
		}
		
	}
	
	@Override
	public void addEdge(int u, int v) {
		adj.get(u).add(v);
		adj.get(v).add(u);
	}
	
	@Override
	public void printGraph()
	{
		for(int i=0;i<adj.size();i++)
		{
			System.out.printf("노드 %d의 인접리스트\n", i);
			System.out.print("head");
			for(int j=0; j<adj.get(i).size();j++)
			{
				System.out.print("->"+adj.get(i).get(j));
			}
			System.out.printf("\n\n");
		}
	}
	
	public static void main(String[] args)
	{
		int V = 9;
		UndirectedGraph undirectedGraph = new UndirectedGraph(V);
		
		undirectedGraph.addEdge(1,2);
		undirectedGraph.addEdge(1,3);
		undirectedGraph.addEdge(2,3);
		undirectedGraph.addEdge(2,4);
		undirectedGraph.addEdge(2,5);
		undirectedGraph.addEdge(3,5);
		undirectedGraph.addEdge(3,7);
		undirectedGraph.addEdge(3,8);
		undirectedGraph.addEdge(4,5);
		undirectedGraph.addEdge(5,6);
				
		undirectedGraph.printGraph();
	}
}

노드 0의 인접리스트
head

노드 1의 인접리스트
head->2->3

노드 2의 인접리스트
head->1->3->4->5

노드 3의 인접리스트
head->1->2->5->7->8

노드 4의 인접리스트
head->2->5

노드 5의 인접리스트
head->2->3->4->6

노드 6의 인접리스트
head->5

노드 7의 인접리스트
head->3

노드 8의 인접리스트
head->3

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/graph/graph01_representations
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌