YouTipGraph Theory Path
## Path Finding Algorithm
## Path Finding Algorithm
The path finding algorithm of graphs can also be implemented through depth-first traversal dfs. To find paths from the starting point s to other points in graph, add a global variable from array in the implementation class from the previous section to record the path. from represents the previous node of i on the searched path.
First, the constructor initializes the initial conditions of the path finding algorithm, from = new int[G.V()] and from = new int[G.V()], and sets default values in the loop. The visited array is all set to false, the from array is all set to -1 values, and then performs recursive dfs processing on the starting node.
...
// Constructor, path finding algorithm, finding paths from s to other points in graph
public Path(Graph graph, int s){
// Algorithm initialization
G = graph;
assert s >=0&& s < G.V();
visited =new boolean[G.V()];
from =new int[G.V()];
for(int i =0; i =0&& w < G.V();
return visited;
}
...
To get the specific path from point s to point w, we use the path method to implement it. First check if they are connected, you can call the hasPath method. As known from the constructor, you only need to trace back through the from array to find all paths.
...
Vector path(int w){
assert hasPath(w);
Stack s =new Stack();
// Find the path from s to w through the from array in reverse, and store it in the stack
int p = w;
while( p !=-1){
s.push(p);
p = from;
}
// Take out elements from the stack one by one to get the ordered path from s to w
Vector res =new Vector();
while(!s.empty())
res.add( s.pop());
return res;
}
...
### Java Example Code
**Source Package Download:*## src/tutorial/graph/Path.java file code:
package tutorial.graph;
import tutorial.graph.read.Graph;
import java.util.Stack;
import java.util.Vector;
/**
* Path Finding
*/
public class Path {
// Reference to the graph
private Graph G;
// Starting point
private int s;
// Record whether nodes are visited during dfs
private boolean[] visited;
// Record the path, from represents the previous node of i on the searched path
private int[] from;
// Depth-first traversal of the graph
private void dfs(int v ){
visited=true;
for(int i : G.adj(v))
if(!visited){
from= v;
dfs(i);
}
}
// Constructor, path finding algorithm, finding paths from s to other points in graph
public Path(Graph graph, int s){
// Algorithm initialization
G = graph;
assert s >=0&& s < G.V();
visited =new boolean[G.V()];
from =new int[G.V()];
for(int i =0; i =0&& w < G.V();
return visited;
}
// Query the path from s to w, stored in vec
Vector path(int w){
assert hasPath(w);
Stack s =new Stack();
// Find the path from s to w through the from array in reverse, and store it in the stack
int p = w;
while( p !=-1){
s.push(p);
p = from;
}
// Take out elements from the stack one by one to get the ordered path from s to w
Vector res =new Vector();
while(!s.empty())
res.add( s.pop());
return res;
}
// Print the path from s to w
void showPath(int w){
assert hasPath(w);
Vector vec = path(w);
for(int i =0; i ");
}
}
}