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

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

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

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

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

Мой вклад

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


c algorithm adjacency-matrix topological-sort
person Yeeun    schedule 19.10.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Обнаружил две ошибки:

  • 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;
}
person ggorlen    schedule 19.10.2019