深さ優先探索(DFS)を再帰を用いて実装
有向グラフを想定した時の、DFSの使い方を整理しました。
ノード数nが与えられ、次に各ノードの出次数とそれぞれの隣接するノードをk個、入力された時に、どの順序でエッジを辿っていくかを出力するようにしています。
import java.util.Scanner; public class DFS { static Scanner sc = new Scanner(System.in); static int n = sc.nextInt(); static int[][] edge = new int[n][n]; static boolean[] visited = new boolean[n]; static int[] first_v = new int[n]; // 最初に訪れる時刻 static int[] end_v = new int[n]; // 最後に訪れる時刻 static int s = 0; public static void main(String[] args){ for (int i=0; i<n; i++){ int v = sc.nextInt()-1; int k = sc.nextInt(); for (int j=0; j<k; j++){ int u = sc.nextInt()-1; edge[v][u] = 1; } } dfs(0); for (int i=0; i<n; i++){ System.out.println(first_v[i]); } System.out.println(); for (int i=0; i<n; i++){ System.out.println(end_v[i]); } } public static void dfs(int v){ // 再帰によるDFS first_v[v] = ++s; for (int u=0; u<n; u++){ if (edge[v][u]==0) continue; if (!visited[u]){ dfs(u); } } visited[v] = true; end_v[v] = ++s; } }