Graphs Flashcards
Count the number of connected components in an undirected graph given its adjacency list.
Maintain a visited set and count.
Loop through the keys of the adjacency list, this is all of your nodes in the graph.
If not in visited, add it to visited and do a DFS. DFS will mark all connected nodes as visited.
Increment count.
Traverse a graph given its edges (list of lists)
Convert edges to to adjacency list:
graph = {i:[] for i in range(n)}
for n1, n2 in edges:
graph[n1].append(n2)
graph[n2].append(n1)
Write a function, shortest_path, that takes in a list of edges for an undirected graph and two nodes (node_A, node_B). The function should return the length of the shortest path between A and B. Consider the length as the number of edges in the path, not the number of nodes. If there is no path between A and B, then return -1.
Breadth first search, but track the distance from the start node within the queue. (node, distance) tuple.
Calculate the distance of next node by adding to distance of current node.
How to solve grid-graph problems?
Don’t convert it into an adjacency list. Just adapt DFS logic to coordinates.
Check index bounds like this:
r_bounds = 0 <= r < len(grid)
c_bounds = 0 <= c < len(grid[0])
if not r_bounds or not c_bounds:
return False
Given an m x n 2D binary grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Go through the entire grid.
Start DFS on each node.
Inside DFS function:
Check if out of bounds as a base case at the beginning of the DFS function.
Check if current coordinates in visited.
DFS through all neighbors.
Return True if all DFS goes through.
O(rc) / O(rc)
STRUCTY
Find the shortest path from a starting coordinate to ending coordinate in a grid-graph.
- Iterative Breadth-first search
- Add coordinate to visited when you add to the queue.
- When you track visited, you CANNOT add the count to visited.
- To reduce repeated code, use a deltaList to track each direction you move to loop through each position.
O(rc) / O(rc)
GENERAL CONCEPT:
Iterative BFS of directed graph given adjacency list.
def bfs(graph):
queue = deque([‘a’])
while queue:
current = queue.popleft()
for char in graph[current]:
queue.append(char)
print(current)
GENERAL CONCEPT:
Iterative DFS of directed acyclic graph given adjacency list.
def dfs(graph):
stack = [‘a’]
while stack:
current = stack.pop()
print(current)
for char in graph[current]:
stack.append(char)
GENERAL CONCEPT:
Recursive DFS of directed acyclic graph given adjacency list and starting node
def dfsRecur(graph, start):
print(start)
for neighbor in graph[start]:
dfsRecur(graph, neighbor)
STRUCTY
Find longest path in a DAG
Keep a distances dict.
Find your endpoint nodes and add them to dict with distance 0.
Recursive DFS:
- if node in distances, return the distance
- track largest distance so far
- recursive call as usual, but set distance if function returns a larger number
- after recursive calls, add starting node to distances with (largest + 1)
- return this distance
Recursive function:
def dfs(graph, start, distances):
if start in distances:
return distances[start]
largest = 0
# traverse the tree from all neighbors of starting node
for neighbor in graph[start]:
attempt = dfs(graph, neighbor, distances)
if attempt > largest:
largest = attempt
distances[start] = 1 + largest
return distances[start]
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Ask yourself if each course can be completed. This depends on the prerequisites. When you go deep enough, you’ll eventually get to a course with no prerequisites (return True). If you find a cycle during this, return False.
- Convert to adjacency list (but don’t flip anything)
- Recursive DFS, tracking visited and removing nodes from adjacency list if they have no neighbors
- if there’s a cycle, return False immediately
- if start has no neighbors, return True
def dfs(start): if start in visited: #cycle return False if graph[start] == []: #node reacheable from endpoint return True visited.add(start) for neighbor in graph[start]: if not dfs(neighbor): return False visited.remove(start) graph[start] = [] return True #you went through all the neighbors and confirmed this node can be visited for node in graph: if not dfs(node): return False return True #all courses can be completed
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}</Node>
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
- Use a hashmap to map old node to new node.
- Recursive DFS
- if node is in hashmap, return the copy
- otherwise copy it, then dfs(neighbors)
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
Check if no cycles and all nodes can be visited.
To check for cycles in undirected graph, track the previous node you were on in dfs function parameters.
If neighbor == prev, continue the loop.
When you return False in the middle of the recursion, YOU MUST DO THIS LOGIC:
for neighbor in graph[start]:
if not dfs(neighbor, graph, start):
return False
return True
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Topological sort
- In the same for loop, convert edges to adjacency lists and make another list counting the number of prereqs each node has.
- Initialize a queue with all nodes that have 0 neighbors.
- Do a BFS, popping from the queue to get current node.
- Go through neighbors of current and decrement its prereq count. If count == 0, add node to the queue.
- numCourses -= 1
- If numCourses == 0 at the end of the BFS, return True.
from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = {i:[] for i in range(numCourses)}
preCount = [0 for i in range(numCourses)]
for node1, node2 in prerequisites:
graph[node1].append(node2)
preCount[node2] += 1
queue = deque()
for i in range(len(preCount)):
if preCount[i] == 0:
queue.append(i)
while queue:
cur = queue.popleft()
for neighbor in graph[cur]:
preCount[neighbor] -= 1
if preCount[neighbor] == 0:
queue.append(neighbor)
numCourses -= 1
return numCourses == 0
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
- Convert the list of words to an adjacency list taking 2 words at a time, take care of the edge case where if you have ‘babbit, bab’ it’s automatically invalid.
- Initialize a result array where the DFS will add each character it visits.
- Initialize a visited dict where you map char : boolean - False means it was visited at some point. True means it was visited and it’s on the current path. If it’s in visited and True, return True immediately because cycle == invalid. Make sure you add True to the dict before the recursive calls. Then change to False after the recursive calls.
- DFS with topological sort - DFS but you add the current char AFTER all the recursive calls (postorder traversal), then reverse the result that you get before returning.
- If you’re doing the Lintcode version, you need to do for char in reversed(sorted(graph.keys())) when you call the DFS function.
