Intro
We use data structures to organize our data. Depending on the structure rules, the process of data manipulation is different. In computer science, we see many types of data structures. And Graph is one of them. It’s one of the most important data structures in computer science. Here, we will know a precise and light overview of Graph data structure.
There are so many real-world use cases of Graph data structure. One good example could be Google Maps. Suppose you want to go from point A to point B. Google Maps shows you the shortest way to reach your destination. And Google uses Graph algorithms to show you the shortest path.
What is Graph?
A graph is a non-linear data structure. In short, a Graph is a collection of Vertices/Nodes and Edges. Nodes are objects, and edges show the relations between objects. We can represent our real-life data using Graph. Let’s think of a basic example of it. Just think of four airports and the distance between them. How can we represent this in a Graph? Here names are nodes, and distances are edges. To understand it better, let’s see a visual representation of it.
As you see above, locations are nodes, and edges show the distances. You can ignore the distance correctness. 🙂
If you know about Tree data structure, you will see trees are more like a Graph. More precisely, a Tree is a type of Graph with some added rules. Just like Binary Trees are the type of Tree with some added rules. Similarly, Binary Search Tree is a type of Binary Tree.
Graph Terminologies
It’s necessary to know some terminology to understand Graph well. It will help you in the future. So let’s see.
Directed and Undirected
Look at the following directed Graph example. There you have a graph of four vertices and edges. In this Graph, you can go from A to B using the edge but can’t come back from B to A. As it specifies the direction using an arrow, it didn’t allow us to do that. Similarly, we can’t traverse from C to B, and so on.
If all the edges are directed, we can call it a Directed Graph or a Unidirectional Graph.
Inversely, if the edges are directed in both ways or without direction, we call that Graph an Undirected or Bidirectional Graph. See the undirected example. In this Graph, you can go from A to B and vice versa.
There can be a Graph with a mix of both.
Adjacent Node
If we can go from node A to node B using an edge, then we can say B is the Adjacent node of A.
In the following example, B is an adjacent node of A, but C is not. And C is an Adjacent node of B as there is a direct edge from B to C. As this is an undirected graph, B is an Adjacent node of both.
Remember, a node can have more than one adjacent node. In the following example, node A has two adjacent nodes.
Weighted and Unweighted
If any value is associated with edges in a Graph, we can identify that Graph as a weighted Graph. This value can be anything related to the Graph. In our first example above, we use edges to describe the distance between two places. And those values are the weight.
Inversely, if no value is associated with edges, we can call it an Unweighted Graph. If there is no defined value, the default weight is one.
Let’s see an example of a Weighted and Unweighted Graph.
Subgraph
A subgraph is nothing but a small portion of a Graph. That can consist of one node or more than one node and edges.
Look at the following example. The highlighted part is a subgraph (D – E – F) of this Graph. Not necessary that it has to be the highlighted one. You can choose another portion too. For example, B – C – D is also a subgraph. A single node can be a subgraph too.
Path
In a Graph, you want to go from one to another node. For example, you want to go from node A to Z. You might need to traverse through some other nodes to reach your destination. So the route you take to travel from node A to node Z, we can call this a path.
It’s not that there has to be at least one node between your starting point to destination to make it a path. There can be no node between a starting point and the destination.
There can also be more than one route/path.
In the following Graph, suppose we want to go from node 1 to node 7. So, starting node is 1, and 7 is the destination. There are three paths to reach node 7. Those are: 1 -> 2 -> 3 -> 7, 1 -> 5 -> 7, 1 -> 4 -> 6 -> 7.
Cycle
Suppose you start traversing from node A, and after visiting some nodes, if you return to node A, we can say it creates a cycle.
Look at the following example. Nodes A, B, and C make a cycle. And A, B, C, and D make a cycle too.
Graph Algorithms
There are many excellent algorithms based on Graph. Using those algorithms, we can solve many Graph related problems. For example, we can use the BFS (Breadth First Search) algorithm to get the shortest path between two nodes. Some most common Graph algorithms are:
- DFS (Depth First Search)
- BFS (Breadth First Search)
- Dijkstra
- Prim’s and Kruskal’s
- Bellman-ford
- Floyd-warshall
- Topological Sort
Final Words
So, that’s a minimal overview of Graph. I hope you got the basic idea about Graph data structure. But this is the tip of the iceberg. It’s a broad topic. I hope this blog will help you to dive into this topic.