DAY 6
GRAPHS
VRITIKA NAIK
LinkedIn: Vritika Naik
Twitter: @NaikVritika
TOPICS COVERED
• Graph Terminology
• Graph Representation – Matrix, List
• Graph Traversal – BFS, DFS
• Shortest path problem – Dijkstra, Bellman Ford
• Minimum Spanning tree – Prims, Kruskal
GRAPHS
• Graph G = (V,E) is a
collection of sets V and E
where V is the collection of
vertices and E is the
collection of edges.
• Edge: (i,j) where i,j are
vertices
• Graph can be directed or
undirected
Weight
TERMINOLOG
Y
Vertex
Edge
Subgraph
TERMINOLOGY (continued…)
• Degree: Number of edges incident on a
vertex
• Indegree: Number of edges entering the Pendant
vertex v Vertex
• Outdegree: Number of edges exiting
vertex v
• Pendant Vertex: If indegree=1 and
outdegree=0
• Isolated Vertex: Outdegree=0 Source
Sink
• Complete Graph: Every vertex is adjacent to
every other vertex
• Multigraph: Contains loops or multiple edges
• Simple Graph: Does not have loops or
TYPES OF multiple edges
GRAPHS • Regular Graph: Every vertex is adjacent to
same number of vertices
• Planar Graph: Can be drawn in a plane
without any 2 edges intersecting
• Null Graph: Has only isolated vertices
REPRESENTATIO • Adjacency Matrix
N OF GRAPH • Adjacency List
ADJACENCY MATRIX
• Maintains info of adjacent vertices
• A(i,j) = {1, if there is an edge from i to j
{0, if there is no edge from i to j
• If a graph has weights on its edges, then:
A(i,j) = {w, if there is an edge from i to j
{0, if there is no edge from i to j
ADJACENCY LIST
• We maintain 2 linked lists
• First: Vertex List
• Second: Edge List
GRAPH TRAVERSAL
Why is graph traversal different from tree traversal?
- There is no root vertex in graph.
- In graph, it is possible for some elements to be not
visited.
- We might encounter a vertex more than once.
- Traversal from different vertices give different
sequences.
There are two main traversals:
• Breadth first Search
• Depth First Search
BREADTH FIRST SEARCH
1. Initially, queue is empty, and all vertices are in initial state
2. Insert the starting vertex into the queue and change its state to waiting
3. Delete front element from the queue and visit it, change its state to visited.
4. Look for the adjacent vertices of the deleted element, and from these insert only
those vertices into the queue which are in initial state. Change the state of all
vertices from initial to waiting.
5. Repeat steps 2, 3 until the queue is empty.
DEPTH FIRST SEARCH
Initially stack is empty, and all vertices are in initial state
1) Push starting vertex on the stack.
2) Pop a vertex from the stack
3) If popped vertex is in initial state, visit it and change its state to visited. Push all
unvisited vertices adjacent to the popped vertex.
4) Repeat steps 2 and 3 until stack is empty.
SHORTEST PATH PROBLEM
In a weighted graph, shortest path is one in which sum of weights of the included
edges is the minimum.
• Dijkstra’s Algorithm: Single source, non-negative weights
• Bellman Ford Algorithm: Single Source, general weights
• Floyd’s Algorithm: All pairs shortest paths
DIJKSTRA’S ALGORITHM
1) Initialize the pathLength of all vertices to be infinity and predecessor of all vertices to NIL. Make the status of all vertices
temporary.
2) Make the pathlength of source vertex equal to 0.
3) From all the temporary vertices in the graph, find out the vertex that has minimum value of pathLength, make it
permanent and now this is our current vertex. If there are more than one, select any.
4) Examine all the temporary vertices adjacent to the current vertex. The value of pathLength is recalculated for all these
temporary successors of current, and relabelling is done if required.
• If pathLength(current) + weight(current, v)<pathLength(v)
pathLength(v)=pathLength(current)+weight(current,v)
predecessor(v)=current
• If pathLength(current) + weight(current, v)>=pathLength(v)
NO relabelling and predecessor remains unchanged.
5) Repeat steps 3 and 4 until there is no temporary vertex left in the graph, or all the temporary vertices left have pathLength
of infinity.
BELLMAN FORD ALGORITHM
1) Initialize the pathLength of all vertices to infinity and predecessors of all vertices to
NIL.
2) Make the pathLength of source vertex equal to 0 and insert it into the queue.
3) Delete a vertex from the front of the queue and make it the current vertex.
4) Examine all the vertices adjacent to the current vertex. Check the condition of
minimum weight for these vertices and do the relabelling if required.
5) Each vertex that is relabelled is inserted into the queue provided it is not already
present in the queue.
6) Repeat steps 3, 4 and 5 till the queue becomes empty.
SPANNING TREE
MINIMUM SPANNING TREE
PRIM’S ALGORITHM
1) Initialize the lengths of all vertices to infinity and predecessors of all vertices to NIL. Make the status of all vertices temporary.
2) Select any arbitrary vertex as the root vertex and make its length label equal to 0.
3) From all the temporary vertices in the graph, find out the vertex that has the smallest value of length, make it permanent and
now this is our current vertex.
4) Examine all the temporary vertices adjacent to the current vertex. Suppose current is the current vertex and v is a temporary
vertex adjacent to the current.
• If weight(current,v)<length(v)
Relabel vertex v
Length(v) = weight(current, v)
Predecessor(v) = current
• If weight(current, v)>=length(v)
No relabelling is done
5) Repeat steps 3 and 4 till there are no temporary vertices left. If the graph is connected, the procedure will stop. Otherwise, there
will be unreachable temporary vertices remaining, and hence no spanning tree is possible.
KRUSKAL’S 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 there are (V-1) edges in the spanning tree.
Formula:
Father[root_v2]=root_v1
VRITIKA NAIK
LinkedIn:
Vritika Naik
Twitter:
THANK YOU!
@NaikVritika
