Scribd
Upload
17 views42 pages

Graph Data Structures and Algorithms

The document provides an overview of graph data structures, including definitions and various representation methods such as set representation, adjacency matrix, incidence matrix, linked list, and hybrid representation. It discusses graph traversal techniques like Breadth First Search (BFS) and Depth First Search (DFS), along with their time complexities. Additionally, it covers concepts of spanning trees, minimum spanning trees, and algorithms like Kruskal's, Prim's, and Dijkstra's for graph processing.

Uploaded by

mannuverma83040
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views42 pages

Graph Data Structures and Algorithms

The document provides an overview of graph data structures, including definitions and various representation methods such as set representation, adjacency matrix, incidence matrix, linked list, and hybrid representation. It discusses graph traversal techniques like Breadth First Search (BFS) and Depth First Search (DFS), along with their time complexities. Additionally, it covers concepts of spanning trees, minimum spanning trees, and algorithms like Kruskal's, Prim's, and Dijkstra's for graph processing.

Uploaded by

mannuverma83040
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DSA

Graph

By Ankush Saklecha
Graph
• It is non primitive non linear data structure.
• A graph is collection of non empty set of vertex and set of
edges.

A B

C D
Q. Explain different ways to represent Graph :
Graph representation :
0 1

4 3
1. Set representation :

Vertex Sets
0 1,4
1 0,2,3,4
2 1,3
3 1,2,4
4 0,3
2. Adjacency matrix :
0 1

4 3

0 1 2 3 4
0 0 1 0 0 1
1 1 0 1 1 1
2 0 1 0 1 0
3 0 1 1 0 1
4 1 1 0 1 0
3. Incidence matrix : e1
0 1
e2
e6 2
e5 e4

e3
4 3
e7

e1 e2 e3 e4 e5 e6 e7
0 1 0 0 0 0 1 0
1 1 1 0 1 1 0 0
2 0 1 1 0 0 0 0
3 0 0 1 1 0 0 1
4 0 0 0 0 1 1 1
A B
4. Linked list representation:

C D
5. Hybrid Representation: A B

C D
Draw the directed graph that corresponds to the following adjacency matrix:
Graph traversal technique :
BFS()
1. Breath first search : Using queue {//starting vertex is V.
2. Depth first search Using Stack label vertex v as reached;
initialize Q to be a queue with only V in
it;
0 while (Q is not empty )
1
{
delete a vertex w from the queue;
2 let u be a vertex (if any) adjacent from w;
while(u)
{
4 3 if(u has not been labeled)
{
add u to the queue;
Ready queue label u as reached;
}
u = next vertex that is adjacent to w;
Waiting queue }

Visited node(BFS) }
Graph traversal technique :

2. Depth first search Using Stack DFS(V)


{
0 1 visited [v] =1;
for each vertex w adjancent from v do
{
2
if(visited[w] = 0)
then DFS(w);
}
4 3

Ready queue

STACK:

Visited node(DFS)
Time Complexity of BFS and DFS :

1. If graph is represented through List then O(V+E).


2. if graph is represented using adjancey matrix then O(V2).
1

2 3

4 5 6 7

8
The Breadth First Search algorithm has been implemented using the queue
data structure. One possible order of visiting the nodes of the following graph
is
Consider the following graph,
Topological ordering : if graph is acyclic connected then we can find
topological order.

A C

B D

COMPLEXITY : O(V+E)
Compare Spanning Tree and Minimum Spanning Tree.
Spanning Tree and Minimum Spanning Tree
Kruskal’s Algorithm :
1. Sort all edges in increasing order of weight.
2. Initialize a disjoint-set data structure (Union-Find) where each vertex is its own
set.
3. Pick the smallest edge and check if adding it creates a cycle:
a. If it does not form a cycle, add it to the MST.
b. If it forms a cycle, discard it.
4. Repeat step 3 until MST contains V−1 edges.
Prim’s Algorithm
[Link] from any vertex (usually vertex 0).

[Link] a priority queue (min-heap) to store edges based on their weights.

[Link] the starting vertex as visited and push all its edges into the priority queue.

[Link] until all vertices are included in the MST:

a. Extract the edge with the smallest weight.


b. If the edge connects to an unvisited vertex, add it to the MST.
c. Mark the new vertex as visited and push all its edges into the priority queue.

[Link] when MST contains V−1edges.


Dijkstra Algorithm
Bellman Ford Algorithms :
Thank You
Tell me and I forget. Teach me and I remember. Involve me and I learn.

You might also like