Updated March 23, 2023
Introduction to Graph in Data Structure
Graphs are non-linear data structures comprising a finite set of nodes and edges. The nodes are the elements, and edges are ordered pairs of connections between the nodes.
Notice the word non-linear. A non-linear data structure is one where the elements are not arranged in sequential order. For example, an array is a linear data structure because it is arranged one after the other. You can traverse all the elements of an array in a single run. Such is not the case with non-linear data structures. The elements of a non-linear data structure are arranged in multiple levels, often following a hierarchical pattern. Graphs are non-linear.
The next word to pay attention to is finite. We define the graph to have a finite and countable number of nodes. This is a rather non-agreeable term. Essentially, a Graph may have an infinite number of nodes and still be finite. For example, a family tree ranging back to Adam and Eve. This is a relatively infinite graph but is still countable and is thus considered finite.
Real-World Example
The best example of graphs in the real world is Facebook. Each person on Facebook is a node and is connected through edges. Thus, a is a friend of B. B is a friend of C, and so on.
Terminologies
Here are the Terminologies of Graph in Data Structure mentioned below
1. Graph Representation: Generally, a graph is represented as a pair of sets (V, E). V is the set of vertices or nodes. E is the set of Edges. In the above example,
V = { A, B, C, D, E }
E = { AB, AC, AD, BE, CD, DE }
2. Node or Vertex: The elements of a graph are connected through edges.
3. Edges: A path or a line between two vertices in a graph.
4. Adjacent Nodes: Two nodes are called adjacent if they are connected through an edge. Node A is adjacent to nodes B, C, and D in the above example, but not to node E.
5. Path: Path is a sequence of edges between two nodes. It is essentially a traversal starting at one node and ending at another. Thus, in the example above, there are multiple paths from node A to node E.
Path(A, E) = { AB, BE }
OR
Path(A, E) = { AC, CD, DE }
OR
Path(A, E) = { AD, DE }
6. Undirected Graph: An undirected graph is one where the edges do not specify a particular direction. The edges are bi-directional.
Example
Thus, the edge AC can be traversed from both A to C and C to A in this example. Similar to all the edges. A path from node B to node C would be either { BA, AC } or { BD, DC }.
7. Directed Graph: A directed graph is one where the edges can be traversed in a specified direction only.
Example
Thus, in the same example, now the edges are directional. You can only traverse the edge along its direction. There is no path from node B to node C now.
8. Weighted Graph: A weighted graph is one where the edges are associated with a weight. This is generally the cost to traverse the edge.
Example
Thus, in the same example, now the edges have a certain weight associated with them. There are two possible paths between node A to node E.
Path1 = { AB, BD, DE }, Weight1 = 3+2+5 = 10
Path2 = { AC, CD, DE }, Weight2 = 1+3+5 = 9
Clearly, one would prefer Path2 if the goal is to reach node E from node A with minimum cost.
Basic Operations on Graph
Here are the Basic Operations of Graph mention below
1. Add/Remove Vertex
This is the simplest operation in the graph. You simply add a vertex to a graph. It need not be connected to any other vertex through an edge. However, you must remove all edges originating from and ending at the deleted vertex when removing a vertex.
2. Add/Remove Edge
This operation adds or removes an edge between two vertices. When all the edges originating from and ending at a vertex are deleted, the vertex becomes isolated.
3. Breadth-First Search (BFS)
This is a traversal operation in the graph. BFS horizontally traverses the graph. This means that it traverses all the nodes at a single level before proceeding to the next level.
The BFS algorithm starts at the top of the first node in the graph and then traverses all the adjacent nodes to it. Once all the adjacent nodes are traversed, the algorithm repeats the same procedure for child nodes.
Example
Traversing the above graph in BFS fashion would result from A -> B -> C -> D -> E -> F -> G. The algorithm starts from node A and traverses all its adjacent nodes B, C and D. It marks all the four nodes as visited. Once all the adjacent nodes of A are traversed, the algorithm moves to the first adjacent node of A and repeats the same procedure. In this case, the node is B, and the adjacent nodes to B are E and F. Next, the adjacent nodes to C are traversed. Once all the nodes are visited, the operation ends.
4. Depth First Search (DFS)
Depth First Search or DFS traverses the graph vertically. It starts with the root node or the first node of the graph and traverses all the child nodes before moving to the adjacent nodes.
Example
Traversing the above graph in BFS fashion would result from A -> B -> E -> F -> C -> G -> D. The algorithm starts from node A and traverses all its child nodes. As soon as it encounters B, it seems that it has further child nodes. So, the child nodes of B are traversed before proceeding to the next child node of A.
Real-World Implementations of Graphs
- Design of electrical circuits for power transmission.
- Design of network of interconnected computers.
- Study of the molecular, chemical and cellular structure of any substance, e.g. Human DNA.
- Design of transport routes between cities and places within a city.
Conclusion – Graph in Data Structure
Graphs are a beneficial concept in data structures. It has practical implementations in almost every field. Therefore, it is essential to understand the basics of graph theory to understand the graph structure’s algorithms.
This article was merely an introduction to graphs. It is just a stepping stone. It is recommended to deep dive further into the topic of graph theory.
Recommended Articles
This is a guide to the Graph in Data Structure. Here we discuss the Terminologies and Basic Operations of Graph in Data Structure. You may also look at the following article to learn more –
