-
Notifications
You must be signed in to change notification settings - Fork 0
/
BFS.pde
25 lines (25 loc) · 928 Bytes
/
BFS.pde
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
import java.util.HashMap;
public Graph getBFS(Graph graph, Vertex a){
Graph bfs = new Graph();
HashMap<Vertex, Boolean> visitedMap = new HashMap<Vertex, Boolean>();
for(Vertex v : graph.getVertexSet())
visitedMap.put(v, false);
LinkedList<Vertex> q = new LinkedList<Vertex>(); //bfs
q.add(a); //visit a
visitedMap.put(a, true);
while(!q.isEmpty()){
Vertex c = q.getLast();
q.removeLast();
for(Edge e: graph.getAdjacentEdges(c)){ //for each adjacent edge
if(!visitedMap.get(e.getDest())){ //if dest is not visited
visitedMap.put(e.getDest(), true); //mark vertex as visited
q.addFirst(e.getDest()); //add to traversal queue
bfs.addEdge(e.getSource(),e.getDest(),e.getWeight());
}
}
}
if(bfs.getVertexSet().size() == graph.getVertexSet().size()){
return bfs;
}
return null; //failed to generate graph
}