Graph Traversals and Implementations
BFS (Breadth First Search)
This algorithm of exploring a vertex's immediate children before moving on to its grandchildren is known as Breadth First Traversal.
Initialize the a queue with the starting vertex and mark that vertex.
Repeat until the queue is empty:
Remove vertex v from the front of the queue.
For each unmarked neighbor n of v:
Mark n.
Add n to the end of the queue.
Set edgeTo[n] = v.
Set distTo[n] = distTo[v] + 1.
Graph API
To Implement our graph algorithms like BreadthFirstPaths and DepthFirstPaths:
An API for Graphs.
An underlying data structure to represent the graphs.
The API uses integers to represent vertices. Map<Label, Integer> is required to lookup vertices by labels.
public class Graph {
public Graph(int V): // Create empty graph with v vertices
public void addEdge(int v, int w): // add an edge v-w
Iterable<Integer> adj(int v): // vertices adjacent to v
int V(): // number of vertices
int E(): // number of edges
...Number of vertices must be specified in advance.
Does not support weights on nodes or edges.
Has no method for getting the degree for a vertex.
degree(Graph G, int v)
public static int degree(Graph G, int v) {
int degree = 0;
for (int w: G.adj(v)) {
degree += 1;
}
return degree;
}print(Graph G)
public static void print(Graph G) {
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
}Graph Representations
The choice of data structure to represent the graph should have implications on both runtime and memory usage.
Adjacency Matrix
Use a 2D array. There is an edge connecting vertex s to t if that corresponding cell is 1, which represents true.
Edge Sets
Use a single set to create a collection of all edges.
Adjacency Lists
Use an array of lists, indexed by vertex number. Each index contains the index of its adjancent vertices.
Implementation
public class Graph {
private final int V;
private List<Integer>[] adj;
public Graph(int V) {
this.V = V;
adj = (List<Integer>[]) new ArrayList[V];
for (int v = 0; v < V; v++) {
adj[v] = new ArrayList<Integer>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}Runtime
Representation
addEdge(s, t)
for(w : adj(v))
print()
hasEdge(s, t)
space used
Adjacency Matrix
Θ(1)
Θ(V)
Θ(V^2)
Θ(1)
Θ(V^2)
Edge Sets
Θ(1)
Θ(E)
Θ(E)
Θ(E)
Θ(E)
Adjacency Lists
Θ(1)
Θ(1) to Θ(V)
Θ(V+E)
Θ(degree(v))
Θ(V+E)
Implementation
Create a Paths API, which takes a Graph object and query the graph-processing for information.
public class Paths {
public Paths(Graph G, int s) // Find all paths from G
boolean hasPathTo(int v) // is there a path from s to v?
Iterable<Integer> pathTo(int v) // path from s to v (if any)
}Depth First Search
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s) {
... // Data structure initialization
dfs(G, s); // Recursively find vertices connected to s
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w: G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
}
public Iterable < Integer > pathTo(int v) {
if (!hasPathTo(v)) return null;
List <Integer> path = new ArrayList < > ();
for (int x = v; x != s; x = edgeTo[x]) {
path.add(x);
}
path.add(s);
Collections.reverse(path);
return path;
}
public boolean hasPathTo(int v) {
return marked[v];
}
}Runtime
The DepthFirstPaths constructor:
O(V+E).Each vertex is visited at most once (
O(V)).
Each edge is considered at most twice (
O(E)).
Breadth First Search
public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
...
private void bfs(Graph G, int s) {
Queue <Integer> fringe = new Queue <Integer> ();
fringe.enqueue(s);
marked[s] = true;
while (!fringe.isEmpty()) {
int v = fringe.dequeue();
for (int w: G.adj(v)) {
if (!marked[w]) {
fringe.enqueue(w);
marked[w] = true;
edgeTo[w] = v;
}
}
}
}
}Graph Problems
Adjacency List Based Graphs
Problem|Description|Solution|Efficiency (adj. list) |---|---|---|---| s-t paths|Find a path from s to every reachable vertex.|DepthFirstPaths|O(V+E) time, Θ(V) space. s-t shortest paths|Find a shortest path from s to every reachable vertex.|BreadthFirstPaths|O(V+E) time, Θ(V) space.
Adjacency Matrix Based Graphs
Problem|Description|Solution|Efficiency (adj. list) |---|---|---|---| s-t paths|Find a path from s to every reachable vertex.|DepthFirstPaths|O(V^2) time, Θ(V) space. s-t shortest paths|Find a shortest path from s to every reachable vertex.|BreadthFirstPaths|O(V^2) time, Θ(V) space.
Last updated