그래프(Graph)란?

그래프(Graph)란, 다음의 2가지 요소로 구성된 자료구조이다.

1. vertex(혹은 node)의 집합

2. vertex 쌍을 잇는 각 edge(간선)들의 모음

그래프에 V개의 vertex가 있을 때, 각 vertex는 0부터 V-1까지의 숫자로 이름 붙인다. 

각 vertex를 잇는 edge는 v-w 혹은 (v,w)와 같이 표현한다.

         

그래프는 단지 vertex들의 집합과 edge들의 모음일 뿐이라는 것을 기억한다면, 위의 두 그래프는 완전히 동일하다는 것을 알 수 있을 것이다.

그래프 개념은 실생활의 많은 곳에서 사용되는데, 지도, 웹 상의 링크, 전자회로, 스케줄링, 전자상거래, 매칭, 컴퓨터 네트워크, 소셜 네트워크 등에 폭넓게 적용된다. 적용 분야에 대한 자세한 내용은 여기를 참고하자.

---

그래프를 표현하는 방법에는 여러가지가 있을 수 있는데, 어떤 방식을 사용하든 다음의 사항들을 고려해야 할 것이다.

✔︎ 실제 응용 상황에서, 그래프 타입을 수용할 수 있는 적당한 공간(space)

✔︎ 그래프를 처리하는 데 있어 시간적으로 효율적(time-efficient)인 구현 방법

위의 사항들을 고려해서, 다음 3가지의 그래프 표현법에 대해 알아보자.

   1. 인접 행렬(adjacency matrix)

    •  V Graph(vertex가 V개인 그래프)라면, V x V의 boolean 배열을 사용하는 것이다. 만약 v와 w 모두를 잇는 edge가 존재한다면(단, undirected graph인 경우), 행렬에서 (v,w)와 (w,v) 모두 true가 되고, 반대의 경우 false가 된다.

    •  weighted graph(가중 그래프)를 표현할 때 사용되기도 한다. 만약 adj[i][j] = 3이라면, i에서 j로 가는 weight가 3인 edge가 존재한다는 뜻이다.

장점:  구현이 쉽다. edge를 제거하거나, 한 vertex에서 다른 vertex로 가는 edge가 존재하는지 알아내는 연산을 수행하는 데 O(1)의 시간이 걸린다. 

단점:  위의 고려사항 중 첫번째를 만족하지 못한다. 세상에는 vertex가 수백만 개인 그래프도 존재하는데 이 경우 행렬의 크기가 너무 커진다. 또한 edge가 많든 적든 무조건 V^2에 비례하는 공간이 필요하므로 비효율적이다. 즉 그래프가 sparse하든 dense하든 공간 복잡도 측면에서 언제나 좋지 못하다.

   2. edge들의 배열

    •  이를테면 한 쌍을 이루는 vertex들을 2개의 int로 표현해 Edge라는 클래스를 만들고, Edge들을 배열에 담는 방식이다.

    •  이 방법은 두번째 고려사항을 만족하지 못한다. 어떤 vertex와 인접한 vertex들을 구하려면 배열의 모든 요소들을 다 찾아봐야 하기 때문이다. 즉 시간 복잡도가 크다.

   3. 인접 리스트(adjacency list)의 배열

    •  각 vertex들을 index로 하는 배열을 만들고, 각 배열 안에는 해당 vertex와 인접한 vertex들을 List 형태로 넣어 놓는 방식이다. 아래 그림을 참고하자.

    •  이 방법은 대부분의 경우에 시간, 공간적인 요구사항을 모두 만족한다.

    •  단, 한 vertex에서 다른 vertex로 가는 edge가 존재하는지 알아내는 연산을 수행하는 데 O(V)의 시간이 걸리므로, 이 부분은 인접 행렬에 비해 느릴 수 있다.

    •  특히 sparse(not dense)한 그래프의 경우, 이 방법이 표준적인 자료구조라고 할 수 있다.

다음은 vertex와 edge의 개수, 각 edge들을 입력 받은 후, 각 vertex마다 인접한 vertex들을 출력하는 코드다. (geeksforgeeks를 참고함)

	package geeksforgeeks;
	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	/**
	* https://practice.geeksforgeeks.org/problems/print-adjacency-list/0
	*/
	public class PrintAdjacencyList {
	static class Graph {
	ArrayList[] array; // array of ArrayList (LinkedList is also possible)
	int v; // the number of vertices
	Graph(int v) {
	this.v = v;
	array = new ArrayList[v];
	// Add linkedList to array
	for (int i = 0; i < v; i++) {
	array[i] = new ArrayList<>();
	}
	}
	}
	private static void addEdge(Graph graph, int source, int target) {
	if (!graph.array[target].contains(source)) {
	graph.array[target].add(source);
	}
	if (!graph.array[source].contains(target)) {
	graph.array[source].add(target);
	}
	}
	private static void printGraph(Graph graph) {
	System.out.println();
	int length = graph.array.length;
	for (int i = 0; i < length; i++) {
	System.out.print(i + "-> ");
	ArrayList list = graph.array[i];
	int size = list.size();
	for (int j = 0; j < size - 1; j++) {
	System.out.print(list.get(j) + "-> ");
	}
	System.out.println(list.get(size - 1));
	}
	System.out.println();
	}
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int t = Integer.parseInt(br.readLine().split(" ")[0]);
	for (int i = 0; i < t; i++) {
	String[] ves = br.readLine().split(" ");
	int v = Integer.parseInt(ves[0]);
	int e = Integer.parseInt(ves[1]);
	Graph graph = new Graph(v);
	for (int j = 0; j < e; j++) {
	String[] vertices = br.readLine().split(" ");
	int source = Integer.parseInt(vertices[0]);
	int target = Integer.parseInt(vertices[1]);
	addEdge(graph, source, target);
	}
	printGraph(graph);
	}
	}
	}

view raw PrintAdjacencyList.java hosted with ❤ by GitHub

다음은 파일을 입력 받아 각 vertex마다 인접한 vertex들을 출력한다. (Algorithms by R. Sedgewick을 참고함)

	public class Graph {
	private final int V;
	private int E;
	private Bag<Integer>[] adj;
	public Graph(int V) {
	this.V = V;
	this.E = 0;
	for (int v = 0; v < V; v++)
	adj[v] = new Bag<Integer>();
	}
	public Graph(In in) {
	this(in.readInt());
	int E = in.readInt();
	for (int i = 0; i < E; i++) {
	int v = in.readInt();
	int w = in.readInt();
	addEdge(v, w);
	}
	}
	public int V() {
	return V;
	}
	public int E() {
	return E;
	}
	public void addEdge(int v, int w) {
	adj[v].add(w);
	adj[w].add(v);
	E++;
	}
	public Iterable<Integer> adj(int v) {
	return adj[v];
	}
	public String toString() {
	String s = V + " vertices, " + E + " edges\n";
	for (int v = 0; v < V; v++) {
	s += v + ": ";
	for (int w : this.adj(v))
	s += w + " ";
	s += "\n";
	}
	return s;
	}
	}

view raw Graph.java hosted with ❤ by GitHub