그래프(Graph)

그래프(Graph)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 트리(Tree)와 같이 비선형 구조를 가지는 자료구조이다. 대표적인 예로는 지도가 있다.

그래프는 정점(Vertex)과 간선(Edge)들의 집합으로 구성된다. 수학적으로는 G = (V, E)로 표시한다. 정점(Vertex)는 여러 가지 특성을 가질 수 있는 객체를 의미하고, 간선(Edge)는 이러한 정점들 간의 관계를 의미한다. 정점은 노드라고도 불리며, 간선은 링크라고도 불린다.

그래프는 간선의 종류에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 구분된다. 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈수 있음을 나타내며 정점 A, B를 연결한 간서은 (A, B)로 표현한다. 방향 그래프는 간선에 방향성이 존재하는 그래프로서 한쪽 방향으로만 갈 수 있음을 나타내며 <A, B>로 표시한다.

​그래프의 간선에 방향뿐만 아니라 가중치를 할당하게 되면 훨씬 복잡한 관계를 표현할 수 있다. 이러한 그래프를 가중치 그래프(Weighted Graph) 또는 네트워크(Network)라고 부른다.

 

그래프에서 인접 정점(Adjacent Vertex)이란 간선에 의해 직접 연결된 정점을 뜻한다. 그래프 G1에서 정점 1의 인접 정점은 2, 3이다. 무방향 그래프에서 정점의 차수(Degree)는 하나의 정점에 인접한 정점의 수를 말한다. 정점 1의 차수는 2이다. 무방향 그래프에 존재하는 정점의 모든 차수를 합하면 그래프의 간선 수의 2개가 된다.

방향 그래프에서는 외부에서 오는 간선의 수를 진입 차수(In-Degree)라 하고 외부로 향하는 간선의 수를 진출 차수(Out-Degree)라 한다. 그래프 G2에서 정점 2의 진입 차수는 1이고 진출 차수는 2이다.

그래프를 표현하는 방법은 2차원 배열을 사용하는 인접 행렬(Adjacency Matrix)과 연결 리스트를 사용하는 인접 리스트(Adjacency List)의 두 가지 방법이 있다.

인접 행렬로 구현한 무방향 그래프는 다음과 같이 표현한다.

 

N개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 N^2개의 메모리 공간이 필요하다. 이에 따라 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)를 표현하는 경우에 적합하나, 간선이 적게 존재하는 희소 그래프(Sparse Graph)에는 적합하지 않다.

​인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 O(1)이라는 시간 안에 알 수 있는 장점이 있다. 또한, 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 O(N)의 연산에 의해 알 수 있다.

반면, 그래프에 존재하는 모든 간선의 수를 알기 위해선 인접 행렬 전체를 조사해야하기 때문에 O(N^2)의 시간이 요구된다.

인접 행렬 그래프를 JAVA로 간단하게 구현한 코드이다.

class MyGraph {
	int vertexCnt;
	int[][] m;
	
	public MyGraph(int N) {
		vertexCnt = N;
		m = new int[N][N];
	}
	
	public void make_UndirectedEdge(int from, int to) {
		m[from][to] = 1;
		m[to][from] = 1;
	}
	
	public void make_DirectedEdge(int from, int to) {
		m[from][to] = 1;
	}
	
	public int getInDegree(int v) {
		int cnt = 0;
		for (int i = 0; i < vertexCnt; ++i) {
			cnt += m[i][v];
		}
		return cnt;
	}
	
	public int getOutDegree(int v) {
		int cnt = 0;
		for (int i = 0; i < vertexCnt; ++i) {
			cnt += m[v][i];
		}
		return cnt;
	}
	
	public void print_allEdge() {
		for (int i = 0; i < vertexCnt; ++i) {
			for (int j = 0; j < vertexCnt; ++j) {
				System.out.print(m[i][j] + " ");
			}System.out.println();
		}
	}
}

public class Blog {

