그래프를 구현하는 방법은 두 가지로 나뉜다.

1. 인접 행렬을 활용한 그래프 구현

2. 인접 리스트(ArrayList)를 활용한 그래프 구현

인접행렬을 활용한 그래프 구현

package testcases;

import java.io.*;

public class Test {

	public static void printGraph(int[][] graph) {
		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 static void putEdge(int[][] graph, int x, int y) {
		graph[x][y] = 1;
		graph[y][x] = 1;
	}
	
	public static void main(String[] args) throws IOException {
		int n = 5; //그래프 정점의 개수
		int[][] graph = new int[n+1][n+1]; //index를 1부터 맞추기 위해 n+1

		putEdge(graph, 1, 2);
		putEdge(graph, 1, 3);
		putEdge(graph, 1, 4);
		putEdge(graph, 2, 3);
		putEdge(graph, 2, 5);
		putEdge(graph, 3, 4);
		putEdge(graph, 4, 5);

		printGraph(graph);
	}
}

인접 리스트를 활용한 그래프 구현

package testcases;

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

public class Test {

	public static void print(ArrayList<ArrayList<Integer>> graph) {
		for (int i = 1; i < graph.size(); i++) {
			ArrayList<Integer> node = graph.get(i); // 2차원 리스트 graph의 i번째를 arraylist로 가져옴
			System.out.print("node"+"["+i+"] : ");
			for (int j = 0; j < node.size(); j++)
				System.out.print(node.get(j)+ "->");
			System.out.println();
		}
	}

	public static void putEdge(ArrayList<ArrayList<Integer>> graph, int x, int y) {
		graph.get(x).add(y); // get(): 해당 번지의 값을 가져옴 
		graph.get(y).add(x);
	}

	public static void main(String[] args) throws IOException {
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

		for (int i = 0; i <= 5; i++)
			graph.add(new ArrayList<>());

		putEdge(graph, 1, 2);
		putEdge(graph, 1, 3);
		putEdge(graph, 1, 4);
		putEdge(graph, 2, 3);
		putEdge(graph, 2, 5);
		putEdge(graph, 3, 4);
		putEdge(graph, 4, 5);

		//		System.out.println(graph);
		//		ArrayList<Integer> node = graph.get(3);
		//		System.out.println(node);

				print(graph); 
	}
}

각각의 장단점

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

• 행렬의 경우

  두 정점이 연결되있는지를 확인하는 방법이 쉽다.
  graph[x][y]의 값을 바로 확인해서 유무를 판단할 수 있기 때문이다.
  단, 정점이 N개인 경우, 행렬을 만들기 위해선 N * N만큼의 공간이 필요하게 된다.

  무방향 그래프의 경우는 절반의 공간이 낭비되는 셈이다.
  

• 리스트의 경우

  실제 연결된 노드들만 리스트 원소에 담겨있으므로 공간 복잡도가 N(간선)이다.

  다만, 두 정점 x, y가 연결되있는지 알고 싶다면 노드x 리스트로 들어가 원소 y가 있는지 처음부터 쭉 탐색해야 하므로 행렬보다 더 많은 시간이 소요된다.

둘 다 각각 장단점을 가지고 있으므로 상황에 따라 맞게 골라쓰면 된다.

간선이 많은 그래프의 경우, 인접 행렬을 통해 빠르게 연결 여부를 확인할 수 있다.

반면 간선이 적은 그래프의 경우는 인접 리스트를 통해 인접 노드를 빠르게 확인할 수 있다.

🙇‍♂️출처🙇‍♂️ : https://born2bedeveloper.tistory.com/42