Graphs: Presented By, M.Sangeetha, Ap/Cse, Kongu Engineering College

Graphs
Presented By,
M.Sangeetha,
AP/CSE,
Kongu Engineering College
 A Graph is a data structure that consists of
the following two components:
1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u,
v) called as edge. ((u, v) indicates that there
is an edge from vertex u to vertex v)
 The edges may contain weight/value/cost.
 A graph G is represented as G = ( V , E ),
where V is set of vertices and E is set of

edges.
 Undirected Edge - An undirected edge is a
bidirectional edge. If there is undirected edge
between vertices A and B then edge (A , B) is
equal to edge (B , A).
 Directed Edge - A directed edge is a
unidirectional edge. If there is directed edge

between vertices A and B then edge (A , B) is
not equal to edge (B , A).
 Weighted Edge - A weighted edge is a edge
with value (cost) on it.

 Undirected Graph - A graph with only
undirected edges is said to be undirected
graph.
 Directed Graph - A graph with only directed
edges is said to be directed graph.

 Mixed Graph - A graph with both undirected
and directed edges is said to be mixed graph.

 Degree - Total number of edges connected to
a vertex is said to be degree of that vertex.

 Indegree - Total number of incoming edges
connected to a vertex
 Outdegree - Total number of outgoing edges
connected to a vertex
Simple Graph
 A graph is said to be simple if there are no
parallel and self-loop edges.
Path
 A path is a sequence of alternate vertices
and edges that starts at a vertex and ends at

other vertex such that each edge is incident
to its predecessor and successor vertex.
Parallel edges or Multiple edges
If there are two undirected edges with same end vertices and two
directed edges with same origin and destination, such edges are called
parallel edges or multiple edges.
Self-loop
Edge (undirected or directed) is a self-loop if its two endpoints coincide
with each other.
• A directed graph is strongly connected if there
is a path from every node to every other node.
• A directed graph is weakly connected if,
treating all edges as being undirected, there is
a path from every node to every other node.
DAG: A directed graph that has no cyclic paths is called a DAG (a
Directed Acyclic Graph).
Complete Graph : Every node should be connected to all other nodes

in the graph.
Representation of graphs:
1. Adjacency Matrix
2. Adjacency List
Adjacency Matrix
In this representation, the graph is represented using a matrix of
size total number of vertices by a total number of vertices.
Adjacency List
 In this representation, every vertex of a graph
contains list of its adjacent vertices.

Graph Traversal
 It refers to the process of visiting each vertex
in a graph.
 There are two graph traversal techniques and
1. DFS (Depth First Search)

2. BFS (Breadth First Search)
Dept-First search (DFS):
 In the depth –first search traversal, we back
track on a path once it reached the end of the

path.
 DFS traversal of a graph produces a spanning
tree as final result. Spanning Tree is a graph

without loops.
 We use Stack data structure with maximum
size of total number of vertices in the graph

to implement DFS traversal.
Algorithm
 Step 1 - Define a Stack of size total number
of vertices in the graph.

 Step 2 - Visit the adjacent unvisited vertex.
Mark it as visited. Display it. Push it in a

stack.
 Step 3 − If no adjacent vertex is found, pop
up a vertex from the stack. (It will pop up all

the vertices from the stack, which do not
have adjacent vertices.)
 Step 4 − Repeat Step 2 and Step 3 until the
stack is empty.
BFS (Breadth First Search)
 Queue data structure with maximum size as
total number of vertices in the graph .

Algorithm:
 Step 1 - Define a Queue of size total number of
vertices in the graph.

 Step 2 - Visit the adjacent unvisited vertex.
Mark it as visited. Display it. Insert it in a queue.

 Step 3 − If no adjacent vertex is found, remove
the first vertex from the queue.

 Step 4 − Repeat Step 2 and Step 3 until the
queue is empty.
Shortest Path Algorithm
Single source shortest path algorithm
(Dijkstra’s Algorithm)
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Example 2
Spanning Trees
 A spanning tree is a sub-graph of an
undirected and a connected graph, which
includes all the vertices of the graph having a
minimum possible number of edges(Forms
no cycle)
Graph Spanning Tree

Minimum Spanning Tree (MST)
 Undirected graph
 MST - Tree formed from graph edges that
connects all vertices at lower cost

 Forms no cycle – acyclic
 Algorithms:
◦ Prim’s Algorithm
◦ Kruskals Algorithm
EXAMPLE
Prim’s Algorithm
 Prim's algorithm starts with the single node
and explore all the adjacent nodes with all
the connecting edges at every step.
 The edges with the minimal weights causing
no cycles in the graph got selected.

Kruskal's Algorithm
 Kruskal's Algorithm is used to find the
minimum spanning tree for a connected
weighted graph.
 Follows greedy approach which finds an
optimum solution at every stage.

 Select the edges in order of smallest weight
and accept an edge if it does not cause a

cycle
Example

Graphs: Presented By, M.Sangeetha, Ap/Cse, Kongu Engineering College

Uploaded by

Copyright:

Graphs: Presented By, M.Sangeetha, Ap/Cse, Kongu Engineering College

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Graphs: Presented By, M.Sangeetha, Ap/Cse, Kongu Engineering College

Uploaded by

Copyright:

Graphs

where V is set of vertices and E is set of

unidirectional edge. If there is directed edge

with value (cost) on it.

edges is said to be directed graph.

and directed edges is said to be mixed graph.

a vertex is said to be degree of that vertex.

parallel and self-loop edges.

and edges that starts at a vertex and ends at

Complete Graph : Every node should be connected to all other nodes

contains list of its adjacent vertices.

1. DFS (Depth First Search)

track on a path once it reached the end of the

tree as final result. Spanning Tree is a graph

size of total number of vertices in the graph

of vertices in the graph.

Mark it as visited. Display it. Push it in a

up a vertex from the stack. (It will pop up all

total number of vertices in the graph .

vertices in the graph.

Mark it as visited. Display it. Insert it in a queue.

the first vertex from the queue.

Graph Spanning Tree

connects all vertices at lower cost

no cycles in the graph got selected.

optimum solution at every stage.

and accept an edge if it does not cause a

You might also like