非递归深度优先搜索的行为几乎类似于c

本文关键字：类似于 递归 深度优先搜索 | 更新日期: 2024-07-27 11:20:25

我正在尝试在c中实现非递归DFS算法#这是我的方法代码

public void dfs(int vertex)
{
   int length = matrix.GetLength(0);
   bool[] visited = new bool[length]; 
   for (int k = 0; k < length; k++)
   {
     visited[k] = false; 
   }
   Stack<int> vertexStack = new Stack<int>();
   vertexStack.Push(vertex);
   visited[vertex] = true;
   Console.Write((vertex) + " ");
   while (vertexStack.Count() != 0)
   {
        int tempVertex = vertexStack.Peek();
        for (int j = 0; j < length; j++)
        {
            if (matrix[tempVertex, j] == 1 && !visited[j])
            {
                Console.Write(j + " ");
                visited[j] = true;
                vertexStack.Push(j);
            }
        }
        vertexStack.Pop();    
   }
}

这是我的图形代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
    class Program
   {
    static void Main(string[] args)
    {
        int[,] matrix2 = {
        {0,1,1,1,0,0},
        {1,0,0,0,1,1},
        {1,0,0,0,0,1},
        {1,0,0,0,0,0},
        {0,1,0,0,0,0},
        {0,1,1,0,0,0},
                         };
        Graphs g2 = new Graphs(matrix2);
        g2.dfs(0);
       // Console.ReadKey();
     }
   }
}

对于这个图，dfs的结果应该是0 1 4 5 2 3

但它们是0 1 2 3 5 4，这几乎类似于该图的BFS 0 1 2 2 3 4 5

有人能告诉我这里怎么了吗？

非递归深度优先搜索的行为几乎类似于c

首先，在循环之后，弹出最后一个被推送的元素。相反，在进入循环之前弹出元素。

其次，当你从堆栈中取出元素时，而不是当你把它们推到堆栈上时，处理它们

第三，为了实现您想要的顺序，向后迭代子节点（因此较小的子节点将位于堆栈的顶部）：

public void dfs(int vertex)
{
    int length = matrix.GetLength(0);
    bool[] visited = new bool[length];
    for (int k = 0; k < length; k++)
    {
        visited[k] = false;
    }
    Stack<int> vertexStack = new Stack<int>();
    vertexStack.Push(vertex);
    while (vertexStack.Count() != 0)
    {
        int tempVertex = vertexStack.Pop();
        if (!visited[tempVertex])
        {
            visited[tempVertex] = true;
            Console.Write((tempVertex) + " ");
            for (int j = length - 1; j >= 0; j--)
            {
                if (matrix[tempVertex, j] == 1 && !visited[j])
                {
                    vertexStack.Push(j);
                }
            }
        }
    }
}
相关文章：