試圖在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中做一個圖的拓撲排序？

回答

相關問題