Graphs Flashcards
BFS
You visit all edges of a given node and only after visiting all the adj nodes, you visit their adjecent nodes. Level by level traversal.
To prevent repetitions we maintain visited array
Push s into q and mark it as visited.
While q is not empty
We pop and enqueue it’s children only if it is not already visited
For multi source bfs and for disconnected components we call bfs on every node if it is not already visited
Number of connected components in a graph
Same as multi source bfs. We maintain a count variable whenever in the main function we call bfs in the for loop if the node is not already visited, we increase the count
Finally return the count
Dfs
You visit a node and you recursively call DFS on each of its adjecent nodes. This results in completely processing the subgraph before moving to the next adjecent
DFS(s,adj[], visited[])
Mark s as visited
Print it
For every v in adj(u)
If not already visited
DFS(v,adj, vis)
Again to take care of disconnected components, we call DFS considering every vertex as source and if it is not already visited
Shortest path in an undirected unweighted graph
Bfs traverses in shortest path possible.
Initialise distance vector to infinity
Dist(s) is 0
Push s into q and mark as visited
Now while q is not empty
Pop
For every adj v of u and not already visited
Dist(v)=dist(u)+1
Mark v as visited
Push v into q
Return dist
Detect cycles in an undirected graph
We use DFS
Visited array alone is not sufficient to give info about cycles but needed anyway to prevent repetitions
We maintain a parent variable
If node is already visited and is parent then ok
If node is already visited and not parent then cycle is present
Dfsrec(adj, s visited parent)
Mark parent as visited
For every adj v of u
If not already visited then call DFS and see if it return true
If already visited and not equal to parent return true
After for loop then return false
Cycle detection in directed graph
The solution for undirected graphs will not work
We use DFS
In DFS recursion stack if there is a back edge then it means cycle is present.
To maintain rescursion stack we maintain bool recSt array
We pop from recSt only after all descendants are processed. This is what helps in disco components as well as 2 arraows ponting to same node cases
We still need visited array to account for disconnected components
Visited (s) as t
RecSt(s) as t
For every u in adj off s
If not already visited then call DFS and if it returns true return true
If already visited and recSt is true then back edge. So return true
RecSt(s) as false
Return false
Topological sorting
Khan’s algorithm
Push all nodes with indegree 0 into the q
Pop a node
Visit its adjecent nodes and decrease their indegree by 1
If indegree become 0 enqueue into q
When in degree is zero it means that it doesn’t depend on any other nodes so it can be done first
Cycle detection in directed graph using Khan’s algorithm
If we processed all vertices then there is no cycle. There is a cycle means they are all dependent on each other and so in topological sorting some of them will not be processed
There won’t be any vertex with degree 0 at some point.
So in Khan’s algorithm we use a count variable to maintain the count of the nodes we processed
If count is equal to v then no cycle
Else cycle
Topological sorting using dfs
Create an empty stack St
For every vertex u do the following
If u not visited call DFS
While stack is not empty pop and print
DFS(u,St)
Mark u as visited
For every adjecent v of u
If v is not visited call DFS(v,St)
Push u onto stack
Shortest path in a weighted directed acyclic graph
The idea is to use topological sorting
Initialise distance vector to infinity
Dist(s) is 0
Find a topological sort of the graph
For every vertex u in topological sort
For every adj v of u
If distance of v >dist(u) + wt
Then update
We use topological sorting because when we are deciding the shortest distance for a given node, we need to know the shortest distances of previous nodes
Minimum spanning tree
Given a weighted connected and undirected graph
Prim’s algorithm
Greedy approach
Initialise key vector to infinity
And mset vector to false
Set key (0) as 0
For count =0 to v
Int u=-1
For i from 0 to v
If (meet(i) is false and key(i) < key of u) then u is i
Mset(u) as t
Res+= key(u)
Now traverse through all adjecents and update their keys
If graph(u,v) not 0 and !mest(v)
Key(v) is min(key(v) and graph(u,v)
Return res
Dijkistra’s single source shortest path algorithm
Undirected and weighted
Initialise distance vector to infinity
Fin vector to false
Mark dist(s) as 0
Picking the minimum from nodes not finalized similar to prim’s
For count =0 to v
U=-1
For i from 0 to v
If fin(i) is false and dist(i) < dist(u) or u is -1
Then u=i
Mark fin(u) as t
Update weights if smaller
For v from 0 to v
If graph(u,v) not 0 and not finalized(v)
Dist(v) is min(dist(v), dist(u)+graph(u,v))
Return dist
Kosaraju’s Algorithm to find strongly connected components
If a set of vertices are connected in such a way that every pair of vertices is reachable from the other, then this set is called a strongly connected component.
Why not use DFS or bfs ? They will work for undirected graphs but not for directed graphs. DFS will call all elements of starting from one node but not from the other
We will get strongly connected components using dfs if we start from sink elements.
Order the vertices in decreasing order of finish times in DFS
Reverse all edges
Do DFS for reversed graph in he order obtained in step 1. For every vertex print all reachable vertices as one strongly connected component.
Implementation of step 1
Create an empty stack St.
For every vertex u do the following
If u not visited
Defsrec(u,St)
While s is not empty pop an item and added to result.
Dfsrec(u,St)
Mark u as visited
For every adj v
If v is not visited
Dfsrec(v,St)
S.push(u)
Why do we need to reverse the graph? Strongly connected components remain strongly connected even when the graph is reversed.
Bellman Ford algorithm
Shortest path from source to all vertices even with negative weight edges
We first find shortest paths that are one edge length away, then shortest paths that are 2 edge lengths away and so on…
We relax all edges v-1 times
For count =0, count d(u)+weight(u,v)
Update
For every edges uv
If d(v)> d(u) +weight(u,v)
Print negative edge cycle found
Articulation points
Articulation points are the points removal of whose vertices and their associated edges increases the number of connected components to more than one.
If root of DFS tree has 2 children then it is an articulation point.
Discovery time - the order in which the nodes are discovered.
Low values- the lowest discovery time reachable from a given node.
If a non root node has a child whose low value is greater then discovery time of this node, then it is an articulation point.
I. E. If no ancestors are reachable from one of its children, the we say that it is an ap.
To take care of such vulnerable points or breaking points we often add edges.
