algorithm - DFS 和堆栈

Question

我在业余时间学习 CS 算法并且进展得很好，但我在理解邻接矩阵和 DFS 时遇到了困难。

010100
101100
010110
111000
001001
000010

如果上面是一个无向图，有 6 个顶点 (a, f)(第一行是顶点 a 等)如果图是使用 DFS 和堆栈遍历，从顶点 a 开始。

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

谁能解释一下如何解决这个问题？

Answer 1

你在 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，所以 pop 和 discard 两次。

[]                     {a d c e f b}

ps 它是 DFS，所以它是一个堆栈，而不是一个队列(你在问题中都提到了)。对于 BFS，它会是相似的，但你追加到队列中，所以前几个步骤是:

[d b]                  {a}
[b b c]                {a d}

其中 b 和 c 添加在“右边”而不是“左边”(但我们仍然从左边取，所以我们探索广度，下一个节点将是 b)。