Performance analysis of Graph Theoretic Algorithms

14 min readDec 15, 2020

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the prime objects of study in discrete mathematics.

Let’s discuss some theoretical algorithms here…

1. Breadth-First Search (BFS)

Breadth first search(BFS) is a algorithm that helps graph traversal algorithm. BFS starts traversing the graph from root node and then bfs explores all the adjacent nodes. Then, bfs selects the nearest node to the current node and then explore all the nodes that are unexplored. The algorithm keeps following the process for each of the nearest node unless it finds the goal node.

Breadth First Search (BFS) algorithm explores a graph breadthwise. BFS uses a queue to store next vertex for searching, if a dead end occurs in any iteration while exploring.

Algorithm :

Put any one of the graph’s node at the back of a queue.
Take the first node of the queue and append it to the visited list.
Create a list of that adjacent nodes of that visited node. Append the nodes which aren’t in the visited list, at ending of the queue.
Keep repeating step 2. and step 3. until the queue is empty.

Pseudocode :

create a queue named as Q.

mark node v as visited node and put node v into queue Q.

while Q is non-empty queue.

remove the head node u of Q.

mark and enqueue all (unvisited) adjacent nodes of u.

..Calculate the path from node A to node E using BFS

Adjacency List

A->B,D

B->C,F

C->E,G

G->E

E->B,F

F->A

D->F

Solution:

1. Add node A to start of QUEUE1 and NULL to QUEUE2.

QUEUE1 = [A]

QUEUE2 = [NULL]

2. Delete the Node A from QUEUE1 and insert all its adjacent nodes. Insert Node A into QUEUE2

QUEUE1 = [B, D]

QUEUE2 = [A]

3. Delete the node B from QUEUE1 and insert all its adjacent nodes. Insert node B into QUEUE2.

QUEUE1 = [D, C, F]

QUEUE2 = [A, B]

4. Delete the node D from QUEUE1 and insert all its adjacent nodes. Since F is the only neighbour of it which has been inserted, we will not insert it again in queue. Insert node D into QUEUE2.

QUEUE1 = [C, F]

QUEUE2 = [ A, B, D]

5. Delete the node C from QUEUE1 and insert all its adjacent nodes. Add node C to QUEUE2.

QUEUE1 = [F, E, G]

QUEUE2 = [A, B, D, C]

6. Remove node F from QUEUE1 and add all its adjacent nodes. Since all of its adjacent nodes has already been added, we will not add them again. Add node F to QUEUE2.

QUEUE1 = [E, G]

QUEUE2 = [A, B, D, C, F]

7. Remove E from QUEUE1, all of E’s adjacent nodes has already been added to QUEUE1 therefore we will not add them again. All the nodes are visited nodes and the target node we want E is available into QUEUE2.

QUEUE1 = [G]

QUEUE2 = [A, B, D, C, F, E]

Now by backtracking from node E to node A, using the have all nodes available in QUEUE2.

minimum path according to bfs is A -> B -> C -> E

Time complexity : O(V + E)
Space complexity : O(V).

where V : number of nodes E : number of edges.

BFS Algorithm Applications

To build index by search index
For GPS navigation
Path finding algorithms
In Ford-Fulkerson algorithm for finding maximum flow in a network
Cycle detection in an undirected graph
In minimum spanning tree

2. Depth-First Search (DFS)

Depth first search (DFS) algorithm start with the first node of the given graph, and then goes to deeper until we find the goal node (G) or the a node without children. The dfs algorithm, then backtracks from the dead end to the most recent node which is unexplored.

Depth First Search (DFS) algorithm explores the graph depthwise . Dfs uses a stack to store next vertex for searching, when a dead end is occured in any iteration.

Algorithm :

Start by appending any node on top of a stack.
Take the top node of the stack and append it to the visited list.
Create a list of that node’s adjacent nodes. Add the nodes which aren’t in the visited list, to top of the stack.
Keep repeating step 2. and step 3. until the stack is empty.

Pseudocode

DFS(G, u)

u.visited = true

for each v ∈ G.Adj[u]

if v.visited == false

DFS(G,v)

