c - 试图在 c 中对图进行拓扑排序？

Question

我正在为图的拓扑排序程序编写代码。我通过对图进行深度优先搜索来实现该算法，将每个顶点值放入堆栈，然后将值从堆栈中弹出并打印出来。这应该会产生一种拓扑排序，但到目前为止，就顶点数量而言，我得到的值始终比我输入的值少一个，而且没有一个数字与我输入的值匹配。

status topological_search(graph G, vertex vertex_number, bool visited[], status
 (*p_func_f)()){

  edge *p_edge = NULL;
  int *temp ;
  stack S ;

  init_stack(&S) ;
  temp = (int *) malloc(sizeof(int)) ;

  while((p_edge = edge_iterator(G, vertex_number, p_edge)) != NULL){
    if(visited[VERTEX(p_edge)] == FALSE){

      visited[VERTEX(p_edge)] = TRUE ;
      *temp = VERTEX(p_edge) ;
      push(&S, (generic_ptr) temp) ;
      vertex_number = VERTEX(p_edge) ;
    }
  }
  while(!empty_stack(&S)){
    pop(&S, (generic_ptr) &temp) ;
    (*p_func_f)(*temp) ;
  }
  return OK ;
}

我的堆栈函数都正常工作，它们已经在其他程序中测试过了。 Edge_iterator 直接来自教科书并且功能正常。任何关于我的排序在哪里得到错误数字的建议将不胜感激。

编辑:我重新编辑了代码以反射(reflect)建议对 vertex_number 和 while{..} 循环所做的更改。然而现在程序将只打印他的第一个顶点，没有别的。我可以看到之前循环不会访问图中的每个节点，但是现在它在停止之前只访问一个节点？这是在哪里停止的？

这里是 Edge_iterator

edge *edge_iterator(graph G, vertex vertex_number, edge *p_last_return){

  vertex other_vertex ;
  if(vertex_number < 0 || vertex_number >= G->number_of_vertices) return NULL ;

  if(p_last_return == NULL) other_vertex = 0 ;
  else other_vertex = VERTEX(p_last_return) + 1 ;

  for( ; other_vertex < G->number_of_vertices; other_vertex++){
    if(G->matrix[vertex_number][other_vertex].weight != UNUSED_WEIGHT)
      return &G->matrix[vertex_number][other_vertex] ;
  }
  return NULL ;
}

和图形实现。

typedef int vertex ;
typedef struct {int weight; vertex vertex_number ;} edge ;

#define UNUSED_WEIGHT (32767)
#define WEIGHT(p_e) ((p_e) -> weight)
#define VERTEX(p_e) ((p_e) -> vertex_number)

typedef enum {directed, undirected} graph_type ;
typedef enum {DEPTH_FIRST, TOPOLOGICAL } searchorder ;

typedef struct {
  graph_type type ;
  int number_of_vertices ;
  edge **matrix ;
}graph_header, *graph ;

Answer 1

您的 vertex_number 永远不会更新，因此您永远不会比起始节点更远。典型的拓扑排序用它的前驱数来标记每个节点。然后它转到计数为零的所有节点并减少其所有后继节点的计数。重复此过程，直到找不到计数为零的新节点。如果最后所有节点的计数都为零，则该图是无环的，访问节点的顺序是拓扑顺序。