Graph
Data Structure
Swetanjali Maharana
Asst. Professor, Dept. CSE
What is Graph
A graph G = (V, E) consists of a finite, nonempty set of vertices V and a set of edges E.
A graph is a set of vertices and a collection of edges that each connect a pair of
vertices.
The edges E = (v, w) which defines the connection between two vertex.
V = {A, B, C, D, E}
E = {(A, B), (A, E), (B, C), (B, D), (E, D), (D, C)}
S Maharana, Asst. Professor, Dept. CSE
Types of Graph
If the edges are ordered pairs (u, v) of vertices, then the graph is said to be directed;
u is called the tail, and v is the head of the edge (u, v).
If the edges are unordered pairs (sets) of distinct vertices, also denoted by (u, v),
then the graph is said to be undirected.
S Maharana, Asst. Professor, Dept. CSE
Types of Graph
In a directed graph G = (V, E), if (v, w) is an edge in E, then vertex w
is adjacent to vertex v. Edge (v, w) is from v to w. The number of
vertices adjacent to v is called the (out-) degree of v.
In an undirected graph G = (V, E), if (v, w) is an edge in E then
assume (w, v) = (v, w), so (w, v) is the same edge. The degree
of a vertex is the number of vertices adjacent to it.
The degree of a vertex is the number of edges incident to it
S Maharana, Asst. Professor, Dept. CSE
Terminologies
Adjacent & Incident
If (v, w) is an edge in an undirected graph,
- v and w are adjacent
- the edge (v, w) is incident on vertices v and w
If <v, w> is an edge in a directed graph,
- v is adjacent to w, and w is adjacent from v
- the edge (v, w) is incident on vertices v and w
S Maharana, Asst. Professor, Dept. CSE
Terminologies
Degree
The degree of a vertex is the number of edges incident to that vertex.
The in-degree of a vertex v is the number of edges that have v as the head.
The out-degree of a vertex v is the number of edges that have v as a tail.
If di is the degree of a vertex i in a graph G with n vertices and e edges, the
number of edges is
S Maharana, Asst. Professor, Dept. CSE
Path
A path in a graph is a sequence of vertices connected by edges
It can connect to 2 or more nodes. Also, if the path connects all the
nodes of a graph in Data Structure, then it is a connected graph,
otherwise, it is called a disconnected graph.
A sequence of edges of the form (v1, v2), (v2, v3), ….. , (Vn-I, Vn).
A path is called a closed path if the initial node is the same as the terminal(end) node.
A path will be a closed path if V0 = Vn, where V0 is the starting node of the graph
and Vn is the last node.
S Maharana, Asst. Professor, Dept. CSE
Path
A simple path is one with no repeated vertices.
A simple graph of ‘n’ nodes and n edges forming a cycle of length ‘n’ is called a cycle
graph.
Each vertex has degree 2. Therefore, they are cycle graphs.
A graph is connected if there is a path from every vertex to every other vertex in the
graph.
A graph that is not connected consists of a set of connected components, which are
maximal connected subgraphs.
The length of a path or a cycle is its number of edges.
S Maharana, Asst. Professor, Dept. CSE
Connected Graph:
A connected graph is a graph in which there is an edge or path
joining each pair of vertices.
Complete Graph:
In a complete graph, there is an edge between every single pair of
nodes in the graph.
Every complete graph is a connected graph, however, vice versa is not
necessary.
Weighted Graph:
In weighted graphs, each edge has a value associated with them
(called weight).
S Maharana, Asst. Professor, Dept. CSE
Graph representation
A graph representation is a technique to store graphs in the memory of the computer.
The following two are the most commonly used representations of a graph.
1. Adjacency List
2. Adjacency Matrix
S Maharana, Asst. Professor, Dept. CSE
Graph representation
Adjacency List
• An adjacency list represents a graph as an array of linked lists.
• The index of the array represents a node.
• Each element in the linked list represents the nodes that are connected to
that node by an edge.
S Maharana, Asst. Professor, Dept. CSE
Graph representation
Adjacency List
S Maharana, Asst. Professor, Dept. CSE
Graph representation
Adjacency List
S Maharana, Asst. Professor, Dept. CSE
Application
Transport Network
Communication Network
Information Network
Social Network
S Maharana, Asst. Professor, Dept. CSE
Graph representation
Adjacency Matrix
• An adjacency matrix is a way of representing a graph as a matrix of Booleans (0's
and 1's).
• A finite graph can be represented in the form of a square matrix on a computer,
where the Boolean value of the matrix indicates if there is a direct path between
two vertices.
S Maharana, Asst. Professor, Dept. CSE
Graph Operation
Graphs support various operations:
Traversal Shortest Path Minimum Spanning Tree
The minimum spanning tree of a
graph using various algorithms
Prim’s algorithm and Kruskal’s algorithm.
The shortest path between two vertices in a graph using
various algorithms Dijkstra’s algorithm and Bellman-Ford algorithm
Traverse the vertices and edges of a graph using various traversal algorithms
depth-first search (DFS) and breadth-first search (BFS)
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Breadth-First Search (BFS): BFS is a graph traversal algorithm that visits all the vertices in a
graph that are reachable from a given starting vertex.
• BFS can be used to find the neighboring locations from a given source location.
• The BFS algorithm can be used as a traversal method to find all the neighboring
nodes, in peer-to-peer networking.
USE
• BFS can be used in web crawlers to create web page indexes.
• BFS is used to determine the shortest path and minimum spanning tree.
• BFS can be used in the Ford-Fulkerson method to compute the maximum flow
in a flow network.
In graph theory, a flow network is a directed
graph where each edge has a capacity and
each edge receives a flow.
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Breadth-First Search (BFS)
Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until QUEUE is empty
Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).
Step 5: Enqueue all the neighbors of N that are in the ready state (whose
STATUS = 1) and set
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Breadth-First Search (BFS)
To avoid processing a node more than once, divide the vertices into two categories:
Visited
A Boolean visited array is used to mark the visited
Not Visited
vertices.
Step 1: Initially queue and visited arrays are empty.
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Breadth-First Search (BFS)
Step 2: Push node 0 into a queue and mark it visited.
Step 3: Remove node 0 from the front of the queue, visit the unvisited neighbors
and push them into the queue.
Step 4: Remove node 1 from the front of the
queue, visit the unvisited neighbors, and push
them into the queue.
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Breadth-First Search (BFS)
Step 5: Remove node 2 from the front of the
queue, visit the unvisited neighbors, and push
them into the queue.
Step 6: Remove node 3 from the front of the
queue, visit the unvisited neighbors, and push
them into the queue.
Steps 7: Remove node 4 from the front of the
queue, visit the unvisited neighbors, and
push them into the queue.
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Depth First Search (DFS): It is a recursive algorithm to search all the vertices of a graph.
• The DFS algorithm can be used to implement the topological sorting.
• DFS can be used to find the paths between two vertices.
• DFS can also be used to detect cycles in the graph.
USE
• DFS algorithm is also used for one solution puzzles.
• DFS is used to determine if a graph is bipartite or not.
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Depth First Search (DFS)
Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting
state)
Step 3: Repeat Steps 4 and 5 until STACK is empty
Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
Step 5: Push on the stack all the neighbors of N that are in the ready state
(whose STATUS = 1) and set their STATUS = 2 (waiting state)
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Depth First Search (DFS)
Step 1: Initially stack and visited arrays are empty.
Step 2: Visit 0 and put its adjacent nodes which are not visited yet
into the stack.
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Depth First Search (DFS)
Step 3: Now, Node 1 is at the top of the stack, so
visit Node 1, pop it from the stack, and put all of its
adjacent nodes that are not visited in the stack.
Step 4: Now, Node 2 is at the top of the stack, so
visit Node 2, pop it from the stack, and put all of its
adjacent nodes that are not visited (i.e., 3, 4) in the
stack.
S Maharana, Asst. Professor, Dept. CSE
Graph Algorithms
Depth First Search (DFS)
Step 5: Now, Node 4 is at the top of the stack, so
visit Node 4, pop it from the stack, and put all of its
adjacent nodes that are not visited in the stack.
Step 6: Now, Node 3 is at the top of the stack, so
visit Node 3, pop it from the stack, and put all of its
adjacent nodes that are not visited in the stack.
S Maharana, Asst. Professor, Dept. CSE