init() {

For each u ∈ G

u.visited = false

For each u ∈ G

DFS(G, u)

}

Calculate the path from node H to node E using BFS

Adjacency List

A->B,D

B->C,F

C->E,G,H

G->E,H

E->B,F

F->A

D->F

H->A

Solution:

1. Push H onto the stack

STACK = [H]

2. POP the top element of the stack i.e. H, print it and push all the adjacent nodes of H onto the stack that are is ready state.

Print (H)

STACK = [A]

3. Pop out the top node of the stack which is A in this case, print it and push all the adjacent nodes of A onto the stack that are in ready state.

Print (A)

Stack = [B, D]

4. Pop out top node of the stack i.e. node D in this case, print it and push all the adjacent nodes of D into the stack that are in ready state.

Print (D)

Stack = [B, F]

5. Pop the top element of the stack i.e. F, print it and push all the adjacent nodes of F onto the stack that are in ready state.

Print (F)

Stack = [B]

6. Pop the top of the stack i.e. B and push all the adjacent nodes

Print (B)

Stack = [C]

7. Pop the top of the stack i.e. C and push all the adjacent nodes.

Print [C]

Stack = [E, G]

8. Pop the top of the stack i.e. G and push all its adjacent nodes.

Print (G)

Stack = [E]

9. Pop the top of the stack i.e. E and push all its adjacent nodes.

Print (E)

Stack = []

Sequence of the graph: H -> A -> D -> F -> B -> C -> G -> E

Time complexity : O(V + E)

where V : number of nodes , E : number of edges

Space complexity : O(V).

DFS Applications

For finding the path
To test if the graph is bipartite
For detecting cycles in a graph

3. DJIKTRAS ALGORITHM:

Using Dijkstra’s Algorithm, you can find the shortest path between nodes in any graph. Basically, you can find the shortest path from any node (also called as “source node”) to all other nodes in the graph, producing a shortest-path tree.

This algorithm is used in GPS devices to find the shortest path between the current location and the destination considering both as nodes of graph. It has broad applications in industry, especially in domains that require modeling networks.

HISTORY:

This algorithm was created and published by Dr. Edsger W. Dijkstra, an intelligent Dutch computer scientist and a brilliant software engineer/developer.

He published an article in 1959 titled “A note on two problems in connexion with graphs” where he explained his algorithm.

During an interview in 2001, Dr. Dijkstra revealed why and how he designed this algorithm:

“What’s the shortest way to travel from Rotterdam to Groningen? It’s the algorithm for finding the shortest path, which I designed in about 20 -25 minutes. So, One morning I was shopping in Amsterdam with my young lovely fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, but then suddenly spark came I designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959. The publication is still quite nice. One of the reasons that it’s so nice was that I designed it without penl and paper. Without pen and paper you are almost forced to avoid all avoidable complexities. Eventually this algorithm became, to my great amazement, one of the cornerstones of my fame.”

— As quoted in the article Edsger W. Dijkstra from An interview with Edsger W. Dijkstra.

⭐ Unbelievable, right?

In just 20 minutes, Dr. Dijkstra designed one of the most famous and interesting algorithm in the history of Computer Science.

Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) where we consider all edge weights to be nonnegative. Therefore, we assume that weight i.e w(u, v) >= 0 for each edge (u, v) ∈ E. With a good implementation, the running time of Dijkstra’s algorithm can become lower than that of the Bellman-Ford algorithm.

Dijkstra’s algorithm maintains a set S of all vertices whose final shortest-path weights from the source node s have already been determined. The algorithm recurrently selects the vertex u where u ∈ V — S with the minimum shortest-path estimate, and then adds u to S, and then relaxes all edges leaving vertex u. In the following algorithm, we have use a min-priority queue Q of vertices, keyed by their d values.

Algorithm for Djiktras:

DIJKSTRA(G,w,s)

INITIALIZE-SINGLE-SOURCE(G,s)

2. S != Φ

3. Q = G.V

4. while Q != Φ

5. u = EXTRACT-MIN(Q)

6. S = S U {u}

7. for each vertex v ∈ G.Adj[u]

8. RELAX(u, v, w)

