In this section of the tutorial, we will discuss the use of **Graph in Data Structure** which will include the **types of graph, graph representation, DFS Algorithm, BFS Algorithm, Prim’s Algorithm, Kruskal’s Algorithm** and **its implementation in programs.**

Now let’s move on further to the introduction of **Graphs in Data Structure**.

## What are Graphs in Data Structure?

**Graphs are very useful data structures and they are often used to solve complex routing problems** like designing and routing airlines among the airports they operate into.

Similarly, **they are used in routing messages over a computer network from one to another node**.

Below are some **important terminologies used in graph:**

**Graph:** It is a collection of nodes.

**Vertices:** It is the fundamental unit of building a graph.

**Lines:** It is a collection of segments.

**Adjacent vertices:** They are two connected vertices in a graph joined by a path of length 1.

**Degree of a vertex:** It is the number of lines incident on the vertex.

**Directed graph or digraph:** A graph in which each line has a direction (arrow head) to its successor.

**Undirected graph:** A graph in which there is no direction of any of the lines are present.

**Path:** It is a sequence of vertices where each vertex is adjacent to the next vertex.

**Cycle:** It is a path having at least three vertices that starts and ends with the same vertex.

**Loop:** It is a special case of a cycle where a single arc begins and ends with the same vertex.

### Graph Operations

**These are some basic operations to perform the Graph Operations in Data Structure. Although, any other operation can also be carried out and added to the data structure**.

#### Insert vertex

**This operation adds a new vertex in a graph.**

**When we insert a vertex in a graph, it is disjoint, it is not connected to any other vertex in the list**.- However,
**adding a vertex in the first step of the operation followed by connecting the vertex to other vertices**.

#### Delete vertex

**This operation deletes or removes a vertex from the graph.**

- When a vertex is removed, all the connecting edges are also removed with it.

#### Insert edge

**This operation connects a vertex to a destination vertex.**

- If we come across a situation where
**a vertex needs multiple edges, add an edge must be called once for each adjacent vertex**. **For adding an edge, two vertices must be specified**.- As for a digraph, one of the vertices must be specified as the source and the other as the destination.

#### Delete edge

**This operation deletes or removes one edge from a graph.**

### Graph Traversal Methods

There could be a situation where we need **to visit all the vertices in a graph. Here, we use the graph traversal methods to visit the vertices in a graph**.

Here, we will discuss two standard graph traversal methods, i.e. **depth-first traversal and breadth-first traversal**.

#### Depth-First Traversal

**In depth-first traversal, before we move to an adjacent vertex we process all of a vertex’s descendants.**

**This kind of traversal is mostly used in graphs when the graph is in the form of a tree.**

In the diagram below we can see the **depth-first traversal of a graph**.

**We start by pushing the first vertex, A, into the stack**.- Then we loop and pop the stack.
- After the vertex is processed,
**we push all the adjacent vertices into the stack**. **Once the stack is empty, it means the traversal is completed**.

#### Breadth-First Traversal

**In breadth-first traversal, before we go the next level we process all the adjacent vertices of a vertex.**

In the diagram below we can see the **breadth-first traversal of a graph**.

**We start by enqueuing vertex A in the queue**.- Then we loop and dequeue the queue.
- Then we
**process the vertex from the front of the queue**. - After the processing is done, we place all of its adjacent vertices into the queue.
**Once the queue is empty, it means the traversal is completed**.

### Graph Algorithms

**The nature of the program states what type of graph applications it needs**. So, it sometimes becomes necessary to write a clean algorithm that **returns the vertex count or vertex’s indegree or outdegree or any other purpose**.

Here, we will discuss two such algorithms, i.e. **Prim’s Algorithm and Kruskal’s Algorithm**.

#### Prim’s Algorithm

**Prim’s Algorithm is used to find the minimum spanning tree (MST) of a graph. This algorithm begins with a vertex and keeps on adding edges as we progress into the graph**.

