DFS和一个堆栈-Java 学习之路

我在业余时间学习CS算法并且一直很好，但是我无法理解邻接矩阵和DFS .

如果以上是无向图，则有6个顶点（a，f）（第1行是顶点a等）如果图是使用DFS和堆栈遍历，则从顶点a开始 .

每次插入或删除顶点后，队列的内容是什么？我假设如果有2个同时插入它将按字母顺序排列 .

有人可以解释如何解决这个问题吗？

2 回答

4
你在 a ，所以你的行是 010100 而你的邻居是 b ， d . 所以把它们放在堆栈上（你已经访问过 a ）：
```
[d b]                  {a}
```
pop d ，将其添加到受访节点集，然后访问那里 - 111000 （ a ， b ， c ）（但您已访问过 a ）：
```
[c b b]                {a d}
```
pop c ，将其添加到访问过的节点集中，然后访问那里 - 010110 （ b ， d ， e ）（但我们访问过 d ）：
```
[e b b b]              {a d c}
```
pop e ，将其添加到访问过的节点集中，然后访问那里 - 001001 （ c ， f ）（但我们访问过 c ）：
```
[f b b b]              {a d c e}
```
pop f ，将其添加到访问过的节点集中，然后访问那里 - 000010 （ e ）（但我们已访问过那里）：
```
[b b b]                {a d c e f}
```
pop b ，将其添加到访问过的节点集中，然后访问那里 - 101100 （ a ， c ， d ）（但我们访问了所有这些节点）：
```
[b b]                  {a d c e f b}
```
我们访问了b，所以弹出并丢弃两次 .
```
[]                     {a d c e f b}
```
ps它是DFS，所以它是一个堆栈，而不是一个队列（你在问题中都提到了） . 对于BFS来说它会类似，但是你追加到队列中，所以前几步是：
```
[d b]                  {a}
[b b c]                {a d}
```
其中 b 和 c 被添加到"right"而不是"left"（但我们仍然从左边开始，所以我们探索广度，下一个节点将是 b ） .
回复于 2024-04-26T13:22:27+08:00

作为安德鲁库克的一个很好的答案的附录，您可以使用python库 networkx 实际可视化DFS搜索！默认情况下，DFS从节点0开始，但可以更改 . 您可以在开头修改图形以显示更复杂的系统 .

enter image description here

import numpy as np
import networkx as netx
import pylab as plt

# Reshape the input string into a numpy array then a graph
A = np.array(map(int,"010100101100010110111000001001000010")).reshape(6,6)
G = netx.Graph(A)

# Compute the DFS tree
T = netx.dfs_tree(G)

# Show the edges traversed
print list(netx.dfs_edges(G))

# Plot the original graph
plt.subplot(121)
pos = netx.circular_layout(G)
netx.draw(G,pos,node_color='w',node_size=800)
netx.draw_networkx_nodes(G,pos,nodelist=[0],node_color='r',node_size=800)

# Plot the result of the DFS
plt.subplot(122)
pos = netx.circular_layout(T)
netx.draw(T,pos,node_color='w',node_size=800)
netx.draw_networkx_nodes(T,pos,nodelist=[0],node_color='r',node_size=800)

plt.show()

回复于 2024-04-26T13:22:27+08:00

DFS和一个堆栈

2 回答

相关问题