我编写了一个递归DFS算法来遍历图:
void Graph<E, N>::DFS(Node n)
{
std::cout << ReadNode(n) << " ";
MarkVisited(n);
NodeList adjnodes = Adjacent(n);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
Node adj = adjnodes.ReadList(pos);
if(!IsMarked(adj))
DFS(adj);
pos = adjnodes.NextPosition(pos);
}
}
然后我用堆栈编写了迭代DFS算法:
template <typename E, typename N>
void Graph<E, N>::IterativeDFS(Node n)
{
Stack<Node> stack;
stack.Push(n);
while(!stack.IsEmpty())
{
Node u = stack.Read();
stack.Pop();
if(!IsMarked(u))
{
std::cout << ReadNode(u) << " ";
MarkVisited(u);
NodeList adjnodes = Adjacent(u);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
stack.Push(adjnodes.ReadList(pos));
pos = adjnodes.NextPosition(pos);
}
}
}
我的问题是在一个图表中,例如,我输入三个节点'a','b','c'带有弧('a','b')和('a','c')我的输出是:
带有递归DFS版本的'a','b','c',以及:
带有迭代DFS的'a','c','b'。
我怎么能得到同样的订单?难道我做错了什么?
谢谢!
两者都是有效的DFS算法。 DFS不会指定您首先看到的节点。这并不重要,因为边缘之间的顺序没有定义[记住:边缘通常是一组]。不同之处在于您处理每个节点的子节点的方式。
在迭代方法中:首先将所有元素插入到堆栈中 - 然后处理堆栈的头部[这是插入的最后一个节点] - 因此您处理的第一个节点是最后一个子节点。
在递归方法中:您在看到每个节点时处理它们。因此,您处理的第一个节点是第一个孩子。
要使迭代DFS产生与递归相同的结果 - 您需要以相反的顺序向堆栈添加元素[对于每个节点,首先插入其最后一个子节点并将其最后一个子节点插入]
在这里,我以递归的方式离开我的解决方案,非常快速地实现。只需要针对需要使用此算法的任何问题进行调整。
将当前状态标记为已访问,定义为ok[u] = true
非常重要,即使具有所有状态,因为它们未使用memset(ok, 0, sizeof ok)
访问过
#define forn(i , a , b) for(int i=(a);i<(b);i++)
vector<int> arr[10001];
bool ok[10001];
void addE(int u , int v){
arr[u].push_back(v);
arr[v].push_back(u);
}
void dfs(int u){
ok[u] = true;
forn(v , 0 , (int)arr[u].size()) if(!ok[arr[u][v]]) dfs(arr[u][v]);
}
int main(){
//...
memset(ok , 0 , sizeof ok);
//...
return 0;
}
下面是C#for Adjacency Matrix中的示例代码(根据上面的@amit回答)。
using System;
using System.Collections.Generic;
namespace GraphAdjMatrixDemo
{
public class Program
{
public static void Main(string[] args)
{
// 0 1 2 3 4 5 6
int[,] matrix = { {0, 1, 1, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 1, 0},
{1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0 ,0},
{0, 0, 1, 1, 1, 0, 0} };
bool[] visitMatrix = new bool[matrix.GetLength(0)];
Program ghDemo = new Program();
for (int lpRCnt = 0; lpRCnt < matrix.GetLength(0); lpRCnt++)
{
for (int lpCCnt = 0; lpCCnt < matrix.GetLength(1); lpCCnt++)
{
Console.Write(string.Format(" {0} ", matrix[lpRCnt, lpCCnt]));
}
Console.WriteLine();
}
Console.Write("\nDFS Recursive : ");
ghDemo.DftRecursive(matrix, visitMatrix, 0);
Console.Write("\nDFS Iterative : ");
ghDemo.DftIterative(matrix, 0);
Console.Read();
}
//====================================================================================================================================
public void DftRecursive(int[,] srcMatrix, bool[] visitMatrix, int vertex)
{
visitMatrix[vertex] = true;
Console.Write(vertex + " ");
for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++)
{
if (visitMatrix[neighbour] == false && srcMatrix[vertex, neighbour] == 1)
{
DftRecursive(srcMatrix, visitMatrix, neighbour);
}
}
}
public void DftIterative(int[,] srcMatrix, int srcVertex)
{
bool[] visited = new bool[srcMatrix.GetLength(0)];
Stack<int> vertexStack = new Stack<int>();
vertexStack.Push(srcVertex);
while (vertexStack.Count > 0)
{
int vertex = vertexStack.Pop();
if (visited[vertex])
continue;
Console.Write(vertex + " ");
visited[vertex] = true;
for (int neighbour = srcMatrix.GetLength(0) - 1; neighbour >= 0; neighbour--)
//for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++)
{
if (srcMatrix[vertex, neighbour] == 1 && visited[neighbour] == false)
{
vertexStack.Push(neighbour);
}
}
}
}
}
}