-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCountPathBw2Nodes.java
More file actions
68 lines (60 loc) · 1.64 KB
/
CountPathBw2Nodes.java
File metadata and controls
68 lines (60 loc) · 1.64 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
package algorithm.graph;
import java.util.LinkedList;
/**
* The type Count path bw 2 nodes.
*/
public class CountPathBw2Nodes {
/**
* Count int.
*
* @param graph the graph
* @param source the source
* @param destination the destination
* @return the int
*/
public static int count(Graph graph, int source, int destination) {
int count = 0;
return countRecursive(graph, source, destination, count);
}
private static int countRecursive(Graph graph, int source, int destination, int count) {
LinkedList<Integer>[] list = graph.getAdj();
if (source == destination)
count++;
else {
for (int i = 0; i < list[source].size(); i++) {
int adjVertices = list[source].get(i);
count = countRecursive(graph, adjVertices, destination, count);
}
}
return count;
}
/**
* Main.
*
* @param args the args
*/
public static void main(String args[]) {
int answer;
Graph g1 = new Graph(6);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(1, 3);
g1.addEdge(3, 4);
g1.addEdge(2, 3);
g1.addEdge(4, 5);
answer = count(g1, 0, 5);
System.out.println(answer);
Graph g2 = new Graph(7);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(1, 5);
g2.addEdge(2, 3);
g2.addEdge(2, 4);
g2.addEdge(5, 3);
g2.addEdge(5, 6);
g2.addEdge(3, 6);
answer = count(g2, 0, 3);
System.out.println(answer);
}
}