[자료구조] Graph 기본 개념 및 구현

트리와 그래프

그래프를 설명하기 이전에, 트리가 빠질 수 없습니다.

그래프는 겉보기에 트리와 상당히 유사하지만, 더 다양한 표현 방법으로 인해 기능이 많아지고, 그럼으로써 어려워졌다고 볼 수 있습니다.

이번 포스트에서는 트리 자체에 대한 내용을 따로 다루지 않을 것이고, 필요하시다면 이전글을 참조해주세요.

 

차이

• Tree
  
  1. 무조건적으로 부모-형제 관계와 같이 상-하 구조로 연결되어 있다.
  2. 위에서 아래로 방향성을 갖고 있다.
  3. 계층 모델을 사용

• Graph
  1. 부모-형제 개념이 없다.
  2. 방향성에 대한 제약이 없다(양방향, 단방향).
  3. 연결 상태를 필수적으로 갖지 않아도 된다.
  4. 네트워크형 모델을 사용한다.

 

추가 용어

• 방향 그래프 : 간선의 방향이 존재하는 그래프. 무방향 그래프에서는 양방향으로 이동이 가능.
• 연결 그래프 : 두개 이상의 정점이 연결되어 있는 그래프
• 사이클 그래프 : 특정 노드의 경로가 시작-종료지점이 동일한 그래프
• 완전 그래프 : 그래프 내 모든 정점이 서로 연결되어 있는 그래프

 

사용도

• 지하철 목적지 최단거리 알고리즘
• DFS
• BFS

구현 방법

인접한 노드를 리스트 형태로 나타내는 방법, 행렬로 나타내는 방법 두 가지가 있습니다.

다음 그림은 아까 전, 그래프에 대한 예시로 보여드렸던 내용이며, 이를 토대로 나타내보도록 하겠습니다.

• Adjacency List

그래프의 연결 상태를 리스트에 담는 형태

• Adjacency Matrix

그래프의 연결 상태를 행렬로 나타내는 형식

DFS(Depth First Search, 깊이 우선 탐색)

그래프를 다룰 경우, 빠질 수 없는 알고리즘입니다

DFS는 한 마디로, 노드를 순서대로 탐색하되, 더 깊은 내용(연결된 다른 내용)이 존재한다면, 존재하지 않을 때까지 들어간 후 다음 노드를 탐색하는 방법입니다.

그래프 탐색에서는 어떤 노드가 거쳐갈 때, 그에 대한 플래그를 체크하는 것이 굉장히 중요합니다. 이미 방문한 노드인 경우, 다시 해당 노드에서 작업을 할 필요가 없기 때문이죠.

따라서, DFS 방법은 하나의 기준 노드에서 방문 여부를 체크하고, 연결된 노드가 있을 때 재귀적으로 연결 노드가 없을 때까지 파악하는 프로세스를 가지고 있습니다.

 

public void dfs(Node node) {
	System.out.println(node.data + " ");
	node.visited = true;
	Iterator<Node> iter = node.adjacent.iterator();
		
	while(iter.hasNext()) {
		Node adNode = iter.next();
		if(!adNode.visited) {
			dfs(adNode);				
		}			
	}
}

 

구현(Graph)

package Graph;

import java.util.ArrayList;
import java.util.Iterator;

// Adjacency List Graph
public class Graph {
	public class Node {
		private int data;
		private boolean visited;
		private ArrayList<Node> adjacent;
		
		public Node() {
			visited = false;
			adjacent = new ArrayList<Node>();
		}
		
		public Node(int data) {
			this.data = data;
			visited = false;
			adjacent = new ArrayList<Node>();
		}
		
		public int getData() {
			return data;
		}
		
	}
	
	public Graph() {
	}
	
	public Node addNode(int data) {
		Node newNode = new Node(data);
		
		return newNode;
	}
	
	public void addEdge(Node node1, Node node2) {
		node1.adjacent.add(node2);
	}
	
	// 방향 그래프
	public void dfs(Node node) {
		System.out.println(node.data + " ");
		node.visited = true;
		Iterator<Node> iter = node.adjacent.iterator();
		
		while(iter.hasNext()) {
			Node adNode = iter.next();
			if(!adNode.visited) {
				dfs(adNode);				
			}			
		}
	}
}

 

실행

import Graph.Graph;
import Graph.Graph.Node;

public class Run {
	public static void main(String[] args) {
		Graph g = new Graph();
		
		// 노드 생성
		Node node1 = g.addNode(1); Node node2 = g.addNode(2);
		Node node3 = g.addNode(3); Node node4 = g.addNode(4);
		Node node5 = g.addNode(5); Node node6 = g.addNode(6);
		
		// 연결 상태 정의
		g.addEdge(node1, node2);
		g.addEdge(node2, node4);
		g.addEdge(node3, node5);
		g.addEdge(node3, node6);
		g.addEdge(node4, node1);
		g.addEdge(node4, node3);
		g.addEdge(node5, node4);
		
		g.dfs(node1);
	}
}