-
Notifications
You must be signed in to change notification settings - Fork 5
/
BFS.java
executable file
·83 lines (74 loc) · 2.02 KB
/
BFS.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
package com.vee.algorithms.graph;
import com.vee.algorithms.datastructures.LinkedQueue;
/**
* @author vee
* <h5>Breadth First Search</h5>
* <b>Applications</b>
* <li> Finding connected components </li>
* <li> Shortest Path between 2 vertices in a graph of equal length </li>
* <li> {@link} <a href="http://en.wikipedia.org/wiki/Bipartite_graph">Bipartite Graph</a></li>
*/
public class BFS {
private int adjMatrix[][];
private int size;
private int visited[];
private int spanningForest[][];
private LinkedQueue<Integer> queue = new LinkedQueue<Integer>();;
private void bfs(int v) {
int w;
queue.enqueue(v);
while (!queue.isEmpty()) {
v = queue.dequeue();
visited[v] = 1;
for (w = 0; w< size; w++)
if (adjMatrix[v][w] == 1)
if (visited[w] == 0) {
queue.enqueue(w);
spanningForest[v][w] = 1;
visited[w] = -1;
}
}
}
public BFS(int[][] adjMatrix,int size) {
init(adjMatrix,size);
for (int v=0; v<size; v++)
if (visited[v] == 0)
bfs(v);
}
private void init(int[][] adjMatrix,int size) {
this.size = size;
this.adjMatrix = adjMatrix;
spanningForest = new int[size][size];
visited = new int[size];
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
spanningForest[i][j]=0;
for (int v=0; v<size; v++) visited[v]=0;
}
public static void main(String args[]) {
int X[][] =
{
{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 size = 10;
BFS bfs = new BFS(X,size);
int C[][] = bfs.getSpanningForest();
for(int i=0;i<size;i++) {
for(int j=0;j<size;j++)
System.out.print(C[i][j] + " ");
System.out.println();
}
}
public int[][] getSpanningForest() {
return spanningForest;
}
}