PPT for Graph in DS:
Slide 1- Introduction (what is graph?)
Slide 2- Directed and non-directed graph. (with example)
Slide 3- Weighted graph, connected, complete, digraph
Slide 4- Adjacency matrix and Adjacency linked
Slide 5- Minimum spanning tree
Slide 6- Prim’s Algorithm with example
Slide 7- Kruskal Algorithm with example
Slide 8- Dijkstra Algorithm with example
Slide 9- Conclusion
SLIDE 1:
What is graph? -
A graph is a type of non-linear data structure made up of vertices and edges. Vertices are also known as nodes, while
edges are lines or arcs that link any two nodes in the network. In more technical terms, a graph comprises vertices
(V) and edges (E). The graph is represented as G (E, V).
EXAMPLE:
SLIDE 2:
Undirected graph: -An undirected graph is a graph where the edges do not have a specific direction and it is
bidirectional in nature it does not have a parent-child relation concept as there is no particular direction.
Directed graph: -A directed graph is a graph that is unidirectional in this the edges have a specific direction and the
edges have directions specified with them also a directed graph can contain cycles .
EXAMPLE:
SLIDE 3:
Connected Graph - A connected graph is the one in which some path exists between every two vertices (u, v) in V.
There are no isolated nodes in connected graph.
Complete Graph - A complete graph is the one in which every node is connected with all other nodes. A complete
graph contain n(n-1)/2 edges where n is the number of nodes in the graph.
Weighted Graph - In a weighted graph, each edge is assigned with some data such as length or weight. The weight of
an edge e can be given as w(e) which must be a positive (+) value indicating the cost of traversing the edge.
Digraph - A digraph is a directed graph in which each edge of the graph is associated with some direction and the
traversing can be done only in the specified direction.
EXAMPLE:
SLIDE 4:
Adjacency Matrix
A sequential representation is an adjacency matrix.
It's used to show which nodes are next to one another. I.e., is there any connection between nodes in a
graph?
You create an MXM matrix G for this representation. If an edge exists between vertex a and vertex b, the
corresponding element of G, gi,j = 1, otherwise gi,j = 0.
If there is a weighted graph, you can record the edge's weight instead of 1s and 0s.
Adjacency List
A linked representation is an adjacency list.
You keep a list of neighbours for each vertex in the graph in this representation. It means that each
vertex in the graph has a list of its neighbouring vertices.
EXAMPLE
SLIDE 5:
Minimum Spanning Tree: -
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-
weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible
total edge weight.
EXAMPLE
SLIDE 6:
Prim’s Algorithm:
Step 1: Determine the arbitrary starting vertex.
Step 2: Keep repeating steps 3 and 4 until the fringe vertices (vertices not included in MST) remain.
Step 3: Select an edge connecting the tree vertex and fringe vertex having the minimum weight.
Step 4: Add the chosen edge to MST if it doesn’t form any closed cycle.
Step 5: Exit
EXAMPLE
SLIDE 7:
Kruskal Algorithm:
Step 1: Sort all edges in increasing order of their edge weights.
Step 2: Pick the smallest edge.
Step 3: Check if the new edge creates a cycle or loop in a spanning tree.
Step 4: If it doesn’t form the cycle, then include that edge in MST. Otherwise, discard it.
Step 5: Repeat from step 2 until it includes |V| - 1 edges in MST.
EXAMPLE:
SLIDE 8:
Dijkstra Algorithm:
1. Mark the source node with a current distance of 0 and the rest with infinity.
2. Set the non-visited node with the smallest current distance as the current node.
3. For each neighbour, N of the current node adds the current distance of the adjacent node with the
weight of the edge connecting 0->1. If it is smaller than the current distance of Node, set it as the new
current distance of N.
4. Mark the current node 1 as visited.
5. Go to step 2 if there are any nodes are unvisited.
EXAMPLE:
