-
Notifications
You must be signed in to change notification settings - Fork 5
/
DFS.java
executable file
·145 lines (125 loc) · 3.78 KB
/
DFS.java
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
package com.vee.algorithms.graph;
import java.util.Comparator;
import java.util.Map.Entry;
import com.vee.algorithms.datastructures.LinkedList;
import com.vee.algorithms.datastructures.LinkedListIterator;
import java.util.TreeMap;
/*
* Tree edges: edge (u; v) is a tree edge if v was first discovered by exploring
edge (u; v). The tree edges form a spanning forest of G (no cycles).
* Back edges: an edge (u; v) is a back edge if it connects vertex u to an
ancestor v in a DFS tree.
* Forward edges: an edge (u; v) is a forward edge if it connects a vertex u
to a descendant v in a DFS tree.
* Cross edges: all other edges.
It is easy to show that:
* (u; v) is a tree edge or a forward edge , d[u] < d[v] < f[v] < f[u]
* (u; v) is back edge , d[v] < d[u] < f[u] < f[v]
* (u; v) is a cross edge , d[v] < f[v] < d[u] < f[u]
*/
public class DFS {
private int adjMatrix[][];
private int size;
private int visited[];
private int previsit[],postvisit[];
private int clock;
LinkedList<Integer>[] adjList;
TreeMap<Integer,Integer> order = new TreeMap<Integer,Integer>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {return o2 - o1;};
});
public DFS(int[][] adjMatrix,int size) {
init(adjMatrix,size);
for (int v=0; v<size; v++)
if (visited[v] == 0)
dfs(v);
}
private void dfs(int v) {
visited[v] = 1;
previsit[v] = clock++;
LinkedList<Integer> vList = adjList[v];
for (LinkedListIterator<Integer> iterator = vList.iterator(); iterator.hasNext();) {
int w = iterator.getNext();
check(v,w);
if(visited[w] == 0)
dfs(w);
}
postvisit[v] = clock++;
order.put(clock,v);
}
private boolean check(int u, int v) {
if(previsit[v] > 0 && postvisit[v] == 0)
System.out.println("BackEdge " + (u+1) + "->" + (v+1));
else if(previsit[u] > previsit[v] && previsit[v] == 0)
System.out.println("FwdEdge " + (u+1) + "->" + (v+1));
else
System.out.println("CrossEdge " + (u+1) + "->" + (v+1));
return true;
}
private void init(int[][] adjMatrix,int size) {
this.size = size;
this.adjMatrix = adjMatrix;
clock = 1;
visited = new int[size];
previsit = new int[size];
postvisit = new int[size];
for (int v=0; v<size; v++) visited[v]=0;
toAdjList();
}
@SuppressWarnings("unchecked")
private void toAdjList() {
adjList = new LinkedList[size];
for(int i=0; i< adjMatrix.length; i++) {
adjList[i] = new LinkedList<Integer>();
for(int j=0; j< adjMatrix.length; j++)
if(adjMatrix[i][j] != 0)
adjList[i].insert(j);
}
}
public static void main(String args[]) {
int Y[][] =
{
{0,1,0,1,0,0,0,0,0,0},
{0,0,1,0,0,1,0,0,0,0},
{1,0,0,1,1,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{0,0,0,0,0,1,0,1,0,0},
{0,0,0,0,0,1,0,0,0,1},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,1,0}
};
int X[][] =
{
{0,1,1,0},
{0,0,0,1},
{0,1,0,1},
{1,0,0,0},
};
int size = X[0].length;
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
if(X[i][j] == 1)
System.out.println(i+1 + " " + (j+1));
DFS dfs = new DFS(X,size);
int previsit[] = dfs.getPrevisit();
int postvisit[] = dfs.getPostvisit();
System.out.println("PreVisit");
for(int i=0;i<size;i++) {
System.out.print(previsit[i]+" ");
}
System.out.println("\nPostVisit");
for(int i=0;i<size;i++) {
System.out.print(postvisit[i]+" ");
}
System.out.println("\nOrdering");
for (Entry<Integer, Integer> entry : dfs.order.entrySet())
System.out.print(entry.getValue()+" ");
}
public int[] getPrevisit() {
return previsit;
}
public int[] getPostvisit() {
return postvisit;
}
}