Graph ML: Graph Algorithms

The following are standard graph algorithms.

1. Graph Search

We are searching for a particular vertex in the graph.

For DFS and BFS, we need to iterate over each of the \(V\) nodes and each of its edges \(E\). We visit the edge from both sides, i.e. from each of the nodes attached to it, so we perform \(V + 2E\) steps.

The complexity is therefore \(O(V+ E)\).

1.1. Depth-First Search (DFS)

Start at the root node and go as deep as possible before backtracking.

DFS is a recursive algorithm where we keep track of the nodes visited so far.

It is similar to the binary tree traversal algorithm, which shouldn’t be surprising since a tree is a type of graph and we want to traverse it to find our target node.

Steps:

1. Initialise: Start at any (random) node.
2. Visit the node: Add the current node to the visited_nodes hash table.
3. Recursively visit neighbors: Iterate through the current node’s neighbors. If the neighbor has already been visited, ignore it. Otherwise, recursively call DFS on the unvisited neighbor, i.e. go back to Step 2.

DFS can be used to find cycles, because a node will be visited twice during traversal if and only if a cycle exists.

1.2. Breadth-First Search (BFS)

Start at the root node and explore all neighbors before going deeper.

BFS does not rely on recursion, instead using a queue to track the execution order.

Steps:

1. Initialise: Start at any (random) node.
2. Visit the node: Add the current node to the visited_nodes hash table and to the node_queue.
3. Iterate through the queue: Run a while-loop to iterate while the queue is populated.
4. Process the queue: Pop the first node from node_queue. Iterate over its neighbors. If the neighbor has been visited already, ignore it. Otherwise, visit the node - add it to the visited_nodes hash table and to the node_queue. Repeat until the queue is empty.

1.3. A* Algorithm

1.4. Bidirectional Search

2. Shortest Path Algorithms

We are trying to find the shortest path between two nodes.

2.1. Dijkstra’s Algorithm

Dijkstra’s algorithm maintains

1. A hash map shortest_distances containing shortest known distances from the starting node to each node visited.
2. A hash map shortest_path_previous_node tracking the previous node visited on the shortest knonw path to a node.

A nice bonus is that it ends up finding the shortest path from the source node to all other nodes, not just the target node we care about.

Steps:

1. Initialise: Start at the source node and make it the current_node.
2. Check the immediate neighbours: If the distance to a neighbor from the source node is shorter than the current known shortest_distances, then update shortest_distances and shortest_path_previous_node.
3. Visit the new node closest to source: Visit whichever unvisited node has the shortest known distance. Make it the current_node and repeat Step 2.

3. Minimum Spanning Tree

3.1. Kruskal’s Algorithm

3.2. Prim’s Algorithm

4. Further Topics in Graph Theory

• Tarjan’s strongly connected components algorithm
• Topological sort
• Floyd-Warshall algorithms
• Bellman-Ford algorithm
• Graph coloring
• Min-cut max-flow