0

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

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 直接来自教科书并且正常运行。任何关于我的排序在哪里得到错误数字的建议将不胜感激。

编辑：我重新编辑了代码以反映建议对 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 ;
4

1 回答 1

2

你vertex_number永远不会更新，所以你永远不会比起始节点更进一步。典型的拓扑排序用它的前辈数量标记每个节点。然后它转到该计数为零的所有节点并减少其所有后继节点的计数。重复此过程，直到找不到计数为零的新节点。如果最后所有节点的计数为零，则该图是非循环的，并且访问节点的顺序是拓扑顺序。

于 2013-05-07T15:47:56.947 回答