使用源去除算法结果的拓扑排序未显示

Question

我目前正在编写一个使用源去除算法的拓扑排序算法。

我首先在剩余的有向图中识别出一个没有传入边的顶点，并将它连同所有从它传出的边一起删除。并且删除顶点的顺序产生了拓扑排序问题的解决方案。

输入是我要排序的顶点数，我用邻接矩阵表示边的方向和存在。

问题是代码中的某处形成了无限循环，因此我的代码没有显示结果。

我的输入是

number of vertices: 4
Enter row 1 
0 1 1 0

Enter row 2
0 0 0 1

Enter row 3
0 0 0 1

Enter row 4
0 0 0 0

而且我期望这个输出：

1 2 3 4

但是我得到的是一个无限循环（结果根本不显示）

我想这里有问题：

while(count<n-1){
        for(k=0;k<n;k++){

            if((indeg[k]==0 && flag[k] ==0))        // zero incoming edges && not sorted yet
            {
                printf("%d ", k+1);
                flag[k]=1;      //checked

                for(i=0;i<n;i++){
                    if(a[k][i]==1){  // if there is an outgoing edge
                        a[k][i]=0;     // delete the outgoing edge
                        indeg[k]--;   // decrease the indeg sing the outgoing edge is deleted
                    }
                }

                count++;
            }
        }
    }

...但找不到问题所在。而且我不知道为什么连第一个顶点都没有打印出来。

以下是完整代码，以防万一：

# include <stdio.h>
# include <stdlib.h>


int main(void){

    int i, j;
    int k, n;
    int a[10][10];      // adjacency matrix

    int indeg[10] = {0};        // number of incoming edges
    int flag[10] = {0};         // checked or not

    int count=0;                // count value for sorting vertices


    printf("Enter the no of vertices: ");
    scanf("%d",&n);

    printf("Enter the adjacency matrix:\n");
    for(i=0;i<n;i++){
        printf("Enter row %d\n",i+1);
        for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);       // enter the adjacency matrix
    }


    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            indeg[i]+=a[j][i];      // number of incoming edges updated



    printf("\nThe topological order is:");



    while(count<n-1){
        for(k=0;k<n;k++){

            if((indeg[k]==0) && (flag[k] ==0))      // zero incoming edges && not sorted yet
            {
                printf("%d ", k+1);
                flag[k]=1;      //checked

                for(i=0;i<n;i++){
                    if(a[k][i]==1){
                        a[k][i]=0;              // delete the sorted vertice's outgoing edges 
                        indeg[k]--;             // subtract indeg since the outgoind edge is deleted
                    }
                }

                count++;                        // update the iteration count
                break;                          // break the for loop and start a new one
            }
        }
    }

}

我用这个页面来编写我的算法（尽管我上传的 while 循环中的代码也是错误的）https://www.thecrazyprogrammer.com/2017/05/topological-sort.html

Answer 1

我发现了两个错误：

indeg[k]--; 应该是 indeg[i]--; 因为 k 是当前节点（我们已经确定 indeg[k]==0 只是为了在代码中到达这个位置）并且 i 是我们要删除传入边的邻居（从 k 传出）。
while(count<n-1) 应该是 while(count<n) 否则我们不会打印最后一个节点。

几点建议：

调试此类程序的一个好方法是打印数据以检查其在每次迭代中的值。打印 indeg[k] 显示该值下降到 0 以下，这应该可以清楚地说明问题。
暂时对输入数据进行硬编码可以节省重复输入的时间，减少错误并使其他人可以轻松重现问题。
在整个代码中使用清晰的变量名称和一致的间距有助于减少错误，并在错误出现时更容易对其进行追踪。
最好将算法逻辑与输入逻辑分开以避免side effects。将代码分解成函数是一个很好的方法。这大大简化了调试并使代码可扩展和可重用。
这段代码容易受到攻击buffer overflow attack because of the hardcoded array size. Dynamic memory allocation是一个很好的解决方案，或者至少添加一个条件来防止用户指定n > 10。

这是一个最初的重写，它只实现了上面的一些建议（用 gcc topological_sort.c -Wall -std=c99 编译）：

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int n = 4;
    int adjacency_matrix[][4] = {
        {0, 1, 1, 0},   //   0-->1-->3
        {0, 0, 0, 1},   //   |       ^
        {0, 0, 0, 1},   //   v       |
        {0, 0, 0, 0}    //   2-------+
    };
    int indegrees[n];
    bool visited[n];
    memset(&indegrees, 0, sizeof(*indegrees) * n);
    memset(&visited, false, sizeof(*visited) * n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            indegrees[i] += adjacency_matrix[j][i];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!indegrees[j] && !visited[j]) {
                visited[j] = true;
                printf("%d ", j + 1);

                for (int k = 0; k < n; k++) {
                    if (adjacency_matrix[j][k]) {
                        adjacency_matrix[j][k] = 0;
                        indegrees[k]--;
                    }
                }

                break;
            }
        }
    }

    return 0;
}

使用源去除算法结果的拓扑排序未显示

Topological sorting using source-removal algorithm result not showing

c

algorithm

topological-sort

adjacency-matrix