TIME COMPLEXITY:

Time Complexity of these implementation is O(V²) But if the input graph is represented using adjacency list , time complexity can be reduced to O(E log V) with the help of binary heap.

4. Topological Sorting

Linear ordering of vertices such that for every directed edge ms from vertex m to vertex s, m comes before s in the ordering is topological ordering of a graph that is directed. This process is impossible if the graph is not directed. In graph theory, a directed graph is a graph where edges connect vertices and these edges have a direction. A topological ordering is useful in the cases where there are constraints as to which task is to be performed first or before some other tasks. Here, the vertices of the graph may represent the task and the edges may represent the constraints or the condition. Another condition for topological ordering is that it should be a directed acyclic graph. Each and every DAG has at least one set of topological ordering which is performed in linear time.

Here node 1 points to node 3 and node 2. So, node 1 comes before them in ordering. Similarly, node 2 and node 3 point to node 4. So, they come before node 4 in the ordering. 1,2,3,4,5 will be the order after topological sorting.

The Algorithm:

Step 1: Identify a node with no incoming edges.

Step 2: Add that node to the ordering.

Step 3: Remove it from the graph.

Step 4: Repeat.

The process is to be repeated until there aren’t any more nodes with indegree zero. This happens because of primarily two reasons:

1. All the nodes are finished. All of them are taken out of the graph and we have added them in our topological ordering.

2. Some nodes are left. These nodes have incoming edges. This means the graph is cyclic and no topological ordering is possible in this case.

Here node B has an indegree 0. Hence it becomes the first element of the topological order. Now B can be removed from the DAG and the similar process can be continued.

Now node E has an indegree of 0. Hence it is next removed from the graph and added to the topological ordering.

Repeating the process, here node A is removed from the graph.

Applications:

The general application of topological ordering is in scheduling a sequence of various jobs depending on their conditions and dependencies. The vertices represent the jobs. There exists an edge from x to y if x is to be finished before y. For example, while coding, the job of writing an algorithm is completed first before writing the actual code. Topological order gives you an actual sequence.

In Computer Science, topological sorting finds its applications mainly in instruction scheduling, logical synthesis, finding the sequence of tasks to perform in make files, data serialization and solving symbol dependencies in linkers.

Topological Sorting also finds its uses in some real-life problems like in trading forex. Currencies have multiple pairs and majority of the trading platforms tell about the percent of traders in long positions vs short ones. If we consider a partial order between currencies weighted along percentages, and if we aggregate this weight on more than one paths between same currencies, it can give some clear currencies widely considered as down or up compared to the volume of the other ones. Of course, topological sorting this DAG is just a hint for opening a possibly long or short position and care must be taken with three timing of going in and especially it is out of the position even after incurring a loss. Research and analysis of GDP growth, current deficit of the account, economy late cycle bringing danger to small currencies, is again another input of the following process. But this definitely is an important application.

Another application is in Django migrations, where migration files are written to create Schema. Here relative ordering becomes an important need.

Uniqueness:

If all pairs of consecutive vertices in sorted orders are joined by edges, then these edges form a directed Hamiltonian path and there exists a unique topological order. Conversely, if a Hamiltonian path is not formed by the topological ordering, then the DAG will have two or more valid topological orderings and also in this situation it is possible to form a second valid ordering by exchanging two consecutive vertices that are not connected. Therefore, in linear time it is possible to check whether a unique ordering is present or not.

Time and Space complexity:

Dividing the algorithm in individual steps:
Determine the incoming nodes whose indegree is zero. This is O(M)O(M) time ( MM is the number of edges), since each directed edge in the graph is looked at once,
Next step is to discover nodes with no incoming edges. This is a simple loop through all the nodes encompassing a few constant-time appends. O(N)O(N) time (where NN is the number of nodes).
Add nodes until we run out of nodes with no incoming edges. This loop could run once for every node — O(N)O(N) times. In the body, we:
Do two constant-time operations on an array to add a node to the topological ordering.
Decrement the indegree for each neighbour of the node we added. We will do exactly one decrement for each edge resulting in step O(M)O(M) time overall.
Check if we included all nodes or found a cycle. This is a fast O (1)O(1) comparison.

