Graph Algorithms

Graph

Graph is a type of data structure, that is consist of some nodes connected with edges. These edges can be directed or undirected. The directed edges can be seen as a one way street while the undirected edges are more of a two-way street. A simple class for a node in graph can look like below:

class node{
    int num;
    node* children[];
};


class Graph {
    node arrayOfNodes[];
};

In terms of representing graph in programming, there are two common ways:

Adjacency List

This is the common way of representing graph. In this representation every node store a list of adjacent nodes. For the undirected graph, the edge would be stored twice. Technically defining a graph class is not necessary; an array can store the adjacency list. The graph above can be represented as:

0: 1, 2 1: 2: 0, 1 3: 1

This will simply give the relationship between the nodes in a graph but not quiet clean. Usually the node class is being used unless we do not have to.

Adjacency Matrices

An adjacency matrix is an NxN matrix where 1 is representing an edge from node i to node j at matrix[i][j] position. For undirected graph the adjacency matrix will be symmetric but in directed graph it will not necessarily be. We can use the same graph algorithms that are used with adjacency list with adjacency matrix but one down fall of adjacency matrix is in order to iterate through the neighbors of a node we need to iterate through all the nodes to find the ones that are neighbor. However this is not the case with adjacency list, in order to find the neighbor of a node we can easily iterate through the neighbors of a node. Searching a Graph

The most common ways to search in a graph are depth first search (DFS) and breadth first search.

For depth first search, we start at a node and explore each branch completely before moving on to the next branch. On the other hand, in breadth first search, we start at a node and explore just the neighbor before going deep. BFS follows greedy algorithm principle, which we look for local solution and hope to find the global optimal solution. Depends on the scenario each of these algorithms can be handy. When we are trying to visit every node in the graph in order to come up with the solution we tend to use the depth first search but when we are looking to find the shortest path between two nodes, the BFS is generally preferred.

Depth First Search (DFS)

In DFS, we tend to visit a node and then iterate through each of the nodes neighbor. This method visit every node in the graph by the time the search is done. Some of the tree traversal is a form of DFS.

The following pseudocode implements DFS:

void search(node *root){
    if(root == NULL)
        return;
    visit(root);
    for each (node n in root.adjacent){
        if(n->visited == false){
            search(n);
        }
    }
}

Breadth First Search(BFS)

In BFS, all the neighbors of each node are visited before visiting other nodes. This is more of searching level-by-level starting from a node. In order to keep track of the nodes that already been visited in this case we use queue. The following pseudocode implements BFS:

void search(node *root){
    queue <node*> nodeQ;
    root->marked = true;
    nodeQ.push(root);
    
    while(!nodeQ.empty()){
        node newNode = nodeQ.pop();
        visit(newNode);
        for each (Node n in r.adjacent){
            if(n->marked = false){
                n->marked = true;
                nodeQ.push(n);
            }
        }
    }
}

Shortest Path in Graph

Shortest path problems is one of the most common problems that have different applications such as map navigations, robot navigation, urban traffic controlling… Some of the well-known algorithms that are helpful in finding the shortest path between nodes in a graph are Dijkstra and Bellman Ford. Both of these algorithms are using the relaxation operation. The relaxation procedure takes two nodes as arguments and an edge with weight connecting these nodes. If the distance from the source to the first node plus the edge length is less than distance to the second node, than the first node is denoted as the predecessor of the second node and the distance to the second node is recalculated. Otherwise no changes are applied.

Dijkstra Algorithm

This is the most common algorithm in finding the shortest path. It can be used for both directed and undirected graphs, which makes it convenient for use. The algorithm is a version of breadth first search but in this case we have weighted edges. Below is the pseduocode implementation of Dijkstra:

Dijkstra{
    PQ.push((0,sourceVertex))
        while !PQ.empty()
            if the front pair is invalid, skip
                for each neighbor v of u = PQ.front()
                    relax(u, v, w(u, v)) + insert new pair to PQ
}

Bellman Ford Algorithm

This is another algorithm that is used to find the shortest path in problems where it can detect a graph with negative cycles. Comparing with Dijkstra algorithm, Bellman Ford is slower but the fact that can detect the negative weight cycle, it made the algorithm more versatile. The following pseduocode implements the Bellman Ford:

Bellman_Ford{
    for i = 1 to |V|-1
        for each edge(u, v) in E
            relax(u, v, w(u, v))
    for each edge(u, v) in E
        if can still relax that edge, -∞ cycle found
}

In contrast, the bellman ford algorithm is more versatile than Dijkstra since it can detect the negative weight cycles in a graph. The bellman ford algorithm is following the Dynamic Programming principle which can help with the complexity but on the other hand Dijkstra is following the Greedy Algorithm principle that not necessarily can give us the optimal solution but can have a lower complexity.

The following link will walk you through a visual example for both Dijkstra and Bellman Ford Algorithm: https://visualgo.net/sssp