c - 在图中使用队列进行拓扑排序
问题描述
以下是我在教科书中对队列上的拓扑排序算法的阅读:
void topologicalsort(struct Graph* G){
struct queue* Q;
int counter;
int v,w;
Q=createqueue();
counter=0;
for(v=0;v<G->V;v++){
if(indegree[v]==0)
enqueue(Q,v);
while(!isemptyqueue(Q)){
v=dequeue(Q);
topologicalorder[v]=++counter;
for each w to adjacent to v
if(--indegree[w]==0){
enqueue(Q,w);
}
}
}
}
下图的算法失败:
如果在给定的图中,最初 7 5 3 的度数为零,那么它们将被插入队列中,但对于与我们相邻的7 5 3
任何顶点,我们没有任何度数为 1 的顶点。这意味着因此if(--indegree[w]==0)
不会成立7 5 3
将不会在队列中进一步排队,因此该算法不会处理更多的顶点。如果图形是 DAG,我想知道为什么算法会失败?在哪方面是不正确的?
我知道我们也可以使用 DFS 实现拓扑排序,但我想按原样实现以下内容:
解决方案
您的算法实现不正确。这里while(!isemptyqueue(Q))
不在for(v=0;v<G->V;v++)
(参见算法中的缩进)。有关更多说明,请参见下文:
void topologicalsort(struct Graph* G){
struct queue* Q;
int counter;
int v,w;
Q=createqueue();
counter=0;
for(v=0;v<G->V;v++){
if(indegree[v]==0)
enqueue(Q,v);
}
while(!isemptyqueue(Q)){
v=dequeue(Q);
topologicalorder[v]=++counter;
for each w to adjacent to v {
if(--indegree[w]==0){
enqueue(Q,w);
}
}
}
}
这适用于每个 DAG。
推荐阅读
- linux - 在 Linux 中编写通过 SPI 连接的 PHY 驱动程序
- javascript - console.log 在 io.on('connection',....) 中不起作用
- excel - 如何使用 IF 条件在 FOR 循环中使用 STEP?
- google-data-studio - 适用于 Bigquery 的数据洞察社区连接器
- c# - 读取流然后反序列化
- javascript - React JS 标签启用显示
- flask - 如何计算使用 IIS 部署的 Flask 的唯一访问者
- c++ - 我因为两次定义了一个函数而收到此错误
- svg - 以源图像分辨率计算 SVG 过滤器
- r - 将R中的数字强制列表“现有数据有XXX行,分配的数据有YYYY行”