Graph Problem List

Grid Graph Problem List

Graph

DFS

Find connected components, check for cycles

261. Graph Valid Tree

Undirected graph, check if it’s acyclic and connected.

Using vis[i]=True is sufficient. However, since it’s an undirected graph, when traversing neighbors, you need to skip the parent node, so it needs to be passed as a parameter.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def dfs(i, parent):
    vis[i]=True
    for nxt in g[i]:
        if nxt==parent:
            continue
        if vis[nxt]:
            return False
        if not dfs(nxt, i):
            return False
    return True

For example, 1-3-6, 1-5-6. If connected this way, there must be a cycle, so three colors are not needed.

207. Course Schedule

Directed graph, check if it’s acyclic.

Why must three colors be used?

Because it’s necessary to distinguish: nodes on the current path, and nodes that have already been traversed. For example, 1->3->6 (6 has been traversed). Now traverse 1->5->6 and encounter 5 again. Clearly, there is no cycle here. If True/False is used, both cases would be considered True.

2192. All Ancestors of a Node in a Directed Acyclic Graph

To find all ancestors of a node, you don’t need to carry all visited nodes in the current search during DFS, because we will traverse each node as a starting point. So during the search, we only need to add this starting point to the ancestor list.

DFS condition: when the next node has not been visited in this search, you can traverse it. So each time DFS is called, vis[i] represents the starting point of this search.

After visiting a node, do you need to restore it?

No. For example, 0->3->6, 0->4->6. The second time you reach 6, it’s actually a different path. At this time, 6 is marked as not visited.

When start = 0:

When traversing path 0→3→6, you reach 6 for the first time, satisfying vis[6] != 0. So ans[6].append(0). Then when you backtrack, if you write vis[6] = -1, it’s like erasing the mark “6 has been visited by start=0”.

Back to 0, traverse another path 0→4→6. Again, check vis[6] != 0 (because you restored it to -1), and ans[6].append(0) again - the same ancestor 0 is added twice.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def dfs(i, start):
    # i, start are the current node and the initial ancestor
    # Find all reachable nodes
    vis[i]=start
    for child in g[i]:
        if vis[child]!=start:
            dfs(child, start)
    # Record its ancestor (only record start. Because each node will do one start!)
    if i!=start:
        res[i].append(start)

2101. Detonate the Maximum Bombs

Loop through each node, and search once with this node as the ancestor. And each loop needs a new vis array.

If vis[i]=False is restored at the end of DFS, there will be problems, because for 1-4-6, 1-5-6, the first search to 6 marks it as False, and the second search to it will recount.

721. Accounts Merge

Treat both person names and email names as nodes, the goal is to count the number of connected components.

Build an email_to_account to record which accounts each email belongs to. In one DFS, all accounts belonging to the same person will be marked, and all their emails will be added to a set.

924. Minimize Malware Spread

In an undirected graph, find the largest connected component that is infected and has only one source of infection. Return the size of the connected component. DFS returns three values: connected component size, number of bombs in the connected component, and the index of the bomb in the connected component (returns inf if none).

BFS

Generally, when adding to the queue, set the neighbor’s visited to True.

127. Word Ladder

1311. Get Watched Videos by Your Friends

Note that you should mark the node as visited when adding it to the queue.

815. Bus Routes

Station i enters the queue. Each time, neighbors are found by looking at all stations reachable by each bus in stopToBus[i]. Also, a vis array is used to record whether a station has been visited / a bus has been taken. This way, each bus route is traversed at most once, because once a bus has been reached, its route is not traversed again. The final time complexity is O(S), which is the sum of the lengths of all routes.

Topological Sort

DFS Explanation

For directed acyclic graphs.

269. Alien Dictionary

Need to pay attention to: graph construction method. DFS uses the three-color coloring method. Each time a node is marked as [traversal complete], it is added to the topological queue. The final answer is the reverse order of the topological queue.