c - 试图在c中做图的拓扑排序？

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

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_迭代器是直接从教科书和功能正常。如果您能给我提供任何关于我的电话号码错在哪里的建议，我们将不胜感激。
编辑：我重新编辑了代码，以反映对顶点数和while{..}循环的建议更改。但是现在程序只打印第一个顶点而不打印其他顶点。我可以看到循环之前是如何不访问图中的每个节点的，但是现在它只访问一个节点才停止的？这是在哪里被阻止的？
这是边迭代器

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 ;

最佳答案

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

关于c - 试图在c中做图的拓扑排序？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16422108/