'How to find a path between two vertices (and shortest path) in an undirected unweighted graph
I want to find a path between two vertices in my graph and look for the shortest. My graph is unweighted and undirected. I use BufferedReader to load the social network graph given in a text file. I already check and there is no edge between the two nodes. I implement BFS to see if the graph is connected and it's not. Do I need to implement DFS to do this? What is the most suitable algorithm to do it?
public class UndirectedGraphs {
HashMap<String, LinkedList<String>> socialNetworkAdj;
public UndirectedGraphs() {
socialNetworkAdj = new HashMap<String, LinkedList<String>>();
}
public void addVertex(String label){
socialNetworkAdj.put(label, new LinkedList<String>());
}
public LinkedList<String> getEdges(String label) {
return socialNetworkAdj.get(label);
}
public void addEdges(String ver1, String ver2) {
if (!socialNetworkAdj.containsKey(ver1)) {
addVertex(ver1);
}
if (!socialNetworkAdj.containsKey(ver2)) {
addVertex(ver2);
}
socialNetworkAdj.get(ver1).add(ver2);
socialNetworkAdj.get(ver2).add(ver1);
//System.out.println(socialNetworkAdj);
}
public int getVertexCount(){
return socialNetworkAdj.keySet().size();
}
List<String> bFS (String root){
List<String> visited = new ArrayList<>();
Queue<String> queue = new LinkedList<>();
queue.add(root);
visited.add(root);
while (!queue.isEmpty()) {
String vertex = queue.poll();
for (String v : this.getEdges(vertex)) {
if (!visited.contains(v)) {
visited.add(v);
queue.add(v);
}
}
}
return visited;
}
public boolean isConnected() {
String anyVertex = (String) socialNetworkAdj.keySet().toArray()[0];
int reachableVertices = bFS(anyVertex).size();
System.out.println("\nReachable Nodes: " + reachableVertices + " vs. vertex count: " + getVertexCount());
if (reachableVertices == getVertexCount()) {
return (true);
} else {
return false;
}
}
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
