C에서 위상적인 종류의 그래프를 만들려고합니까?

Question

그래프 용 토폴로지 정렬 프로그램의 코드 작업 중입니다. 그래프의 깊이 우선 검색을 수행하고 각 정점 값을 스택에 넣고 값을 스택 밖으로 빼내어 인쇄하여 알고리즘을 구현했습니다. 이것은 토폴로지 정렬을 생성해야하지만, 지금까지 나는 꼭 꼭짓점 수만큼 일관되게 하나의 값을 얻었고, 그 중 하나도 내가 입력 한 것과 일치하지 않았습니다.

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 ; 

Answer 1

vertex_number은 업데이트되지 않으므로 시작 노드 이상을 얻을 수 없습니다. 일반적인 토폴로지 정렬은 모든 노드를 선행 노드의 수로 표시합니다. 그런 다음이 수가 0 인 모든 노드로 이동하고 모든 후속 노드의 수를 줄입니다. 이 프로세스는 카운트가 0 인 새 노드가 발견되지 않을 때까지 반복됩니다. 끝에있는 모든 노드의 수가 0 인 경우 그래프는 비순환 적이며 노드가 방문한 순서는 위상적인 순서입니다.