试图在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_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 ;

来源

2013-05-07 user2305426

'edge_iterator'如何工作？它看起来像是在'p_edge'后面返回与顶点编号'vertex_number'相邻的下一个边。递归调用深度优先遍历在哪里？ “while”循环中应该有多少？目前，这只是'if {...}'。看起来你正在设置一个堆栈，遍历与'vertex_number'相邻的边缘（但我不知道'edge_iterator'是如何工作的，在访问过程中标记这些边上的顶点并将它们的值放入堆栈中，然后，从堆栈中弹出一个值，使用它调用'p_func_f'，并结束 – 2013-05-07 15:34:56

您是对的，edge_iterator只是返回p_edge后面顶点的下一条边，整个While {..}循环是深度优先遍历，我只是不能使用funcition调用，因为它是递归的，我需要每个边都被添加到堆栈中，因为我一次只能遍历遍历的一个边。是的，到目前为止，其余的分析是然而，在所有这些之后，我得到的值小于打印用于遍历的图中的边，并且这些数字与输入的数不匹配 – user2305426 2013-05-07 15:41:26

如果您有一个图'G = {（A，B ）（B，C）（C，D）}'，你从调用'topological_sear开始ch（G，A，[false，false，false]，？）'，应该在'A'处开始深度优先遍历。从“C”开始的深度优先遍历是什么时候发生的？我没有看到它会在这段代码中发生。 “C”何时会被标记为已访问？ – 2013-05-07 16:19:44

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

来源

2013-05-07 15:47:56

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

回答

相关问题