그래프

그래프의 정의

그래프는 정점(vertex)과 간선(edge)으로 구성된 자료구조이다.

그래프의 종류

• 무방향 그래프
  • 간선에 방향이 없는 즉 간선이 양방향인 그래프이다.
• 방향 그래프
  • 간선에 방향이 있는 그래프이다.
  • 두 정점 u, v가 있을 때 u -> v와 v -> u가 다른 간선을 의미한다.
• 가중치 그래프
  • 간선에 가중치를 부여한 그래프이다.
  • 가중치 그래프도 방향 그래프와 무방향 그래프로 나눌 수 있다.

그래프의 표현

그래프는 인접 행렬과 인접 리스트로 표현할 수 있다.

인접 행렬

그래프의 연결 관계를 이차원 배열로 표현한다. (adj[n][n])

정점 a와 b를 잇는 간선이 있을 경우 adj[a][b] = 1이 된다.

무방향 그래프의 경우 a-> b, b -> a 양방향을 모두 1로 표시하고 방향 그래프는 해당하는 방향만 1로 표현한다.

가중치 그래프의 경우 간선이 있으면 해당 값을 1로 표시하는 것이 아니라 가중치로 표시한다.

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] adj = new int[n + 1][n + 1];
		while(m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj[a][b] = 1;
		}
	}
}

인접 리스트

n개의 연결 리스트를 통해 각 정점에 연결된 정점을 관리한다.

자바를 이용한다면 가중치가 없는 그래프의 경우 이중 ArryList를 이용한다.

가중치가 있는 그래프의 경우 Edge class를 만들고 Edge로 이루어진 ArrayList로 인접 리스트를 만든다.

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
		for (int i = 0; i <= n; i++)
			adj.add(new ArrayList<>());
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj.get(a).add(b);
		}
	}
}

class Edge {
	int s, e, w;

	public Edge(int s, int e, int w) {
		this.s = s;
		this.e = e;
		this.w = w;
	}
}

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		ArrayList<Edge> adj = new ArrayList<>();
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			adj.add(new Edge(a, b, w));
		}
	}
}

인접 행렬과 인접 리스트 비교

인접 행렬은 두 정점을 잇는 간선을 한 번의 배열 접근만으로 확인할 수 있다는 장점이 있다.

인접 리스트의 경우 간선이 있는지 확인하려면 연결 리스트를 처음부터 읽어가면서 확인해야 한다.

반면에 인접 행렬은 2차원 배열을 사용하기 때문에 실제 간선의 수와 관계없이 항상 O(n^2)의 공간을 사용한다는 문제가 있다.

인접 리스트는 실제 간선 수만큼을 저장하기 때문에 O(n + m)의 공간을 사용한다.

각자 장단점이 있기 때문에 두 표현을 적절히 골라 사용해야 한다.