Getting Started With Graphs š
Graphs are one of the most important and frequently used data-structures in Computer Science. They are used in many applications that we use daily like Facebook, Google Maps, Airline Networks, Recommendations Engine and many other use cases which areĀ essentialĀ inĀ ourĀ dailyĀ lives.
WHAT ARE GRAPHS
Graphs, in the simplest of terms, are just some collection of nodes connected by some edges. We usually denote graphs as set of vertex and edges by the notation ā G = (V,E).
If you know about trees, you can consider Graphs to be Trees with fewer restrictions. A graph is a superset of Trees where there are no rules like non-existence of cycle.
Lets dive in more into Graphs by looking at their types.
TYPES OF GRAPH
- Directed And Undirected Graphs ā Directed Graphs refer to graphs in which there is an edge from node A to node B (in Graphs,Vertex are also called as Nodes). Undirected Graphs are those in which there is an edge from Node A to Node B and the same edge also implicitly specifies that the edge connects Node B to Node A
- Weighted And Unweighted Graphs ā A Graph in which edges are given weights are known as Weighted Graphs. A graph where edges are specified without assigning weights to them are called Non-Weighted or Unweighted Graphs.
- Sparse And Dense Graphs ā When the number of edges in a graph is more, we call it as Dense Graphs and when the number of edges are less, they are known as Sparse Graphs. There are at max VĀ² number of edges possible in a Graph. So, we generally call a graph having edges close to VĀ² as Dense Graph and vice-versa.
We probably have encountered graphs in Mathematics in our school or colleges. Graphs in Computer Science are similar to it with few differences when it comes to how we represent a Graph. Lets see how we represent Graphs in computers and the different types.
REPRESENTATION OF A GRAPH
There are two ways in which we can represent our graph ā
- Adjacency-Matrix Representation : In this form of representation, we use a V x V matrix to represent the graph. Each cell of the matrix will either specify if an edge exists between two vertex (in case of Non-weighted Graphs) using 1-edge present or 0-edge absent, or specify the weight of edge between two vertex(in case of Weighted Graphs).
- Adjacency-List Representation : In this form of representation, for each node we use a list to represent all the nodes connected to it. So, we are maintaining an array of V lists, where each of the list will specify all the nodes connected to the corresponding numbered node.
Now that we know how graphs are formed and represented, the next step to understand is how we use them. Obviously, we construct a graph to use it sometimes in the future and to use a graph, we must explore it or more formally, Traverse the Graph. Lets look at the different Traversal Techniques available.
Graph Traversal š£ļø
- Breadth-First SearchāāāThis is a standard Graph Traversal algorithm in which we start traversing from a certain start or source node and traverse the graph layer-wise, thus exploring each of the neighbour nodes (nodes which are directly connected to source node). Then we move towards the next-level neighbour nodes and repeat the same procedure until we have traversed all graph.
Pseudocode -
BFS (G, s) //Where G is the graph and s is the source node
let Q be queue.
Q.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.
mark s as visited.
while ( Q is not empty)
//Removing that vertex from queue,whose neighbour will be visited now
v = Q.dequeue( )
//processing all the neighbours of v
for all neighbours w of v in Graph G
if w is not visited
Q.enqueue( w ) //Stores w in Q to further visit its neighbour
mark w as visited.- Depth-First Search ā This is another well-known Graph traversal algorithm in which we recursively traverse one branch of the starting node all the way down before moving on to the next one. Once we reach the last node of a branch, we backtrack to find the next nodes to traverse.
Pseudocode -
DFS(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS(G, w)You can get a better idea on how these algorithms work by checking out some Graph visualizer tools available online. I have posted two simple graph traversal animations below which would help in better understanding how traversal works ā
š CONCLUSION
At first, Graphs and these algorithms may feel intimidating, but implementing these algorithms is easy once we understand the way they work. Graph is one of the topics in Computer Science where many people face difficulty in grasping the ideas and concepts behind it. But once you get started with it and have enough hands-on practice with them, you will surely start getting the core concepts behind them and implementing them would be easy.
Graphs are a powerful data-structure used in various aspects of our Life and Technology. Thereās still a lot to learn in Graphs and Graph theory. Hopefully, this article would have cleared the basic concepts related to Graphs and help you get started with them š.
