[알고리즘/JAVA] 그래프

그래프란?

정점(Vertex)들의 집합과 이들을 연결하는 간선 (Edge)들의 집합으로 구성된 자료구조

 

그래프의 종류

• 무향 그래프(Undirected Graph)
  

• 유향 그래프(Directed Graph)
  
• 순환 그래프(Cycle graph)
  
• 가중치 그래프(Weighted Graph)
  
• 사이클 없는 방향 그래프(DAG, Directed Acyclic Graph)
  
  
  

 

그래프 저장 방법

간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정

1. 인접 행렬
2. 인접 리스트

인접 행렬(Adjacent matrix)

|V| x |V| 크기의 2차원 배열을 이용해서 간선 정보를 저장(V: 정점의 수) 배열의 배열

인접 리스트(Adjacent List)

각 정점마다 해당 정점으로 나가는 간선의 정보를 저장

	인접 행렬	인접 리스트
A와 B를 잇는 간선 존재 여부 확인 (시간 복잡도)	O(1)	O(min(deg(A), deg(B)))
A와 연결된 모든 정점 확인 (시간 복잡도)	O(|V|)	O(deg(A))
공간 복잡도	O(|V|2)	O(|E|)

 

 

그래프 탐색 방법

 

깊이 우선 탐색(Depth First Search)

루트 노드(시작 정점 , 출발 위치)에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드(정점)로 되돌아와서 다른 방향의 노드 정점 으로 탐색을 계속 반복하여 결국 모든 노드(정점)을 방문하는 순회방법

예시 코드

public class 그래프01_DFS {
	static int N = 7;
	//인접행렬
	static int[][] adj = { 
			{ 0, 1, 1, 0, 0, 1, 0 }, 
			{ 1, 0, 0, 1, 0, 0, 1 }, 
			{ 1, 0, 0, 1, 0, 0, 0 },
			{ 0, 1, 1, 0, 0, 0, 1 },
			{ 0, 0, 0, 0, 0, 1, 1 },
			{ 1, 0, 0, 0, 1, 0, 0 }, 
			{ 0, 1, 0, 1, 1, 0, 0 } };
	
	static boolean[] visited = new boolean[N];
	
	public static void main(String[] args) {
		DFS(0);
	}
	
	static void DFS(int v) {
		// v에 대한 방문처리를 하겠다.
		visited[v] = true;
		System.out.println(v+1);
		//나와 연결되어 있으면서 (간선이 존재하면서) 아직 방문하지 않은 정점을 재귀호출
		for(int i = 0; i<N; i++) {
			//방문하지 않았고 / 간선이 존재하면
			if(!visited[i] && adj[v][i] == 1) {
				 DFS(i);
			}
		}
	}
}

 

너비 우선 탐색(Breadth First Search)

너비 우선 탐색은 탐색 루트 노드(시작 정점 , 출발 위치)의 자식 노드(인접한 정점)들을 먼저 모두 차례로 방문한 후에 방문했던 자식 노드들(인접한 정점)을 시작점으로 하여 다시 해당 노드의 자식 노드(인접한 정점)들을 차례로 방문하는 방식

예시코드

import java.util.LinkedList;
import java.util.Queue;

public class BFS_01 {
	static int N = 7;
	//인접행렬
	static int[][] adj = { 
			{ 0, 1, 1, 0, 0, 1, 0 }, 
			{ 1, 0, 0, 1, 0, 0, 1 }, 
			{ 1, 0, 0, 1, 0, 0, 0 },
			{ 0, 1, 1, 0, 0, 0, 1 },
			{ 0, 0, 0, 0, 0, 1, 1 },
			{ 1, 0, 0, 0, 1, 0, 0 }, 
			{ 0, 1, 0, 1, 1, 0, 0 } };
	
	static boolean[] visited = new boolean[N];
	static Queue<Integer> queue = new LinkedList<>();
	
	public static void main(String[] args) {
		BFS(0);
	}
	
	static void BFS(int v) {
		queue.add(v);
		visited[v] = true;
		
		while (!queue.isEmpty()) {
			int curr = queue.poll();
			System.out.print(curr+1+" ");
			for (int i = 0; i < adj.length; i++) {
				if(adj[curr][i]==1 && !visited[i]) {
					queue.add(i);
					visited[i] = true;
				}
			}
		}
	}
}

 

시간 복잡도

	DFS	BFS
인접 행렬	O(n2)	O(n2)
인접 리스트	O(n+e)	O(n+e)

 

예시 문제

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int N, M, V;
	static boolean[] visited;
	static ArrayList<Integer>[] arr;
	static Queue<Integer> queue = new LinkedList<>();
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		visited = new boolean[N+1];
		arr = new ArrayList[N+1];
		for (int i = 1; i <= N; i++) {
			arr[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			arr[x].add(y);
			arr[y].add(x);
		}
		for (int i = 1; i <= N; i++) {
			Collections.sort(arr[i]);
		}
		DFS(V);
		System.out.println(sb.toString());
		sb = new StringBuilder(); Arrays.fill(visited, false);
		BFS(V);
		System.out.println(sb.toString());
	}
	// DFS 탐색
	private static void DFS(int v) {
		visited[v] = true;
		sb.append(v).append(' ');
		for (int i = 0; i < arr[v].size(); i++) {
			if(visited[arr[v].get(i)]) continue;
			DFS(arr[v].get(i));
		}
	}
	// BFS 탐색
	private static void BFS(int v) {
		queue.add(v);
		visited[v] = true;
		while (!queue.isEmpty()) {
			int x = queue.poll();
			sb.append(x).append(' ');
			for (int i = 0; i < arr[x].size(); i++) {
				if(visited[arr[x].get(i)]) continue;
				queue.add(arr[x].get(i));
				visited[arr[x].get(i)] = true;
			}
		}
	}

}