Recently, we have been writing a small project on branch delimitation for TSP, which involves various knowledge of graphs and trees, so we will summarize our recent learning work from the traversal of undirected graphs, using DFS recursion to traverse undirected graphs.
The adjacency matrix, adjacency table, etc. can be used to represent a graph, here use the adjacency table array to represent, that is, the vertex-indexed list array, the specific implementation uses a dictionary to create the adjacency table array.
Depth-first search DFS simply means that when you visit one of the vertices, you mark it as visited and recursively visit all its neighboring vertices that are not marked.
Old habit, on the code.
Run it and see the result.
A shallow analysis of the recursive process
dfs(0) — dfs(1) — 0 has been marked, the next dfs(3) — 1 has been marked, so the next dfs(2) — 0,3 in graph[2] are marked, back to graph[3], then dfs(5) — 3 has been marked, so dfs(6) — the next is simple, dfs (4). Seems to be the end of it should be so.
here if it ends, it seems perfunctory, tossed a little, to achieve a simple a little dumb s-v of the path to build the function, or use the above example to illustrate the final visited = [0,1,3,2,5,6,4], according to this marker order, there will be and only 0-1, 1-3, 3-2, 3-5, 5-6, 6-4 is selected (do not ask why. This is my rule).
first run the previous dfs, get visited = [0,1,3,2,5,6,4], according to this mark order, there will be and only 0-1, 1-3, 3-2, 3-5, 5-6, 6-4 are selected (do not ask why, this is my rule). Look at lines 4 and 5 and turn the path to build u-v into a path to build v-u.
Someone will wonder why the path from 0 to 5 why not 0-3-5 this, because 0-3 is not marked ah! As for why, this is my rule, do not care (understand the natural will understand my journey, do not understand even if, anyway, the construction of the path and not on the cost, distance, etc. to do requirements).
