-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNodesInGivenLevel.java
More file actions
72 lines (66 loc) · 1.98 KB
/
NodesInGivenLevel.java
File metadata and controls
72 lines (66 loc) · 1.98 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
package algorithm.graph;
import datastructure.graph.AdjacencyListGraph;
import java.util.Iterator;
import java.util.LinkedList;
/**
* The type Nodes in given level.
*/
public class NodesInGivenLevel {
/**
* Gets nodes in given level.
*
* @param graph the graph
* @param source the source
* @param level the level
* @return the nodes in given level
*/
public static int getNodesInGivenLevel(AdjacencyListGraph graph, int source, int level) {
int vertices = graph.vertices;
int count = 0;
int[] visited = new int[vertices];
visited[source] = 1;
LinkedList<Integer> queue = new LinkedList<Integer>();
queue.add(source);
while (queue.size()!=0) {
source = queue.poll();
LinkedList<Integer> aList[];
aList = graph.adjacencyList;
Iterator<Integer> i = aList[source].listIterator();
while (i.hasNext()) {
int t = i.next();
if (visited[t] != 1) {
visited[t] = visited[source] + 1;
if (visited[t] < level)
queue.add(t);
}
}
}
for (int i = 0; i < vertices; i++)
if (visited[i] == level)
count++;
return count;
}
/**
* Main.
*
* @param args the args
*/
public static void main(String args[]) {
AdjacencyListGraph g = new AdjacencyListGraph(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(3, 5);
g.addEdge(2, 4);
int answer;
answer = getNodesInGivenLevel(g, 0, 1);
System.out.println(answer);
answer = getNodesInGivenLevel(g, 0, 2);
System.out.println(answer);
answer = getNodesInGivenLevel(g, 0, 3);
System.out.println(answer);
answer = getNodesInGivenLevel(g, 0, 4);
System.out.println(answer);
}
}