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
