c++ - 邻接矩阵的深度优先搜索

Question

对于这个程序，我得到了一组输入，我需要将它们存储在邻接矩阵中。我已经这样做了，所以我有一个邻接矩阵 Matrix[11][11]。现在，使用这个矩阵，我需要执行深度优先搜索并返回 pi 值。

我有这方面的伪代码，所以我相信我需要两种方法:DFS(graph) 和 DFS-VISIT(node)。但是，我在实际执行此操作时遇到了麻烦。我可以直接使用邻接矩阵来执行此操作，还是需要以某种方式使用该矩阵创建图形？任何实际编码方面的帮助将不胜感激。

DFS(G) 
   for each u ∈ V[G] do 
      color[u] = WHITE  
      ∏[u] = NIL 
   time = 0 
   for each u ∈ V[G] do 
      if color[u] = WHITE then 
         DFS-VISIT(u) 

DFS-VISIT(u) 
   color[u] = GRAY 
   time++ 
   d[u] = time 
   for each v ∈ Adj[u] do 
      if color[v] = WHITE then 
         ∏[v] = u 
         DFS-VISIT(v) 
   color[u] = BLACK
   time++ 
   f[u] = time

Answer 1

你那里的伪代码似乎假设有一个邻接表。

特别是这段代码:(假定对应于代码块的缩进)

for each v ∈ Adj[u] do 
  if color[v] = white then 
    ∏[v] = u 
    DFS-VISIT(v) 

区别在于:对于邻接矩阵，所有顶点都在那里，并且通常使用 0/1 标志来指示当前顶点和目标顶点之间是否存在边。

因此，您应该遍历邻接矩阵中该行的所有顶点，并且仅在标志设置为 1 时执行某些操作。

这部分伪代码看起来像这样:

for v = 1 to n do  // assuming 1-indexed
  if color[v] = white && AdjMatrix[u][v] == 1 then 
    ∏[v] = u 
    DFS-VISIT(v) 

据我所知，伪代码的其余部分看起来应该是相同的。