非递归深度优先搜索的行为几乎类似于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
有人能告诉我这里怎么了吗?
首先,在循环之后,弹出最后一个被推送的元素。相反,在进入循环之前弹出元素。
其次,当你从堆栈中取出元素时,而不是当你把它们推到堆栈上时,处理它们
第三,为了实现您想要的顺序,向后迭代子节点(因此较小的子节点将位于堆栈的顶部):
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);
}
}
}
}
}