graphs_class Flashcards
What are standard steps to address any graph problem in general?
Build a Graph
Write BFS/DFS
Outer loop to run as many BFS/DFS to explore graph
Given list of edge representations (src, dest), how do we build the Adjacency List representation for given undirected Graph
For each (src, dest) element within the edge list, we need to perform following two operations
adj_list[src].append(dest)
adj_list[dest].append(src)
Given list of edge representations (src, dest), how do we build the Adjacency List representation for given directed Graph
For each (src, dest) element within the edge list, we need to perform following operation adj_list[src].append(dest)
Three requirements/steps to build a graph
Need to know vertices of the graph
Build adjacency list for given list of edges using
for each (src, dest) in edges:
adj_list[src].append(dest)
adj_list[dest].append(src)
and
Initialize visited array with blank/null values
Why is it preferred to represent vertices in convenient Id format 0 to n-1
That would help us using array & use index as the vertex Id, which will eventually enable us to retrieve it’s neighbors in constant time O(1)
Basic BFS template for Graphs
def bfs(source):
queue = deque()
queue.append(source)
visited[source] = 1
while not queue:
node = queue.popleft()
for neighbor in adj_list[node]:
if visited[neighbor] == 0:
visited[neighbor] = 1
queue.append(neighbor)
Basic DFS template for Graphs
def dfs(source):
visited[source] = 1
for neighbor in adj_list[source]:
if visited[neighbor] == 0:
dfs(neighbor)DFS tree from graph produces of which type of edges
DFS tree from graph produces tree edges and back edges.
BFS tree from graph produces of which type of edges
BFS tree from graph produces tree edges and cross edges
Types of Edges in graphs
Tree Edge
Forward Edge
Backward Edge
Cross Edge
Outer loop code/logic for graph BFS/DFS traversal
components = 0
for v in 0 to n-1:
if visited[v] == -1:
components ++
dfs/bfs(v)
return componentsOuter loop code/logic for graph BFS/DFS traversal
components = 0
for v in 0 to n-1:
if visited[v] == -1:
components ++
dfs/bfs(v)
return componentsSum of degrees of all nodes in an undirected graph
twice the number of edges
BFS time complexity on Graphs
O(m+n) where
O(n) - Push and pop of each vertex from Queue
O(m) - Looking at adjacency list of each vertex
Sum of degrees of all nodes in an undirected graph
twice the number of edges
BFS space complexity on Graphs
Auxiliary space: O(n) - number of vertices in queue if source vertex connected to all remaining vertices in worst case
Actual Space: O(n + m)
O(n) - to save vertices information
O(m) - to save edges information
DFS time complexity on Graphs
O(m+n) where
O(n) - Push and pop out of active stack frame for each vertex
O(m) - Looking at adjacency list of each vertex
BFS space complexity on Graphs
Auxiliary space: O(n) - number of vertices in queue if source vertex connected to all remaining vertices in worst case
Actual Space: O(n + m)
O(n) - to save vertices information
O(m) - to save edges information
DFS time complexity on Graphs
O(m+n) where
O(n) - Push and pop out of active stack frame for each vertex
O(m) - Looking at adjacency list of each vertex
DFS space complexity on Graphs
Auxiliary space: O(n) - number of active stack frame entries is height of the tree, which can be O(n) in worst case
Actual Space: O(n + m)
O(n) - to save vertices information
O(m) - to save edges information
When Graph is valid Tree?
If all vertices are connected with no cycles in it
BFS function to detect if there is a cycle or not
def bfs_has_cycle(source):
queue = deque()
queue.append(source)
visited[source] = 1
parent[source] = None
while queue:
node = queue.popleft()
for neighbor in adj_list[node]:
if visited[neighbor] == 0:
visited[neighbor] = 1
parent[neighbor] = node
queue.append(neighbor)
else: # if visited node
if neighbor !=parent[node]: # here check if neighbor is not our own parent
return True # This is cross edge
return False
If there is a cross edge in a tree, can we conclude graph has cycle?
Yes
DFS function to detect if there is a cycle or not
def dfs_has_cycle(node):
visited[node] = 1
for neighbor in adj_list[node]:
if visited[neighbor] == 0:
parent[neighbor] = node
if dfs_has_cycle(neighbor):
return True
else: # if visited node
if neighbor != parent[node]: # here check if neighbor is not our own parent
return True # This is back edge
return False
