Graph Theory

Basic functions for most graph theory problems. Both types of searches are provided where the path is stored backwards in the parent array. An Adjacency matrix is used to store the graph.

public int nodeCount;
public int edge[][];
public int flow[][];
public int parent[];
// Prepares a graph for a given number of nodes.
public void createGraph(int nodeCount) {
this.nodeCount = nodeCount;
this.edge = new int[nodeCount][nodeCount];
this.parent = new int[nodeCount];
}
// Adds a weight to a given edge.
public void addEdge(int start, int end, int weight) {
edge[start][end] = weight;
}
//Breadth-First-Search of Graph using a Queue.
public boolean breadthFirstSearch(int start, int target) {
boolean[] visited = new boolean[nodeCount];
Queue<Integer> queue = new ArrayDeque<Integer>(nodeCount + 2);
queue.offer(start); // Start searching on the first node
parent[start] = -1; // Clear its parent.
while (!queue.isEmpty()) { // While nodes exist in the Q
int u = queue.poll(); / Remove and traverse the next node
if (u == target) // If we've reached the target, return success
return true;
for (int v = 0; v < nodeCount; v++) { // Search all nodes...
// Must be an unvisited node, must have flow left...
if (!visited[v] && (edge[u][v] > flow[u][v])) {
queue.offer(v); // Add it as a possibility for traversal
visited[v] = true; // Mark it as visited
parent[v] = u; // Save the parent of this node for backtracking
}
}
}
return false; // The target node has not been reached.
}
//Depth-First-Search of Graph using a Queue.
public boolean depthFirstSearch(int start, int target) {
boolean[] visited = new boolean[nodeCount];
Stack<Integer> stack = new Stack<Integer>();
stack.push(start); // Start searching on the first node
parent[start] = -1; // Clear its parent.
while (!stack.isEmpty()) { // While nodes exist in the Q
int u = stack.pop(); // Remove and traverse the next node
if (u == target) // If we've reached the target, return success
return true;
for (int v = 0; v < nodeCount; v++) { // Search all nodes...
// Must be an unvisited node, must have flow left...
if (!visited[v] && (edge[u][v] > flow[u][v])) {
stack.push(v); // Add it as a possibility for traversal
visited[v] = true; // Mark it as visited
parent[v] = u; // Save the parent of this node for backtracking
}
}
}
return false; // The target node has not been reached.
}