Результат топологической сортировки с использованием алгоритма удаления источника не отображается

Question

В настоящее время я кодирую алгоритм топологической сортировки, используя алгоритм удаления источника.

Сначала я определил вершину без входящих ребер в оставшемся орграфе и удалил ее вместе со всеми выходящими из нее ребрами. И порядок, в котором удаляются вершины, дает решение проблемы топологической сортировки.

Входные данные - это число вершин, которые я хочу отсортировать, и я использовал матрицу смежности, чтобы показать направление и существование ребер.

Проблема в том, что где-то в коде получается бесконечное числоцикл и в результате мой код не показывает результат.

Введено количество вершин: 4

Введите строку 10 1 1 0

Введите строку 20 0 0 1

Введите строку 30 0 0 1

Введите строку 40 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, что должно прояснить проблему.
• Временное жесткое кодирование ваших входных данных экономит время повторного ввода, сокращая количество ошибок и делая проблему легко воспроизводимой для других.
• Использование четких имен переменных и равномерного пробела во всем коде помогает уменьшить количество ошибоки облегчает их отслеживание при возникновении.
• Хорошая идея отделить логику алгоритма от логики ввода, чтобы избежать побочных эффектов . Разбить код на функции - хороший способ сделать это. Это значительно облегчает отладку и делает код расширяемым и пригодным для повторного использования.
• Этот код уязвим к атаке переполнения буфера из-за размера в жестком коде массива. Динамическое выделение памяти - хорошее решение или, по крайней мере, добавление условия, чтобы пользователь не мог указать 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;
}