Data Structure

DCST IV SEMESTER
GRAPH
UNIT 5
5.1 Graph
What is a Graph?
A graph is a non-linear kind of data structure. It is made up of nodes also called as vertices
and edges that connect any two nodes in the graph.
Graph represents the real world problem area such as a network like telephone networks,
circuit networks, and social networks.
For example, it can represent a single user as nodes or vertices in a telephone network,
while the link between them via telephone represents edges.
Graph is shown in the figure 1 below. This graph has:
1. A set of 5 vertices V= { 1,2,3,4,5} and
2. A set of edges E= { (1,2),(1,3),(2,3),(2,4),(2,5),(3,5),(4,50 }.

Figure 1. Graph

Types of Graphs in Data Structures

Graphs can broadly be categorized as:
1. Undirected Graph Fig 2 a: An undirected graph is directionless. This means that the
edges have no directions. In other words, the relationship is mutual. An undirected
graph comprises a set of nodes and links connecting them. The order of the two
connected vertices is irrelevant and has no direction. You can form an undirected
graph with a finite number of vertices and edges. For example, a Facebook or a
LinkedIn connection. Contrarily, edges of directed graphs have directions associated
with them.
1. Directed Fig 2 b: A directed graph also referred to as a digraph, is a set of nodes
connected by edges, each with a direction. An asymmetric relationship between a
boss and an employee or a teacher and a student can be represented as a directed
graph in data structure.
2. Weighted Graph Fig 2c: Graphs can also be weighted, indicating real values
associated with the edges. Depending upon the specific use of the graph, edge
weights may represent quantities such as distance, cost, similarity etc.
Application of Graphs in Data Structures

Following are some applications of graphs in data structures:

 Graphs are used in computer science to depict the flow of computation.

 Users on Facebook are referred to as vertices, and if they are friends, there is an edge
connecting them. The Friend Suggestion system on Facebook is based on graph theory.

 Web pages are referred to as vertices on the World Wide Web. Suppose there is a link
from page A to page B that can represent an edge. This application is an illustration of a
directed graph.

 Graph transformation systems manipulate graphs in memory using rules. Graph

databases store and query graph-structured data in a transaction-safe, permanent
manner.

**************************************************************************

Terminologies of Graphs in Data Structures

Vertices − Interconnected objects in a graph are called vertices. Vertices are also known
as nodes. If two vertices are endpoints of the same edge, they are adjacent.
Edges − It is one of the two primary units used to form graphs. Edges are the links that
connect the vertices.
Directed graph − In a directed graph, edges have direction, i.e., edges go from one vertex to
another.
Undirected graph − In an undirected graph, edges have no direction.
Degree: The total number of edges occurring to a vertex in a graph is its degree.
Out Degree: The out-degree of a vertex in a directed graph is the total number of outgoing
edges,
In-degree: It is the total number of incoming edges.
Source Vertex: A vertex with an in-degree of zero is referred to as a source vertex,
Sink Vertex: one with an out-degree of zero is known as sink vertex.
Tree: A tree is a connected forest. The primary form of the tree is called a rooted tree,
which is a free tree.
Forest: Forest is a graph without a cycle.
Paths: A path is a sequence of non-repeated nodes connected through edges present in a
graph. We can understand a path as a graph where the first and the last nodes have a
degree one, and the other nodes have a degree two.
Cycles: The path that starts and finishes at the same vertex is known as a cycle. Traversing a
graph such that we do not repeat a vertex nor we repeat an edge but the starting and
ending vertex must be same i.e. we can repeat starting and ending vertex only then we get
a cycle.

Here 1->2->4->3->1 is a cycle. Cycle is a closed path.

**************************************************************************
Spanning Tree:

The spanning tree is a sub graph of an undirected connected graph. It includes all the
vertices in the sub graph and the least number of edges that can connect every vertex
without forming a loop or cycle. The spanning tree must have an equal number of vertices
as of the given graph. In the spanning tree, the total number of edges is n-1. Here, n is the
number of vertices in the graph. The edges of the spanning tree may or may not have
weight with them, it depends that the edges of the actual graph have weight or not.

Properties of Spanning Tree

1. A connected graph can have multiple spanning trees. A graph with n vertices can
have an n^(n-2) number of spanning trees.
2. Spanning trees does not have any loop or cycle.
3. Spanning trees have n vertices and n-1 number of edges.
4. All spanning tree of a graph has equivalent vertices.
5. Removing a single edge from the spanning tree will make the graph disconnected as
the spanning tree is minimal connected.
6. Adding any edge can create a loop or cycle in the spanning tree.
7. Spanning trees can be formed on connected graphs only, disconnected graphs
cannot form spanning trees.

Example of Spanning Tree: Consider the following original graph

The following Spanning trees are possible from the above graph:
 Applications of Spanning Tree:

 In routing protocols
 Cluster mapping and analysis
 Network Planning
 Explore the path/ route in the maps.

****************************************************************************

Directed acyclic graphs:

When there are no cycles in a graph, it is called an acyclic graph. It's also known as a
directed acyclic graph (DAG), and it's a graph with directed edges but no cycle. It represents
the edges using an ordered pair of vertices since it directs the vertices and stores some data.

*************************************************************************

Minimum spanning tree algorithm

A spanning tree whose sum of weight (or length) of all its edges is less than all other
possible spanning tree of graph G is known as a minimal spanning tree or minimum cost
spanning tree. The following figure shows a weighted connected graph.
Some possible spanning trees of the above graph are shown below −

Fig (a) Fig (b)

Fig (c) Fig (d)

Fig (e) Fig (f)

 Fig (g)

Among all the above spanning trees, Fig (d) is the minimum spanning tree. The concept of
minimum cost spanning tree is applied in:

1. Travelling salesman problem,

2. Designing electronic circuits,
3. Designing efficient networks, and
4. Designing efficient routing algorithms.

**************************************************************************
 Graph Traversal

Graph traversal is a fundamental operation in computer science used to visit,

search, or update each vertex (node) in a graph. There are several traversal
algorithms, two of the most common being
 Depth-First Search (DFS) and
 Breadth-First Search (BFS).
These algorithms differ in the order in which they visit nodes and the data
structures they use to keep track of visited nodes.

1. Depth-First Search (DFS):

 DFS explores as far as possible along each branch before backtracking.
It traverses deep into the graph before moving to the next branch.
 The standard implementation of DFS uses a stack data structure
(either explicitly or implicitly via recursion) to keep track of vertices to
visit.
 DFS is often used for topological sorting, finding connected
components, and detecting cycles in a graph.
2. Breadth-First Search (BFS):
 BFS explores all the neighbouring nodes at the present depth prior to
moving to the nodes at the next depth level.
 It uses a queue data structure to keep track of vertices to visit,
ensuring that nodes are visited in the order of their distance from the
source node.
 BFS is useful for finding shortest paths in un weighted graphs and for
solving problems where exploring all nodes at a particular depth is
necessary.
In graph theory, Depth-First Search (DFS) is a fundamental algorithm used to
traverse or visit all the vertices (nodes) of a graph. The traversal starts at a chosen
vertex and explores as far as possible along each branch before backtracking.
Key Concepts:
1. Visited Nodes:
 As DFS traverses the graph, it maintains a set of visited nodes to ensure
that each node is visited exactly once.
 Nodes are marked as visited either before or after visiting them,
depending on the specific implementation.
2. Recursion or Stack:
  DFS can be implemented using either recursion or an explicit stack data
structure.
 In the recursive approach, each recursive call explores a neighbor of the
current node until all reachable nodes are visited.
 Alternatively, an explicit stack can be used to simulate the recursion,
pushing and popping nodes as they are visited and backtracked.
3. Backtracking:
 When DFS reaches a dead end (i.e., a node with no unvisited neighbors),
it backtracks to the nearest unexplored branch.
 This process continues until all nodes are visited or until the algorithm
exhausts all possible paths.
A
/\
B C
/\ \
D E F

Starting from node A, DFS would traverse as follows: A -> B -> D -> E -> C -> F.
Here's the high-level DFS algorithm for traversing a graph:
1. Start DFS from a chosen vertex.
2. Mark the current vertex as visited.
3. Recursively visit all adjacent vertices that are not yet visited.
4. Backtrack if necessary until all vertices are visited.

Applications:
DFS has numerous applications in graph theory and computer science,
including:
 Finding connected components in a graph.
 Detecting cycles in a graph.
 Finding paths or routes between nodes.
 Solving problems like topological sorting and finding strongly connected
components.
 Maze solving and puzzle games.

BFS in Graph Theory

In graph theory, Breadth-First Search (BFS) is another fundamental algorithm used to
traverse or visit all the vertices (nodes) of a graph. Unlike Depth-First Search (DFS), BFS
explores all the neighboring nodes at the present depth level before moving to the nodes at
the next depth level.
Key Concepts:
1. Visited Nodes:
 Similar to DFS, BFS maintains a set of visited nodes to ensure that each node
is visited exactly once.
  Nodes are marked as visited when they are dequeued from the queue,
before exploring their neighbors.
2. Queue:
 BFS uses a queue data structure to keep track of the vertices to visit.
 The queue follows the "first in, first out" (FIFO) principle, ensuring that
vertices are visited in the order they were discovered.
3. Level-Based Exploration:
 BFS explores the graph level by level, visiting all vertices at a particular depth
level before moving to the vertices at the next depth level.
 This property makes BFS particularly useful for finding shortest paths in
unweighted graphs.
Example:
Consider the following graph:
mathematica

A
/\
B C
/\ \
D E F

Starting from node A, BFS would traverse as follows: A -> B -> C -> D -> E -> F.
Algorithm:
Here's the high-level BFS algorithm for traversing a graph:
1. Start BFS from a chosen vertex.
2. Enqueue the starting vertex into the queue.
3. Mark the starting vertex as visited.
4. While the queue is not empty, dequeue a vertex and visit all its neighbors.
5. Mark each neighbor as visited and enqueue them if they have not been visited.