	public static void main(String[] args) {
		MyGraph mg = new MyGraph(4);
		System.out.println("무방향 그래프 mg");
		mg.make_UndirectedEdge(0, 1);
		mg.make_UndirectedEdge(0, 2);
		mg.make_UndirectedEdge(1, 2);
		mg.make_UndirectedEdge(1, 3);
		mg.make_UndirectedEdge(2, 3);
		System.out.println("Vertex 1의 진입 차수 : " + mg.getInDegree(1));
		System.out.println("Vertex 3의 진출 차수 : " + mg.getOutDegree(3));
		mg.print_allEdge();

		System.out.println("방향 그래프 mg2");
		MyGraph mg2 = new MyGraph(4);
		mg2.make_DirectedEdge(0, 1);
		mg2.make_DirectedEdge(0, 2);
		mg2.make_DirectedEdge(1, 2);
		mg2.make_DirectedEdge(1, 3);
		mg2.make_DirectedEdge(2, 3);
		System.out.println("Vertex 1의 진입 차수 : " + mg2.getInDegree(1));
		System.out.println("Vertex 3의 진출 차수 : " + mg2.getOutDegree(3));
		mg2.print_allEdge();
	}
}

 

인접 리스트로 구현한 무방향 그래프는 다음과 같이 표현한다.

정점의 수가 N개이고 간선의 수가 E개인 무방향 그래프를 표시하기 위해서는 N개의 연결 리스트가 필요하고, 2E개의 노드가 필요하다. 따라서 인접 리스트 표현은 간선의 개수가 적은 희소 그래프의 표현에 적합하다.

그래프에 간선 (i, j)의 존재 여부나 정점 i의 차수를 알기 위해서는 인접 리스트에서의 정점 i의 연결 리스트를 탐색해야 하므로 연결 리스트에 있는 노드의 수만큼, 즉 정점 차수만큼의 시간이 필요하다. N개 정점과 E개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 모든 인접 리스트를 조사해야 하므로 O(N+E)의 연산이 요구된다.

​따라서 상황에 맞게 인접 행렬, 연결 리스트로 구현한 그래프를 사용해야 한다.

​연결 리스트 그래프를 JAVA로 간단하게 구현한 코드이다.

import java.util.ArrayList;

class MyGraph {
	int vertexCnt;
	ArrayList<Integer>[] edgeList;
	
	public MyGraph(int N) {
		vertexCnt = N;
		edgeList = new ArrayList[N];
		for (int i = 0; i < N; ++i) {
			edgeList[i] = new ArrayList<>();
		}
	}
	
	public void make_UndirectedEdge(int from, int to) {
		edgeList[from].add(to);
		edgeList[to].add(from);
	}
	
	public void make_DirectedEdge(int from, int to) {
		edgeList[from].add(to);
	}
	
	public int getInDegree(int v) {
		int cnt = 0;
		for (int i = 0; i < vertexCnt; ++i) {
			for (int j = 0; j < edgeList[i].size(); ++j) {
				if (edgeList[i].get(j) == v) cnt++;
			}
		}
		return cnt;
	}
	
	public int getOutDegree(int v) {
		return edgeList[v].size();
	}
	
	public void print_allEdge() {
		for (int i = 0; i < vertexCnt; ++i) {
			System.out.print("Vertex " + i + " : ");
			for (int j = 0; j < edgeList[i].size(); ++j) {
				System.out.print(edgeList[i].get(j) + " ");
			}System.out.println();
		}
	}
}

public class Blog {

	public static void main(String[] args) {
		MyGraph mg = new MyGraph(4);
		System.out.println("무방향 그래프 mg");
		mg.make_UndirectedEdge(0, 1);
		mg.make_UndirectedEdge(0, 2);
		mg.make_UndirectedEdge(1, 2);
		mg.make_UndirectedEdge(1, 3);
		mg.make_UndirectedEdge(2, 3);
		System.out.println("Vertex 1의 진입 차수 : " + mg.getInDegree(1));
		System.out.println("Vertex 3의 진출 차수 : " + mg.getOutDegree(3));
		mg.print_allEdge();

		System.out.println("방향 그래프 mg2");
		MyGraph mg2 = new MyGraph(4);
		mg2.make_DirectedEdge(0, 1);
		mg2.make_DirectedEdge(0, 2);
		mg2.make_DirectedEdge(1, 2);
		mg2.make_DirectedEdge(1, 3);
		mg2.make_DirectedEdge(2, 3);
		System.out.println("Vertex 1의 진입 차수 : " + mg2.getInDegree(1));
		System.out.println("Vertex 3의 진출 차수 : " + mg2.getOutDegree(3));
		mg2.print_allEdge();
	}
}