Graphs Theory and Algorithms
Written by:
-Jayant Meshram, Ajinkya Mondhe, Akash Nachan, Tejas Nilangekar, Aditya Patil
What are Graphs and why it is such a big deal?
So we all know what graphs are, at least well enough to pass our schools. Speaking in a general context, a graph, is basically what represents the relationship between variables(usually two, but can be more). Now how can an algorithm make use of a graph and why it is important?
To answer that, let us dive into algorithms, theoretically. So an Algorithm, in programming, is a series of instructions told to a compiler to complete a certain task using the resources such as data, data structures, functions, etc. There can be several types of data structures programming languages can make use of, such as Arrays/List(Language Dependent), Linked List, Stacks, Queues, Trees, Heaps, Graphs, etc.
There are two main parts in Graphs:
a. Vertices — Nodes (1,2,3,4,5,6)
b. Edges — Connections(1–2,1–5,2–3,2–5,3–4,4–5,4–6)
Graphs and Graph Theory is the ultimate tool for a programmer. Given a set of nodes & connections, we abstract anything, starting from city layouts to complex computer data. It provides a helpful tool to quantify & simplify the many moving parts of dynamic systems.
And the Theoretical study of Graphs is called a Graph-Theory.
Types of Graphs
Depending on the structure and some of the properties of the graph, they can be divided into several categories.
a. Undirected Graphs:
This is the most simple a graph data structure can be. It Just has the vertices and Edges.
b. Directed Graphs:
Here the Edges have some direction, indicating the next node from the current one.
c. Weighted Graphs:
Here the Edge has some weight to it (can represent anything, cost of traveling from node u ->v, distance, etc.)
d. Directed Acyclic Graphs:
Directed Acyclic Graphs or DAGs, are Directed Graphs, with no Cycle in them.
e. Bipartite Graphs:
Here, the nodes can be divided into two different categories. For eg, set U and set V.
Graph Representation
We Obviously can feed drawn nodes and vertices to the computer and ask it to understand them (although we might try to build a computer vision app to do so, anyways...), so we generally represent Graphs using 3 different types:
- Adjacency Matrix
All nodes are arranged in 2-D Matrix, more like axes, and the weights corresponding to the edge between nodes are represented in the Graph accordingly.
For eg. adj[m][n] = 0
As all the nodes are arranged in a 2-D matrix, the time taken for a query is O(1).
2. Adjacency List
In Adjacency List, we create a key-value pair, the key being a particular node, and the values can be nodes it has a connection with.
Like, eg. {A: ‘B’, ‘C’}
Time taken for running a query is O(|V|).
3. Edge List
In the edge list, we have a list of all the connected nodes in pairs.
(‘A’, ‘B’), (‘A’, ‘C’), etc.
Time taken for running a query is O(|E|).
Common Graph Algorithms:
As we already discussed, graphs are very useful data structures and can be to model various problems. These algorithms have direct applications on Social Networking sites, State Machine modeling, and many more.
Some of the common graph algorithms are:
- Breadth-First Search:
Breadth-First is a Popular search algorithm used to explore nodes and edges of a graph. Particularly it is useful for one thing: finding the shortest path on unweighted graphs. We start with some root node, and keep exploring its neighbors, doing the same for them, until the whole neighborhood is traversed, then move onto the next level.
Generally, it is Implemented by Maintaining Queue.
Input: A graph G and a starting vertex root of G
Output: Goal state. The parent links trace the shortest path back to the root.
It has the time complexity of O(V+E)
2. Depth First Search:
Depth First Search algorithm is also used for traversing or searching tree or graph data structures, but unlike in BFS, we explore Depth-first.
Depth-first search is used in topological sorting, scheduling problems, cycle detection in graphs, and solving puzzles with only one solution, such as a maze or sudoku.
Generally is Implemented using Stack.
1. Initialize all nodes as Unvisited.
2. Push the starting node A into Stack
3. Repeat the following steps until Stack is empty
i. Pop the top node N from Stack and mark N as Visited
ii. Push the neighbors of N that is Not visited on the stack
4. Exit.
Time Complexity:
It has the time complexity of O(V+E)
3. Dijkstra:
Dijkstra’s algorithm is generally used for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
Dijkstra’s original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.
We maintain two sets, one set contains vertices included in the shortest-path tree, other set includes vertices not yet included in the shortest-path tree. Initially, Initialize all distance values as infinity, Then at every step of the algorithm, we find a vertex that is in the other set (set of not yet included) and has a minimum distance from the source.
- Best case time complexity: O(E+V log V)
- Space complexity: O(V)
Apart from this, there are several common algorithms, Such as Prims, Kruskal’s, Floyd Warshall Algorithm, and many more, which can be used to solve different problem Statements.
Graph Theory Applications:
- Path Finding: Maze Problems
DFS and BFS can be used to find the path from the start node to the end node using Graphs.
2. Flight Networks:
For flight networks, efficient route optimizations perfectly fit graph data structures.
Using graph models, airport procedures can be modeled and optimized efficiently.
3. Social Graph (Facebook Graph API) :
On The Graph API, everything is a vertex or node. Graphs allow for a visual display of relationships between sets of entities, where each entity is a node and connections are edges.
Social Graphs uses the measure of centrality. It basically ranks the nodes within a graph corresponding to their network position.
There are several other applications of Graph theory, like Google’s Knowledge Graph, Routing APIs in Google Maps, Logistics and Deliveries, Laying Down Electric Grid, LAN WAN Networks, and many more.
Final Thoughts:
We have looked at all the basic one would need to dive into graph-theoretic algorithms, starting from what are graphs to the real-world applications of Graph Theory. We hope you find this article useful, simple, and well summarized for introduction to Graph-Theoretic Algorithms.
