[JAVA] 그래프 구현하기

그래프란?

그래프는 정점(Vertex)와 간선(Edge)로 구성된 한정된 자료구조를 의미한다.

그래프의 종류

1. 무방향 그래프
간선에 방향이 따로 없다.
2. 방향 그래프
간선에 방향이 있다.
3. 가중치 그래프
간선에 가중치가 존재한다.

무향 그래프 구현방법

1. 인접행렬

2. 인접리스트

1. 인접행렬로 구현하기

2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다.

• 인접행렬은 '연결된 정보' 외에도 모든 관계를 저장한다.
• 특정노드가 다른 특정 노드와 연결되어있는지 여부를 확인하려면 graph[x][y]를 통해 손쉽게 확인할 수 있다.

package Graph;

import java.io.*;
import java.util.*;

public class graph {
	static int graph[][];
	static int N;
	
	public static void putEdge(int x, int y) {
		// 무방향이므로, 양쪽 관계를 생각해주어야 한다.
		graph[x][y] = 1;
		graph[y][x] = 1;
	}
	
	public static void main(String [] args) {
		// 정점의 갯수
		N = 5;
		// 그래프 초기화하기 -> 0번은 사용 X
		graph = new int [N+1][N+1];
		
		putEdge(1, 2);
        putEdge(1, 3);
        putEdge(1, 4);
        putEdge(2, 3);
        putEdge(2, 5);
        putEdge(3, 4);
        putEdge(4, 5);
 
        System.out.println(Arrays.deepToString(graph));
		
	}
}

출력값

[[0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 1, 0], [0, 1, 0, 1, 0, 1], [0, 1, 1, 0, 1, 0], [0, 1, 0, 1, 0, 1], [0, 0, 1, 0, 1, 0]]

2. 인접리스트로 구현하기

해당 노드와 연결되어 있는 노드들을 리스트로 쭉 붙이는 방식이다. ArrayList를 이용하여 구현할 수 있다.

• 인접리스트는 '연결된 정보' 만을 저장한다.
• 특정노드가 다른 특정노드와의 연결여부를 확인할때 속도가 느리다.
  ∵ graph = y 가 나올때 까지 ArrayList를 순회해야하기 때문에..
  

package Graph;
import java.io.*;
import java.util.*;

public class GraphByArrayList {
	static ArrayList<ArrayList<Integer>> graph; 
	static int N;
	//from v to w
	static void addEdge(int v, int w) {
  		//마찬가지로 무향 그래프니까 양쪽에서 연결관계 넣어죽
		graph.get(v).add(w); //정점 v에 w 추가
		graph.get(w).add(v); //정점 w에 v 추가
	}
	
	//정점의 갯수만큼 추가해주기
	static void init() {
		for(int i=0; i<N; i++) {
			graph.add(new ArrayList<>());
		}
	}
	
	//그래프 확인하기
	static void print() {
		for(int i=0; i<N; i++) {
			ArrayList<Integer> node = graph.get(i);
			for(int j=0; j<node.size(); j++) {
				System.out.println(i+"->"+node.get(j));
			}
		}
		
	}
	
	public static void main(String []  args) {
		
		//정점의 개수
		N = 5;
		graph = new ArrayList<ArrayList<Integer>>();
		init();
		
		// 간선 추가
        addEdge(0, 1);
        addEdge(0, 4);
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(1, 4);
        addEdge(2, 3);
        addEdge(3, 4);
        
        print();
		
		
	}

}

출력값

0->1
0->4
1->0
1->2
1->3
1->4
2->1
2->3
3->1
3->2
3->4
4->0
4->1
4->3

정리

	인접행렬	인접리스트
시간 복잡도	O(N^2)정점 N * N만큼 필요	O(N), N : 간선의 개수
두 정점의 연결여부 파악하기	graph[x][y] 의 값으로 한번에 확인	graph 의 원소에서 y가 나올때까지 탐색
인접한 노드 파악하기	N * N만큼 반복문을 돌아 확인한다.	각 리스트에 담겨있는 원소를 확인한다.