Repository navigation
Expand file tree
/
Copy pathDepthFirstSearch.java
More file actions
84 lines (72 loc) · 1.58 KB
/
Copy pathDepthFirstSearch.java
File metadata and controls
84 lines (72 loc) · 1.58 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package DepthFirstSearch;
import java.util.List;
import java.util.Stack;
public class DepthFirstSearch {
// private Stack<Vertex> stack;
//
// public DepthFirstSearch(){
// this.stack=new Stack<>();
// }
//
// public void dfsRecursive(Vertex vertex){
//
// System.out.print(vertex+"->");
//
// for( Vertex v : vertex.getNeighbourList() ){
// if( !v.isVisited() ){
// v.setVisited(true);
// dfsRecursive(v);
// }
// }
// }
//
// public void dfsNormal(Vertex root){
//
// stack.add(root);
// root.setVisited(true);
//
// while( !stack.isEmpty() ){
//
// Vertex actualVertex = stack.pop();
// System.out.print(actualVertex+"->");
//
// for( Vertex v : actualVertex.getNeighbourList() ){
// if( !v.isVisited() ){
// v.setVisited(true);
// stack.push(v);
// }
// }
// }
// }
private List<Vertex> vertexList;
private int time = 0;
public DepthFirstSearch(List<Vertex> vertexList){
this.vertexList = vertexList;
}
public void runDfs(){
for( Vertex vertex : vertexList ){
if( !vertex.isVisited() ){
dfs(vertex);
}
}
}
public void dfs(Vertex vertex){
System.out.print(vertex.getName()+"-");
time++;
vertex.setStartingRank(time);
for( Vertex v : vertex.getNeighbourList() ){
if( !v.isVisited() ){
v.setVisited(true);
v.setPredecessor(vertex);
dfs(v);
}
}
time++;
vertex.setFinishingRank(time);
}
public void printVertices(){
for(Vertex vertex : vertexList){
System.out.println(vertex+"");
}
}
}