Altogether, the time complexity is O(M+N) O(M+N).

This is the fastest time that we can have since every of the vertices and edge has to be visited.

What about space complexity? Here are the data structures we created:

indegrees — this has one entry for each node in the graph, so it’s O(N)O(N) space.
nodesWithNoIncomingEdges — in a graph with no edges, this would start out containing every node, so it’s O(N)O(N) space in the worst case.
topologicalOrdering — in a graph with no cycles, this will eventually have every node. O(N)O(N) space.

All in all, we have three structures and they’re all O(N)O(N) space. Overall space complexity: O(N)O(N).

This is the best space complexity we can expect, since we must allocate a return array which costs O(N)O(N) space itself.

5. FLOYD WARSHAL ALGORITHM

Floyd Warshal also called as Floyd’ algorithm or Roy-Warshal algorithm is an algorithm that is used to find shortest paths in a weighted graph having positive or negative edge weights. We can also detect negative cycles using this algorithm. If the algorithm calculates the distance between the vertex v and itself as negative then the graph is said to have negative cycles.This algorithm can be applied to directed as well as undirected weighted graphs.A graph in which each edge has a numerical value associated with it is called weighted graph.

A one time execution of this algorithm can be used to find the summed weights of shortest paths between all pairs of vertices. By doing some modifications to the algorithm it is possible to reconstruct the paths. This algorithms follows the dynamic approach to find the shortest paths.

Steps followed to find the shortest path between all pairs of vertices.

1.A matrix A0 of dimension n*n is created where n is the number of nodes.The row is indexed as x and column as y. x and y represent the vertices of the graph.The cells in matrix e.g in A[x][y] are filled with the distance from the x vertex to the j vertex.If there is no path between x and y vertex then it is filled by infinity.

2.Now we will create A1 with the help of A0.The elements in first row and first column are not changed and rest of the elements are calculated in the following way

· Let k be the intermediate vertex in the shortest path from source to destination.if A[x][y]>A[x][k]+A[k][y] then A[x][y] is filled with A[x][k]+A[k][y] else it is kept the same.

· In this step,k is in 1 and after each cycle it will get change e.g the direct distannce from vertex 2 to 4 is 4 and the path that goes from 1 i.e from 2 to 1 + 1 to 4 is 7.Since 4<7 so A[2,4] is filled with 4.

3. Similarly, A2 is created using the A1.This time the elements of second column and second row are left as they are. Here the k value will be 2 and the remaining steps are as the same as in step2.

4. After that in the same way A3 and A4 is created.

5. A4 gives us the shortest path between all pairs of vertices.

ALGORITHM:

n = no of vertices

A = matrix of dimension n*n

for k = 1 to n

for i = 1 to n

for j = 1 to n

Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])

return A

Time Complexity

There are three loops. Each loop has constant complexities. So, the time complexity of the Floyd-Warshall algorithm is O(n3).

Space Complexity

The space complexity of the Floyd-Warshall algorithm is O(n2).

APPLICATIONS:-

1.It gives us the shortest path in a directed graph

2.Transitive closure of directed graphs can also be found.

3.It can be also used to find the Inversion of real matrices

4.It is used to test whether an undirected graph is bipartite

SUMMARY

Breadth-First Search (BFS)

Time Complexity: O(V + E)
Space Complexity: O(V)

2. Depth-First Search (DFS)

Time Complexity: O(V + E)
Space Complexity: O(V)

3. DJIKTRAS ALGORITHM

Time Complexity: O(V²) can be reduced to O(E log V)
Space Complexity: O(V2)

4. TOPOLOGICAL SORTING

Time Complexity: O(M+N) O(M+N)
Space Complexity: O(N)O(N)

5. FLOYD WARSHAL ALGORITHM

Time Complexity: O(n3)
Space Complexity: O(n2)

References:

Authors: Shyam Kawale, Nishant Bhat, Bhargav Pawar, Abhijit Gawai
We hope you found this blog interesting, feel free to drop your queries in the comments below. Stay tuned for more!
THANK YOU….