Graphs Flashcards
No of edges in directed and undirected graph with V vertices
Undirected: VC2 -> v*(v-1)/2
Directed: 2* vC2
Walk and Path
Path is a simple path or walk with no repeating vertices.
Adjacency Matrix representation
Adding/Removing an edge takes O(1) time. Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1). Find adjacent vertices/ degree of a vertex takes O(V) time.
Cons: Consumes more space O(V^2). Even if the graph is sparse(contains less number of edges), it consumes the same space. Adding a vertex is O(V^2) time.
Adjacency List Representation
Can use dynamic arrays or linked list.
Pros: Saves space O(|V|+|E|) for directed and O(|V|+2|E|) for undirected. In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space. Adding/Removing a vertex is easier O(V).
Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).
Find all adjacent to v: O(deg(V)
Degree of u: theta(1)
BFS
For each V in adj list:
if not visited:
call BFS
BFS: while q is not empty: 1 v = q.pop() and print 2 for each adj u of v: 3 if not visited: q.add (u)
Time: O(V+E) E= v*(v-1)/2. If dense O(E), if sparse: O(V)
line 1: O(V), line 3: O(E)
DFS
Same time complexity as BFS. DFS is always preferred over BFS in maze or similar puzzle like problems because the tree of possible outcomes will keep on growing and with BFS you will reach the final level only after traversing n levels while in DFS you can reach the outcome in O(ht) as well in best case. Also in DFS, you will reach the adjacent of (final-1) node so many more outcomes will be covered.
Applications of DFS
DFS: Path finding, Maze puzzles, Topological sort (Makefile dependencies), Cycle detection, Find SCC.
Applications of BFS
BFS: Shortest path in unweighted graph, web crawling, p2p network, social network, garbage collection, cycle detection, Ford algorithm for maximum flow, broadcasting.
Shortest path in an unweighted graph
We use BFS here. BFS by default visits adjacent nodes which are closest and so on. So we maintain a dist array intialized to INF. dist[source] =0. Then upon visiting u adj of v, we can do dist[u] = dist[v]+1.
Detect Cycle in an undirected graph
Apart from revisiting a node, we also need to make sure that the node is not its parent. We can use BFS and DFS for it. Parent is just a variable passed as argument in rec calls.
Detect Cycle in a directed graph
Here, for each recursive call we need to check if there exist a back edge to any of its ancestor in the same recursion call. We maintain a recSt array initialized to false to maintain if the node belongs to currrent rec stack. In DFS, we set recst[s] = true then visit adj of s and call dfs on them after that we set recSt[s] =false.
Topological Sort (Kahn’s algorithm) using BFS
We need to first store indegree of each vertex in an array or map by traversing through the adjacency list.
Then in a queue keep adding vertices with 0 indegree.
Pop each item and reduce the indegree of its adjacent. When indegree of a vertex becomes 0, then add it to queue. O(V+E) as modified BFS.
Topological sort doesn’t work when there is a cycle in a directed graph.
Cycle detection in Directed Graph (Kahn’s algo)
The idea is that if there is a cycle then the indegree of vertices in the cycle will not be 0 as they depend on each other. So in order to detect cycle, we count the total no of vertices popping out of queue to get the no of vertices with 0 indegree. Once the queue is empty, we check if count is equal to total no of vertices in graph or not. If not then there is a cycle.
Topological Sort using DFS
We create an extra stack and pass it to the recursive calls as parameter. Initially the stack is empty. We push a vertex v to stack once all its adjacent vertices have been visited and the recursion call has return to current vertex. This ensures that a parent node is pushed after all its child have been pushed so the topology is maintained. Now when all vertices have been visited, we print the topological order by popping vertices from top of stack one by one and printing.
Shortest path in a weighted DAG
We can apply a standard shortest path algorithm like dijkstra or bellman ford. In bellman ford, we can do it in O(VE) and dijkstra in O(ElogV). Topological sort can do it in O(V+E).
We first initialize a dist array to INF and dist[s] = 0. Then find the topological sort of the graph. Then we visit the graph in topological order. For each vertex v in topological sort: for each adjacent u of v:
if dist[v] > dist[u] + weight(u,v): update distance.
This algorithm works bcoz we are traversing in topological order so there will be no back edge or back iteration.
