c++ - 拓扑排序不打印所有顶点
问题描述
我正在使用邻接矩阵而不是边缘列表对 geeksforgeeks 拓扑排序实现进行编码。我的代码结构类似于 c++ 示例,但无法让我的代码访问和打印所有节点。我知道我必须从入度为 0 的顶点开始,但顶点 4 或 5(入度为 0)都不适用于我的代码。我正在使用的示例实现和图解图可以在这里找到https://www.geeksforgeeks.org/topological-sorting/从顶点 5 开始时的预期输出是 542310,但我的代码输出的是 52310。开始时的预期输出从 4 是 452310 但我的代码输出 410。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> topoSort(int A[6][6], int start);
void topoSortHelper(int A[6][6], int start, vector<bool>& visited, stack<int>& s);
vector<int> topoSort(int A[6][6], int start)
{
vector<bool> visited(6,false);
stack<int> s;
vector<int> result;
for(int i = 0; i < 6; i++)
{
visited[i] = false;
}
visited[start] = true;
topoSortHelper(A, start, visited, s);
while(!s.empty())
{
cout << s.top();
s.pop();
}
return result;
}
void topoSortHelper(int A[6][6], int start, vector<bool>& visited, stack<int>& s)
{
for(int i = 0; i < 6; i++)
{
if(A[start][i] == 1 && visited[i] == false)
{
visited[i] = true;
topoSortHelper(A, i, visited, s);
}
}
s.push(start);
}
int main()
{
int A[6][6] =
{
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 0},
{1, 1, 0, 0, 0, 0},
{1, 0, 1, 0, 0, 0}
};
vector<int> result = topoSort(A, 5);
for(auto i: result)
{
cout << i;
}
return 0;
}
解决方案
您的代码缺少这部分
// Call the recursive helper function to store Topological
// Sort starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
from the linked code.
When you start only from e.g. 4
, you can verify in the linked drawing that only 0
and 1
are reachable in the example graph.
推荐阅读
- airflow - Cloud Composer 将文件写入其他存储桶问题
- c# - C# string.this int ' 不能分配给(它是只读的)REPLACE
- excel - 根据列中的单元格值突出显示列标题
- swift - 将日期字符串转换为所需的日期格式,输出为零
- azure-devops - 看不到通过 API 添加的测试附件
- php - 调用 PDO() 时的未知数据库,用于使用 WAMPServer 3.2.0 在 phpMyAdmin 上创建的 MySQL 数据库
- java - 在流函数中解析对象
- go - 无法在 go 例程中获取多个通道值
- google-cloud-platform - GCP Composer - 如何运行 Python 3 而不是 Python 2
- php - SoapCall 从 WSDL PHP 中可用的服务中调用特定服务