본문 바로가기
Study

(JAVA) Java DFS 구현 Java dfs ArrayList

by Developer RyanKim 2019. 3. 16.

n : 정점의 수

m : 간선의 수


0 - 1 - 2

라고 가정하면

입력을

0

1

1

2

로 해야한다.

a[0] 1

a[1] 0 2

a[2] 1



public static void main(String[] args) {
int n = 5;
int m = 4;

Scanner sc = new Scanner(System.in);
ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n];
for (int i = 0; i < n; i++) {
a[i] =
new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
a[v1].add(v2);
a[v2].add(v1);
}
Boolean[] visited =
new Boolean[a.length];
for(int i = 0; i < visited.length; i++) {
visited[i] =
false;
}
dfs(a,visited,0); //0자리는 시작정점으로 정할것을 넣자

}

public static void dfs(ArrayList<Integer>[] a ,Boolean[] visited, int v){
if(visited[v]) return;

System.out.println("v : " + v);
visited[v] = true;

for(int vv : a[v]){
dfs(a,visited,vv);
}
}


댓글