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

Question

我目前正在使用源去除算法对拓扑排序算法进行编码。

我首先确定了一个顶点，在剩余的有向图中没有任何进入的边，然后将其连同所有从其出来的边一起删除。并且删除顶点的顺序可以解决拓扑排序问题。

输入的是我要排序的顶点数，并且我使用了邻接矩阵来显示边的方向和存在。

问题是代码中的某个地方产生了无限循环，结果我的代码未显示结果。

我的输入是顶点数：4

输入第1行0 1 1 0

输入第2行0 0 0 1

输入第3行0 0 0 1

输入第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数组的大小，此代码容易受到hardcoded攻击。 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;
}