[알고리즘]Graph - 경로 탐색(인접행렬, DFS)

Graph(그래프) - G(V, E)

 

 

Vertex(정점), Edge(간선)으로 구성되어있다.

 

종류

무방향 그래프 & 방향 그래프

 

무방향 가중치 그래프 & 방향 가중치 그래프

 

Adjacency Matrix(인접행렬)

• 인접 정점을 찾기 위해 모든 정점을 순회해야 한다.
• 그래프에 간선이 많이 존재하는 밀집 그래프인 경우 유리하다.

 

Adjacency List(인접리스트)

• 정점의 개수가 많은 경우 유리하다.
• 그래프에 간선이 적게 존재하는 희소 그래프인 경우 유리하다.

 

그래프 탐색

• DFS: 깊이 우선 탐색 -> stack
• BFS: 너비 우선 탐색 -> queue

 

 

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램

import java.util.Scanner;

public class Main { // DFS
	static int n, m, answer = 0;
	static int[][] graph;
	static int[] ch;
	
	public static void DFS(int v) {
		if (v==n) answer++;
		else {
			for (int i=1; i<=n; i++) {
				if (graph[v][i]==1 && ch[i]==0) {
					ch[i] = 1;
					DFS(i);
					ch[i] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt(); // 정점의 수
		m = scanner.nextInt(); // 간선의 수
		ch =  new int[n+1]; // 방문한 정점
		graph = new int[n+1][n+1]; // 인접행렬
		for (int i=0; i<m; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();		
			graph[a][b] = 1;
		}
		ch[1] = 1;
		DFS(1);
		System.out.println(answer);
	}

}

---

5 9
1 2 
1 3
1 4 
2 1 
2 3 
2 5 
3 4 
4 2 
4 5 
6