UNIT V
UNIT V
UNIT V
GRAPH STRUCTURE
A graph is a pictorial representation of a set of objects where some pairs of objects are
connected by links. The interconnected objects are represented by points termed as vertices,
and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges,
connecting the pairs of vertices. Take a look at the following graph −
Undirected Graph
A graph in which edges do not have any direction. That is the nodes are unordered pairs in the
definition of every edge.
Complete Graph
The graph in which from each node there is an edge to each other node.
Connected Graph
The graph in which from one node we can visit any other node in the graph (at least there is a
path from each node to all other nodes) is known as a connected graph.
Weighted Graph
A graph in which the edges are labelled by an numeric value then the graph is said to be
weighted graph.
Indegree
It is calculated as the number of edges entered to the vertex
Outdegree
It is calculated as the number of edges leaving from the vertex.
Note:
In an Undirected Graph indegree and outdegree value of a vertex is same.
Graph Representation
Graphs are commonly represented in two ways:
● Adjacency Matrix
● Adjacency List
Adjacency Matrix
An adjacency matrix is a 2D array of V x V vertices. Each row and column represent a vertex.
If the value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i and
vertex j. The adjacency matrix for the graph we created above is
Since it is
an
undirected graph, for edge (0,2), we also need to mark edge (2,0); making the adjacency matrix
symmetric about the diagonal. Edge lookup(checking if an edge exists between vertex A and
vertex B) is extremely fast in adjacency matrix representation but we have to reserve space for
every possible link between all vertices(V x V), so it requires more space.
Adjacency List
An adjacency list represents a graph as an array of linked lists. The index of the array
represents a vertex and each element in its linked list represents the other vertices that form an
edge with the vertex. The adjacency list for the graph we made in the first example is as
follows:
An adjacency list is efficient in terms of storage because we only need to store the values for
the edges. For a graph with millions of vertices, this can mean a lot of saved space.
Graph Traversal
Visiting each node by exactly only once in a Graph is called Graph Traversal. There are two
types
● Breadth First Search (BFS)
● Depth First Search (DFS)
Breadth First Search (BFS)
Breadth First Search (BFS) algorithm traverses a graph in a breadth ward motion and uses a
queue to remember to get the next vertex to start a search, when a dead end occurs in any
iteration.
As in the example given above, BFS algorithm traverses from S to A to B to C first then D to E
to F lastly to G. It employs the following rules.
● Rule 1 – Display Start vertex and say visited. Identify all its adjacent vertices
move to queue.
● Rule 2- See front vertex of the queue, if it is not visited move to visited and
display then find its adjacent vertices insert it into a queue.
● Rule 3 − Repeat Rule 2 until the queue is empty.
BFS Example
Let's see how the Breadth First Search algorithm works with an example. We use an undirected
graph with 5 vertices.
We start from vertex 0, the BFS algorithm starts by putting it in the Visited list and
putting all its adjacent vertices in the queue.
Next, we visit the element at the front of queue i.e. 1, check for visited, It is not yet
visited
we can display and move to visited list. Find its adjacency vertices move to rear end of
the queue.
Vertex 2 has not yet visited make it visited and display it then find its adjacent vertices i.e.
vertices 4,1,0 move to rear end of the queue.
Vertex 3 has not yet visited so mark it has visited, display it and move its adjacent vertices 0 to
the rear end of the queue.
Now Front of the queue 2,0 already visited so simply removed from the queue, now front of the
queue become 4 not yet visited mark it has visited, display and find its adjacent vertices to the
queue.
In this stage all the vertices in the queue are simply removed because of all vertices have been
visited already.
Python Code:
class BFS:
def __init__(self,no_of_vertices=7):
self.vertices=no_of_vertices
self.graph=[[] for _ in range(self.vertices)]
self.visited=[]
def create(self):
for i in range(self.vertices):
ch=input("If you have adjacent vertex for " +str(i)+ " give y or n")
if ((ch=='Y') or (ch=='y')):
print("Enter the list of adjacent vertices of " + str(i)+ " seperated by space")
self.graph[i]=[int(x) for x in input().split()]
else:
self.graph[i]=None
def traversal(self):
queue=[]
self.visited.append(0)
print("Traversal Order is",0,end=' ')
for j in self.graph[0]:
queue.append(j)
for i in queue:
if i not in self.visited:
self.visited.append(i)
print(i,end=' ')
if self.graph[i]!=None:
for j in self.graph[i]:
queue.append(j)
b=BFS(5)
b.create()
b.traversal()
We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting
one of its adjacent vertices in the stack.
Next, we visit the element at the top of stack i.e., 1, marked it has visited and
display. Identify one of the adjacent vertices of 1 and not yet visited is pushed into the stack
i.e.,2.
Next, we visit the element at the top of stack i.e., 2, marked it has visited and display. Identify
one of the adjacent vertices of 2 and not yet visited is pushed into the stack i.e.,4.
Now top of the stack contains vertices which does not have any more unvisited adjacent
vertices, so they are all removed, till we have one of the unvisited adjacent vertex 3 for start
vertex 0.
Now 3 is top of the stack it is visited and displayed also popped from the stack because it does
not have any more unvisited adjacent vertices.
Python Code:
class DFS:
def __init__(self,no_of_vertices=7):
self.vertices=no_of_vertices
self.graph=[[] for _ in range(self.vertices)]
self.visited=[]
def create(self):
for i in range(self.vertices):
ch=input("If you have adjacent vertex for " +str(i)+ " give y or n")
if ((ch=='Y') or (ch=='y')):
print("Enter the list of adjacent vertices of " + str(i)+ " seperated by space")
self.graph[i]=[int(x) for x in input().split()]
else:
self.graph[i]=None
b=DFS(5)
b.create()
b.traversal(0)
A DAG is always topologically ordered, i.e. for each edge in the graph, the start vertex of the
edge occurs earlier in the sequence than the ending vertex of the edge
Topological Order
In a directed acyclic graph, we can possibly order the vertices based on the edges only
entering the vertex whose indegree value is zero will be coming first followed by removing that
vertex along with its adjacent vertices edges alone, again recalculate the indegree value of
remaining vertices repeat the process until all the vertices are ordered.
Example:
Python Code:
class Topological_sort:
def __init__(self,no_of_vertices=7):
self.vertices=no_of_vertices
self.graph=[[] for _ in range(self.vertices)]
self.indegree=[0]*self.vertices
def create(self):
for i in range(self.vertices):
ch=input("If you have adjacent vertex for " +str(i)+ " give y or n")
if ((ch=='Y') or (ch=='y')):
print("Enter the list of adjacent vertices of " + str(i)+ " seperated by space")
self.graph[i]=[int(x) for x in input().split()]
else:
self.graph[i]=None
def find_inorder(self):
for i in range(self.vertices):
if self.graph[i]!=None:
for j in self.graph[i]:
self.indegree[j] +=1
def sort(self):
for i in range(self.vertices):
j=self.indegree.index(0)
print(j,end=' ')
self.indegree[j]=None
if self.graph[i]!=None:
for k in self.graph[j]:
self.indegree[k] -=1
b=Topological_sort(7)
b.create()
b.find_inorder()
b.sort()
Shortest Path
Given a graph and a source vertex in the graph, find the shortest paths from the source to all
vertices in the given graph.
we generate a SPT (shortest path tree) with a given source as a root. We maintain two sets, one
set contains vertices included in the shortest-path tree, other set includes vertices not yet
included in the shortest-path tree. At every step of the algorithm, we find a vertex that is in the
other set (set of not yet included) and has a minimum distance from the source.
Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in the
shortest-path tree, i.e., whose minimum distance from the source is calculated and finalized.
Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as
INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSet and has a minimum distance value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate
through all adjacent vertices. For every adjacent vertex v, if the sum of distance value of u
(from source) and weight of edge u-v, is less than the distance value of v, then update the
distance value of v.
Example:
Python Code:
import sys
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)] for row in range(vertices)]
# Driver program
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]]
g.dijkstra(0)
Spanning Tree
A Spanning tree is a subset to a connected graph G, where all the vertices are connected, i.e,
we can traverse to any vertex from a particular vertex. A spanning tree must not have any cycle
in it. Thus, we can say that if there are n vertices in a connected graph then the no. of edges that
a spanning tree may have is n-1.
Algorithm
There are two algorithms available for finding minimum spanning tree
● Kruskal’s Minimum Spanning Tree
● Prim’s Minimum Spanning Tree
This algorithm will identify the edge with minimum cost as well as adding that edge will not
form a cycle in the result of MST, then we can add such a edge into the minimum spanning
Tree (MST).
Algorithm
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If
cycle is not formed, include this edge. else, discard it.
3. Repeat step 2 until all the edges were evaluated
Example:
Python Code
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def kruskal_algo(self):
result = []
i, e = 0, 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i=i+1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e=e+1
result.append([u, v, w])
self.apply_union(parent, rank, x, y)
for u, v, weight in result:
print("%d - %d: %d" % (u, v, weight))
g = Graph(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 0, 4)
g.add_edge(2, 0, 4)
g.add_edge(2, 1, 2)
g.add_edge(2, 3, 3)
g.add_edge(2, 5, 2)
g.add_edge(2, 4, 4)
g.add_edge(3, 2, 3)
g.add_edge(3, 4, 3)
g.add_edge(4, 2, 4)
g.add_edge(4, 3, 3)
g.add_edge(5, 2, 2)
g.add_edge(5, 4, 3)
g.kruskal_algo()
It starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set
contains the vertices already included in the MST; the other set contains the vertices not yet
included. At every step, it considers all the edges that connect the two sets and picks the
minimum weight edge from these edges. After picking the edge, the vertex which is endpoint
of the edge to be moved to the set containing MST.
Algorithm
1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE.
Assign the key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
….a) Pick a vertex u which is not there in mstSet and has a minimum key value.
….b) Include u to mstSet.
….c) Update key value of all adjacent vertices of u. To update the key values, iterate through
all adjacent vertices. For every adjacent vertex v, if the weight of edge u-v is less than the
previous key value of v, update the key value as the weight of u-v
Example:
Python Code:
import sys
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)] for row in range(vertices)]
g = Graph(5)
g.graph = [ [0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]]
g.primMST()