发帖
雷达卡
1 A Walk in the Park
#1. No Cycles Allowed
#2. How to Stop Walking in Circles
start walking in any direction, backtracking whenever you came to a dead end or an intersection you had already walked through (to avoid cycles).
2 Go Deep (DFS)
#1. Depth-first search (DFS) gets some of its most important properties from its recursive structure.
- However, if you use DFS on a directed graph, you can’t expect it to explore an entire connected component.
- Tip: For finding connected components in a directed graph, you can easily construct the underlying undirected graph as a first step. Or you could simply go through the graph and add all the reverse edges. This can be useful for other algorithms as well. Sometimes, you may not even construct the undirected graph; simply considering each edge in both directions when using the directed graph may be sufficient.
#2. Depth-First Timestamps and Topological Sorting
As mentioned earlier, remembering and avoiding previously visited nodes is what keeps us from going in circles (or, rather, cycles), and a traversal without cycles naturally forms a tree. Such traversal trees have different names based on how they were constructed; for DFS, they are aptly named depth-first trees (or DFS trees). As with any traversal tree, the structure of a DFS tree is determined by the order in which the nodes are visited. The thing that is particular to DFS trees is that all descendants of a node u are processed in the time interval from when u is discovered to when we backtrack through it.
To make use of this property, we need to know when the algorithm is backtracking, which can be a bit hard in the iterative version.
3 Infinite Mazes and Shortest (Unweighted) Paths
Until now, the overeager behavior of DFS hasn’t been a problem. We let it loose in a maze (graph), and it veers off in some direction, as far as it can, before it starts backtracking. This can be problematic, though, if the maze is extremely large. Maybe what we’re looking for, such as an exit, is close to where we started; if DFS sets off in a different direction, it may not return for ages. And if the maze is infinite, it will never get back, even though a different traversal might have found the exit in a matter of minutes. Infinite mazes may sound far-fetched, but they’re actually a close analogy to an important type of traversal problem - that of looking for a solution in a state-space.
4 Strongly Connected Components
Summary
In this chapter, showed the basics of moving around in graphs, be they directed or not. This idea of traversal forms the basis—directly or conceptually. Used examples of maze traversal algorithms (such as Trémaux’s and Ore’s), although they were mainly meant as starting points for more computer-friendly approaches. The general procedure for traversing a graph involves maintaining a conceptual to-do list (a queue) of nodes you’ve discovered, where you check off those that you have actually visited. The list initially contains only the start node, and in each step you visit (and check off ) one of the nodes, while adding its neighbors to the list. The ordering (schedule) of items on the list determines, to a large extent, what kind of traversal you are doing: using a LIFO queue (stack) gives depth-first search (DFS), while using a FIFO queue gives breadth-first search (BFS), for example. DFS, which is equivalent to a relatively direct recursive traversal, lets you find discover and finish times for each node, and the interval between these for a descendant will fall inside that of an ancestor. BFS has the useful property that it can be used to find the shortest (unweighted) paths from one node to another.
If a graph consists of several connected components, you will need to restart your traversal once for each component. You can do this by iterating over all the nodes, skipping those that have already been visited, and starting a traversal from the others. In a directed graph, this approach may be necessary even if the graph is connected because the edge directions may prevent you from reaching all nodes otherwise. To find the strongly connected components of a directed graph—the parts of the graph where all nodes can reach each other—a slightly more involved procedure is needed. The algorithm discussed here, Kosaraju’s algorithm, involves first finding the finish times for all nodes and then running a traversal in the transposed graph (the graph with all edges reversed), using descending finish times to select starting points.
京公网安备 11010802022788号
