топологическая сортировка с использованием очереди в графе - PullRequest
Новая
       42

топологическая сортировка с использованием очереди в графе

0 голосов
/ 08 ноября 2018

Ниже мое чтение алгоритма топологической сортировки в очереди, записанное в моем учебнике: 

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);
             }


       }
    } 
}

Алгоритм не работает для следующего графика:

graph the algorithm fails on

Если в данном графе изначально 7 5 3 имеет ноль градусов, то они будут вставлены в очередь, но для любой из вершин, смежных с 7 5 3, у нас нет какой-либо вершины со степенью 1. Это означает, что if(--indegree[w]==0) не будет выполняться для 7 5 3, следовательно, дальнейшая постановка в очередь не будет выполняться, и, следовательно, алгоритм не будет обрабатывать дальнейшие вершины. Я хотел бы знать, почему происходит сбой алгоритма, если граф является DAG? Каким образом это неверно?

Я знаю, что мы также можем реализовать топологическую сортировку с использованием DFS, но я хочу реализовать следующее как есть:

the pseudocode of the algorithm I want to implement

1 Ответ

0 голосов
/ 08 ноября 2018

Ваш алгоритм неверен. Здесь 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.

...