我正在为图形拓扑排序程序编写代码 . 我已经通过对图形进行深度优先搜索，将每个顶点值放入堆栈，然后从堆栈中弹出值并将其打印出来来实现算法 . 这应该是一个拓扑排序，但到目前为止，我总是得到一个比我输入的顶点数少一个值，并且没有一个数字与我输入的数字相匹配 .
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 ;
1 回答
您的
vertex_number永远不会更新，因此您永远不会比起始节点更进一步 . 典型的拓扑排序标记每个节点的前驱数量 . 然后它进入该计数为零的所有节点，并减少其所有后继的计数 . 重复此过程，直到找不到具有计数零的新节点 . 如果最后的所有节点都具有零计数，则该图是非循环的，并且访问节点的顺序是拓扑顺序 .