[Java]그래프의 표현

*그래프의 표현

->프로그래밍을 하다보면 그래프를 만들어야 하는 경우가 발생할 수 있는데, 프로그래밍에서 그래프를 표현하는 방법은 크게 2가지(인접 행렬, 인접 리스트)로 나뉜다.

 

->인접 행렬 : 수학에서 행렬은 그래프를 표현하는데 사용되기도 하였다. 따라서 프로그래밍에서 2차원 배열은 행렬의 성질을 갖는다는 점을 활용하여 마찬가지로 그래프를 표현할 수 있다. 기본적으로 인접행렬을 이용한 그래프 표현은 각 인덱스를 정점이라고 생각하고, 정점이 교차하는 지점(좌표)을 연결된 상태라고 표시해주면 된다.

(1) 무향 그래프 : 방향을 가지지 않는 그래프를 말한다. 따라서, 행렬이 대칭적으로 같은 값을 갖는 특징을 갖는다.

무향 그래프와 인접행렬 값

(2) 유향 그래프 : 방향을 가지고 있는 그래프를 말한다. 따라서, 무조건 행렬이 대칭적으로 같은 값을 갖지는 않는다.

유향 그래프와 인접행렬 값

->인접 리스트 : 인접 리스트를 이용하는 방식은 연결 리스트 자료구조를 활용하여 그래프를 표현할 수 있다. 1차원 배열의 각 인덱스를 노드라고 생각하고, 정점의 연결이 있을 때마다 해당 정점에 연결된 노드 정보를 추가해주면 된다. 

(1) 무향 그래프 : 연결된 노드의 정보를 추가할때 각 노드에 대하여 각각 정보를 추가해주면 된다.

무향 그래프와 인접 리스트 값

(2) 유향 그래프 : 연결된 노드의 정보만 추가해주면 된다.

유향 그래프와 인접 리스트 값

 

*장단점

->인접 행렬은 간선의 추가와 삭제가 빈번하게 사용되는 경우, 인접 리스트는 노드의 추가와 삭제가 빈번하게 사용되는 경우 사용하는 것이 좋다.

 

*인접 행렬 구현

->알고리즘 문제에서는 주로 연결되는 두 노드의 정점과 비용으로 그래프의 연결성이 주어지기 때문(노드 노드 비용)에, 그 상황을 가정하여 인접행렬을 구현해보면 다음과 같다. 

import java.util.Scanner;

/*
정점, 간선의 개수 이후
(노드, 노드, 비용)이 주어진 경우
5 6
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
 */

public class Graph {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// V = 정점의 개수, E = 간선의 개수.
		int V = sc.nextInt();
		int E = sc.nextInt();
		
		// 2차원 배열(인접 행렬)을 만든다.
		// 인덱스의 번호 = 노드의 번호 이기 때문에, 2차원 배열의 크기를 임의로 1 늘려서 정의한다(스킬).
		int[][] graph = new int[V + 1][V + 1];
		
		int row;
		int col;
		int cost;
		for(int i = 0; i < E; i++) {
			row = sc.nextInt();
			col = sc.nextInt();
			cost = sc.nextInt();
			graph[row][col] = cost;
			// 만일, 무향 그래프라면 반대의 상황도 추가해 준다.
			// graph[col][row] = cost;
		}
		
		// 인접 행렬 출력
		for(int i = 1; i < V + 1; i++) {
			for(int j = 1; j < V + 1; j++) {
				System.out.print(graph[i][j] + " ");
			}
			System.out.println();
		}
		sc.close();
	}
}

유향 그래프

무향 그래프(대칭성을 확인할 수 있다)

 

*인접 리스트 구현

->알고리즘 문제에서는주로 연결되는 두 노드의 정점과 비용으로 그래프의 연결성이 주어지기 때문(노드 노드 비용)에, 마찬가지로 그 상황을 가정하여 인접 리스트를 구해보면 다음과 같다.

->자바의 경우, 리스트 안에 자유롭게 노드를 추가 가능한 리스트를 추가할 수 있어야 하기 때문에 List 내부에 동적 리스트를 선언하여 처리해준다. 또한, 그 안에 대상 노드와 비용을 리스트처럼 처리하는 경우가 많기 때문에, Node라는 클래스(객체)를 따로 선언해주어 처리해주는 것이 깔끔하다.

package Graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/*
정점, 간선의 개수 이후
(노드, 노드, 비용)이 주어진 경우
5 6
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
 */

public class Graph {
	// 노드와 비용을 포함하는 객체를 미리 만들어준다.
	static public class Node {
		// 연결되는 정점
		int end;
		// 비용
		int cost;

		Node(int end, int cost) {
			this.end = end;
			this.cost = cost;
		}

		@Override
		public String toString() {
			return "[" + end + ", "
					+ "" + cost + "]";
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// V = 정점의 개수, E = 간선의 개수.
		int V = sc.nextInt();
		int E = sc.nextInt();
		
		// 1차원 리스트를 만든다.
		// 인덱스의 번호 = 노드의 번호 이기 때문에, 1차원 리스트의 크기를 임의로 1 늘려서 정의한다(스킬).
		List<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
		for (int i = 0; i < V + 1; i++) {
			graph.add(new ArrayList<Node>());
		}

		int a;
		int b;
		int cost;
		for (int i = 0; i < E; i++) {
			a = sc.nextInt();
			b = sc.nextInt();
			cost = sc.nextInt();
			
			graph.get(a).add(new Node(b, cost));
			// 만일, 무향 그래프라면 반대의 상황도 추가해 준다.
			// graph.get(b).add(new Node(a, cost));
		}

		// 인접 행렬 출력
		System.out.println(graph);
		sc.close();
	}
}

유향 그래프 

무향 그래프

->유향 그래프의 1번째 인덱스(1번 노드)의 1번째 인덱스(첫 번째 대상 노드)는 2번 노드로 가는데 비용이 2가 든다는 의미, 2번째 인덱스(두 번째 대상 노드)는 3번 노드로 가는데 비용이 3이 든다는 의미이다. 적절히 잘 구현된 것을 확인할 수 있다.

->각 인덱스 내부의 대상 노드 값을 오름차순으로 정렬하면 더 깔끔하게 표현가능하지만, 큰 상관은 없다.