**Prim’s Algorithm Pseudocode**

Algorithm Prim(empty graph) 1 while empty graph is not a MST of graph loop 1 find an edge in graph that is in some MST of the graph, but not in empty graph 2 add edge to graph (unless edge makes a cycle) 2 end loop 3 return empty graph End Algorithm

**We select a random vertex as the starting point**.- Then we initialize a minimum spanning tree.
**We find the edges that connect the other vertices**.- We find the minimum weight and add it to the spanning tree.
**We keep on adding edges until all the vertices are covered**.

#### Kruskal’s Algorithm

**Kruskal’s Algorithm is used to find the MST in a connected graph. The algorithm finds a subset of a graph and forms a tree with every vertex in it. The sum of the weight is minimum among all the spanning trees that can be possibly formed from this graph.**

**Kruskal’s Algorithm Pseudocode**

Algorithm Kruskal(Graph) 1 int edgesAccepted = 0; 2 DisjSet s(NUM_VERTICES); 3 while (edgesAccepted < NUM_VERTICES – 1) 1 edge e = (u, v) 4 uset = s.find(u); 5 vset = s.find(v); 6 if (uset != vset) 1 edgesAccepted++; 2 s.unionSets(uset, vset); End Algorithm

- Here,
**the algorithm first sorts all the edges from the lowest weight to the highest**. - Then the lowest weight of the edge is selected and it is added to the spanning tree.
**If the cycle is created, the edge is discarded**.- Then the edges are kept added until all the vertices are covered.

##### Program example to demonstrate the implementation of Graph Operations

**Code:**

#include <iostream> #include <list> #include <stack> using namespace std; class Graph { int V; list<int> *adj; void Fill_Order(int s, bool visitedV[], stack<int> &Stack); void DFS(int s, bool visitedV[]); public: Graph(int V); void Add_Edge(int s, int d); void display(); Graph transpose(); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::DFS(int s, bool visitedV[]) { visitedV[s] = true; cout << s << " "; list<int>::iterator i; for (i = adj[s].begin(); i != adj[s].end(); ++i) if (!visitedV[*i]) DFS(*i, visitedV); } Graph Graph::transpose() { Graph g(V); for (int s = 0; s < V; s++) { list<int>::iterator i; for (i = adj[s].begin(); i != adj[s].end(); ++i) { g.adj[*i].push_back(s); } } return g; } void Graph::Add_Edge(int s, int d) { adj[s].push_back(d); } void Graph::Fill_Order(int s, bool visitedV[], stack<int> &Stack) { visitedV[s] = true; list<int>::iterator i; for (i = adj[s].begin(); i != adj[s].end(); ++i) if (!visitedV[*i]) Fill_Order(*i, visitedV, Stack); Stack.push(s); } void Graph::display() { stack<int> Stack; bool *visitedV = new bool[V]; for (int i = 0; i < V; i++) visitedV[i] = false; for (int i = 0; i < V; i++) if (visitedV[i] == false) Fill_Order(i, visitedV, Stack); Graph gr = transpose(); for (int i = 0; i < V; i++) visitedV[i] = false; while (Stack.empty() == false) { int s = Stack.top(); Stack.pop(); if (visitedV[s] == false) { gr.DFS(s, visitedV); cout << endl; } } } int main() { Graph g(8); g.Add_Edge(0, 1); g.Add_Edge(1, 2); g.Add_Edge(2, 3); g.Add_Edge(2, 4); g.Add_Edge(3, 0); g.Add_Edge(4, 5); g.Add_Edge(5, 6); g.Add_Edge(6, 4); g.Add_Edge(6, 7); cout << "Connected Vertices:\n"; g.display(); }

**Output:**

Connected Vertices: 0 3 2 1 4 6 5 7

In the upcoming sections of the tutorial, we will **practice programs on Data Structure which will cover topics like Searching, Sorting, Linked List, and Tree**.