Graph Algorithms
Graph algorithms are used to solve the problems of representing graphs as networks like airline flights, how the Internet is connected, or social network connectivity on Facebook. They are also popular in NLP and machine learning fields to form networks (Ejonavi 2020). In this post, I will talk about some important graph algorithms with basic ideas under the hood, specific implementations, and complexity analysis.
Breadth First Search (BFS)
Idea for breadth-first-search: Start from node s and visit all nodes with distance i to s in iteration i.
Implementation:
public class BFS {
int nodeNum;
LinkedList<Integer>[] adjacencyList;
public BFS(int nodeNum) {
this.nodeNum = nodeNum;
adjacencyList = new LinkedList[nodeNum];
for (int i = 0; i < nodeNum; i++) {
adjacencyList[i] = new LinkedList<>();
}
}
public void addEdge(int parent, int child) {
adjacencyList[parent].add(child);
}
public void BFS(int startingNode) {
ArrayList<ArrayList<Integer>> outcome = new ArrayList<>();
ArrayList<Boolean> visited = new ArrayList<>(Collections.nCopies(nodeNum, false));
LinkedList<Integer> myQue = new LinkedList<>();
myQue.push(startingNode);
visited.set(startingNode, true);
while (!myQue.isEmpty()) {
ArrayList<Integer> oneLayer = new ArrayList<>();
int size = myQue.size();
for (int i = 0; i < size; i++) {
int s = myQue.remove();
oneLayer.add(s);
for (int n : adjacencyList[s]) {
if (!visited.get(n)) {
visited.set(n, true);
myQue.add(n);
}
}
}
outcome.add(oneLayer);
}
System.out.println(outcome);
}
}
Depth First Search (DFS)
Idea for depth-first-search: Whenever you visit a vertex, explore in the next step one of its non-visited neighbors.
Implementation:
public class DFS {
LinkedList<Integer>[] adjacencyList;
ArrayList<Boolean> visited;
public DFS(int nodeNum) {
adjacencyList = new LinkedList[nodeNum];
for (int i = 0; i < nodeNum; i++) {
adjacencyList[i] = new LinkedList<>();
}
visited = new ArrayList<>(Collections.nCopies(nodeNum, false));
}
public void addEdge(int parent, int child) {
adjacencyList[parent].add(child);
}
public void DFS(int startingNode) {
System.out.println(startingNode);
visited.set(startingNode, true);
for (int n : adjacencyList[startingNode]) {
if (!visited.get(n)) {
DFS(n);
}
}
}
}
Dijkstra Algorithm
-
Dijkstra’s algorithm is a dynamic programming-like strategy. It checks all the outgoing edges of x to see whether there is a better path from s to some unknown vertex through x.
-
At most V deleteMin and insert operations, and at most E decreaseKey operations.
- TDijkstra = O(E * TdecreaseKey(n) + V * (TdeleteMin(n) + Tinsert(n)))
- Original: O(E + V2)
- Binary Heap: O((E + V)log(V))
- Fibonacci Heap: O(E + Vlog(V))
Implementation:
Class Declaration
class Node implements Comparable<Node> {
int node;
int cost;
Node(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
Implementation
public class Dijkstra {
LinkedList<Node>[] adjacencyList;
ArrayList<Boolean> visited;
int nodeNum;
public Dijkstra(int nodeNum) {
adjacencyList = new LinkedList[nodeNum];
for (int i = 0; i < nodeNum; i++) {
adjacencyList[i] = new LinkedList<>();
}
visited = new ArrayList<>(Collections.nCopies(nodeNum, false));
this.nodeNum = nodeNum;
}
public void addEdge(int parent, int child, int cost) {
adjacencyList[parent].add(new Node(child, cost));
}
public void dijkstra(int startingNode) {
PriorityQueue<Node> myQue = new PriorityQueue<>();
ArrayList<Integer> distance = new ArrayList<>(Collections.nCopies(nodeNum, Integer.MAX_VALUE));
// Initialisation
myQue.add(new Node(startingNode, 0));
distance.set(startingNode, 0);
while (!myQue.isEmpty()) {
int u = myQue.poll().node;
visited.set(u, true);
for (Node n : adjacencyList[u]) {
if (!visited.get(n.node)) {
int v = n.node;
int weight = n.cost;
if (distance.get(v) > distance.get(u) + weight) {
distance.set(v, distance.get(u) + weight);
myQue.add(new Node(v, distance.get(v)));
}
}
}
}
// Print shortest distances stored in dist[]
for (int i = 0; i < distance.size(); i++) {
System.out.println(i + " " + distance.get(i));
}
}
}
Minimum Spanning Tree and Algorithms
-
Minimum Spanning Tree: A spanning tree of a graph G = (V, E) is a subset of edges from E forming a tree connecting all vertices of V. A minimum spanning tree minimizes the total length over all possible spanning trees.
-
Prim’s Algorithm: Prim’s algorithm starts from one vertex and grows the rest of the tree one edge at a time until all vertices are included. This algorithm works in a greedy manner such that it picks the best local optimum which is the shortest path to connect with a new unvisited node in each iteration. The time complexity of Prim’s algorithm is O(E + Vlog(V)) when using Fibonacci heaps for implementation of the priority queue.
Implementation
Class Declaration
class Node implements Comparable<Node> {
int node;
int cost;
Node(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
@Override
public String toString() {
return "Node{" +
"node=" + node +
", cost=" + cost +
'}';
}
}
Implementation
public class Prim {
LinkedList<Node>[] adjacencyList;
ArrayList<Boolean> visited;
int nodeNum;
public Prim(int nodeNum) {
adjacencyList = new LinkedList[nodeNum];
for (int i = 0; i < nodeNum; i++) {
adjacencyList[i] = new LinkedList<>();
}
visited = new ArrayList<>(Collections.nCopies(nodeNum, false));
this.nodeNum = nodeNum;
}
public void addEdge(int parent, int child, int cost) {
adjacencyList[parent].add(new Node(child, cost));
adjacencyList[child].add(new Node(parent, cost));
}
public ArrayList<Integer> prim(int startingNode) {
ArrayList<Integer> outcome = new ArrayList<>(Collections.nCopies(nodeNum, -1));
PriorityQueue<Node> myQue = new PriorityQueue<>();
ArrayList<Integer> distance = new ArrayList<>(Collections.nCopies(nodeNum, Integer.MAX_VALUE));
myQue.add(new Node(startingNode, 0));
distance.set(startingNode, 0);
outcome.set(startingNode, startingNode);
while (!myQue.isEmpty()) {
int node = myQue.poll().node;
visited.set(node, true);
for (Node neighbour : adjacencyList[node]) {
int weight = neighbour.cost;
int vertex = neighbour.node;
if (!visited.get(vertex) && distance.get(vertex) > weight) {
distance.set(vertex, weight);
outcome.set(vertex, node);
myQue.add(new Node(vertex, distance.get(vertex)));
}
}
}
return outcome;
}
}
-
Kruskal’s Algorithm: Kruskal’s algorithm repeatedly considers the lightest remaining edge and tests whether its two endpoints lie within the same connected component. This algorithm works by sorting edges based on their weight. The time complexity of Kruskal’s algorithm is O(Elog(E)).
- 2E find operation and (n - 1) union operation.
- O(2E + Vlog(V)) | Sorting takes O(Elog(E)) | E > V
- O(Elog(E))
-
Prim’s algorithm is more efficient for dense graphs, while Kruskal’s algorithm is more efficient for sparse graphs.
Reference
- Ejonavi, J 2020, Algorithms 101: How to use graph algorithms, Educative, viewed 1 October 2022, https://www.educative.io/blog/graph-algorithms-tutorial.