我正在尝试实现 dfs 以从起始节点打印路径。我遵循了 Coremen 书中的算法。这是我的代码: DFS
#include<iostream>
#include<stack>
using namespace std;
int vertex,edge,source,time,adjacency_matrix[100][100],parent[100],Distance[100],Finishing_time[100];
string color[100];
stack<int> result;
void inputGraph();
void initialize();
void doDFS();
void doDFSvisit(int);
void printPath();
//void printAll();
//void printAdjacencyMatrix();
//void printColor();
//void printDistance();
//void printParent();
int main(void)
{
inputGraph();
//initialize();
doDFS();
printPath();
//printAll();
return 0;
}
void inputGraph()
{
cout<<"Total vertex : ";
cin>>vertex;
cout<<"Total edge : ";
cin>>edge;
int i,j;
for(i=1; i<=edge; i++)
{
int start,finish;
cout<<"Enter start and end node for edge "<<i<<" : ";
cin>>start;
cin>>finish;
adjacency_matrix[start][finish]=1;
}
cout<<"The adjacency matrix is : "<<endl;
for(i=1; i<=vertex; i++)
{
for(j=1; j<=vertex; j++)
{
cout<<adjacency_matrix[i][j]<<" ";
}
cout<<endl;
}
}
void initialize()
{
cout<<"Enter source node : ";
cin>>source;
}
void doDFS()
{
int i,j;
for(i=1;i<=vertex;i++)
{
color[i]="white";
parent[i]=0;
}
time=0;
for(i=1;i<=vertex;i++)
{
if(color[i]=="white")
{
doDFSvisit(i);
}
}
}
void doDFSvisit(int node)
{
int i;
time=time+1;
Distance[node]=time;
color[node]="grey";
for(i=1;i<=vertex;i++)
{
if(adjacency_matrix[node][i]==1)
{
if(color[i]=="white")
{
parent[i]=node;
doDFSvisit(i);
}
}
}
color[node]="black";
//extra line for result
result.push(node);
//
time=time+1;
Finishing_time[node]=time;
}
void printPath()
{
cout<<"Path :"<<endl;
int i;
for(i=0;i<=result.size();i++)
{
cout<<result.top()<<" -> ";
result.pop();
}
cout<<" End"<<endl;
}
我的问题:
输入:
6
6
1 2
1 4
2 3
3 4
5 3
5 6
我的输出应该是:
5 6 1 2 3 4 end
但我的输出是:
5 6 1 2 end
似乎从堆栈中打印值会产生问题。请纠正我的错误,在此先感谢。
[附言:我用于输入的有向图的图片,http://imgur.com/fYsICiQ ]
最佳答案
print_path 函数有错误。 您的 for 循环终止条件检查结果(堆栈)的大小,它通过 pop 调用递减每个循环迭代。
您的 print_path 函数应如下所示:
void printPath(){
cout<<"Path :"<<endl;
int i;
while(!result.empty()){
cout << result.top() << " -> ";
result.pop();
}
cout<<" End"<<endl;
}
另外考虑这个 DFS 实现:
list<size_t> l[N];
bool used[N];
void DFS(size_t s){
if (used[s])
return;
used[s] = true;
for(auto i = l[s].begin(); i != l[s].end(); i++)
if(!used[*i]){
DFS(*i);
}
}
used 是全局 bool 数组,指示是否访问了第 i 个顶点。我们不需要为顶点着色。我们必须知道它是否已经访问过。
l 是邻接表(参见 http://www.geeksforgeeks.org/graph-and-its-representations/ )
我们在一些顶点上运行 DFS。 如果它被访问,我们什么也不做。 否则我们将这个顶点标记为已访问。然后在与当前顶点相邻的每个顶点上更深入地运行 DFS。
有关 DFS 的更多信息,请参阅 https://en.wikipedia.org/wiki/Depth-first_search
关于c++ - 算法实现错误(DFS),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37908257/