그래프(Graph)

: 그래프(Graph)는 정점(Node 혹은 Vertex)과 간선(Edge 혹은 Branch)로 이루어져 있으며 간선은 정점과의 관계를 나타내는데 사용한다. G = (V, E)와 같이 나타낸다.

 

그래프의 종류

• 무방향 그래프 : 간선을 통해 양방향으로 이동할 수 있는 그래프로, G(A, B) = G(B, A)
• 방향 그래프 : 간선에 방향이 존재하는 그래프로, G(A, B) ≠ G(B, A)
• 가중치 그래프 : 간선에 비용 또는 가중치가 할당된 그래프
• 연결 그래프 : 무방향 그래프에서 모든 정점쌍들에 대해 항상 경로가 존재하는 그래프
• 비연결 그래프 : 무방향 그래프에서 특정 정점쌍들에 경로가 존재하지 않는 그래프
• 순환 그래프 : 단순 경로의 시작 정점과 종료 종점이 동일한 경우
• 비순환 그래프 : 순환이 없는 그래프

 

그래프 구현

 

그림 1. 그래프

위의 그림과 같은 그래프를 구현하는 대표적인 방법으로는 인접 행렬을 이용한 구현과 인접 리스트를 이용한 구현이 있다.

 

인접 행렬을 이용한 구현

그림 1을 행렬과 같이 표현하면 아래의 그림과 같다. 이 방법에서는 2차원 배열을 선언하여 그래프를 구현한다.

그림 2. 행렬

class Graph {
	
	private int[][] graph;
	
	public Graph(int nV) {
		
		this.graph = new int[nV + 1][nV + 1];
		// 보통 그래프의 정점들은 1부터 n까지이기 때문에 (nV + 1) x (nV + 1) 크기의 행렬로 선언해준다.
		
	}
	
	public int[][] getGraph() {
		
		return this.graph;
		
	}
	
	public void put(int x, int y) {
		
		graph[x][y] = graph[y][x] = 1;
		// 양방향 그래프
		
	}
	
	public void putSingle(int x, int y) {
		
		graph[x][y] = 1;
		// 단방향 그래프
		
	}
	
	public void printGraph() {
		
		for(int i = 1; i < graph.length; i++) {
			for(int j = 1; j < graph.length; j++)
				System.out.print(graph[i][j] + " ");
			System.out.println();
		}
	}
	
}

public class AdjacencyMatrixGraph {
	
	public static void main(String[] args) {
    
		Graph matrixGraph = new Graph(6);
		
		matrixGraph.put(1, 2);
		matrixGraph.put(1, 3);
		matrixGraph.put(2, 3);
		matrixGraph.put(2, 4);
		matrixGraph.put(3, 4);
		matrixGraph.put(3, 5);
		matrixGraph.put(4, 5);
		matrixGraph.put(4, 6);
		// 양방향 그래프이므로, put(4, 6)을 하면 put(6, 4)와 같다.
		
		matrixGraph.printGraph();
		
	}

}

 

출력 화면

 

인접 리스트를 이용한 구현

그림 1을 연결 리스트와 같이 표현하면 아래의 그림과 같다. 이 방법에서는 ArrayList<ArrayList<Integer>>를 통해 그래프를 구현한다.

그림 3. 연결리스트

import java.util.ArrayList;

class Graph {
	
	private ArrayList<ArrayList<Integer>> graph;
	
	public Graph(int nV) {
		
		this.graph = new ArrayList<ArrayList<Integer>>();
		
		for(int i = 1; i <= nV + 1; i++)
		// 보통 그래프의 정점들은 1부터 n까지이기 때문에 i는 0부터 nV + 1까지로 설정한다.
			this.graph.add(new ArrayList<Integer>());
		
	}
	
	public ArrayList<ArrayList<Integer>> getGraph() {
		
		return this.graph;
		
	}
	
	public void put(int x, int y) {
		
		this.graph.get(x).add(y);
		this.graph.get(y).add(x);
		// 양방향 그래프
		
	}
	
	public void putSingle(int x, int y) {
		
		this.graph.get(x).add(y);
		// 단방향 그래프
		
	}
	
	public void printGraph() {
		
		for(int i = 1; i < this.graph.size(); i++) {
			System.out.print(i);
			for(int j = 0; j < this.graph.get(i).size(); j++)
				System.out.print(" -> " + this.graph.get(i).get(j));
			System.out.println();
		}
	}
	
}

public class AdjacencyListGraph  {
	
	public static void main(String[] args) {
    
		Graph listGraph = new Graph(6);
		
		listGraph.put(1, 2);
		listGraph.put(1, 3);
		listGraph.put(2, 3);
		listGraph.put(2, 4);
		listGraph.put(3, 4);
		listGraph.put(3, 5);
		listGraph.put(4, 5);
		listGraph.put(4, 6);
		
		listGraph.printGraph();
		
	}

}

 

출력 화면

 

---

 

그래프 참고 사이트

• https://freestrokes.tistory.com/87