CLRS DFS의 위상 정렬 알고리즘 역?

Question

토폴로지 정렬에 대한 단계를 살펴보면 혼란 스럽습니다. DFS의 역순이 토폴로지 정렬에 대한 예상 솔루션이라는 것을 알았습니다.

은 또한 그래프 데이터 구조 여기 여기

#include "iostream" 
#include "vector" 
#include "list" 

enum color{ 
    WHITE, 
    GREY, 
    BLACK 
}; 

struct edge{ 
    int destination_vertex; 
    edge(int ver){ 
     destination_vertex = ver; 
    } 
}; 

struct vertex{ 
    int id; 
    color visited; 
    std::list<edge> list; 
    vertex(int _id){ 
     id = _id; 
    } 
}; 


class graph 
{ 
private: 
    std::vector<vertex> vertexes; 
    int next; 
    std::list<int> q; 
public: 
    graph(void){ 
     next = 0; 
    } 
    ~graph(void){} 
    void add_node(std::vector<int> edges); 
    void add_node(std::vector<int> incoming_edges , std::vector<int> outgoing_edges); 
    void print(); 
    void dfs(); 
    void dfs_visits(vertex& source); 
    void bfs(); 
    static void process(); 
}; 

예컨대 하나 인 작은 코드

void graph::dfs(void) 
{ 
    for(std::vector<vertex>::iterator iter =vertexes.begin();iter < vertexes.end();iter++){ 
     iter->visited = WHITE; 
    } 

    for(std::vector<vertex>::iterator iter =vertexes.begin();iter < vertexes.end();iter++){ 
     if(iter->visited == WHITE){ 
      dfs_visits(*iter); 
     } 
    } 

    std::cout << "-----------------dfs------------------"<<std::endl; 
    for(std::list<int>::reverse_iterator riter = q.rbegin() ; riter != q.rend();riter++) 
     std::cout << *riter << std::endl; 

    std::cout << "-----------------topological_sort------------------"<<std::endl; 
    for(std::list<int>::iterator iter = q.begin() ; iter != q.end();iter++) 
     std::cout << *iter << std::endl; 


    q.clear(); 
} 


void graph::dfs_visits(vertex& source){ 
    source.visited = GREY; 
    for(std::list<edge>::iterator iter = source.list.begin();iter != source.list.end();iter++){ 
     if(vertexes[iter->destination_vertex].visited == WHITE){ 
      dfs_visits(vertexes[iter->destination_vertex]); 
     } 
    } 
    source.visited = BLACK; 
    q.push_front(source.id); 
} 

시도 그래프 내가

내 질문은 정말 간단 질문 문을 변경

0->1,2, 
1->3, 
2-> 
3-> 
4-> 
5->4, 
-----------------dfs------------------ 
3 
1 
2 
0 
4 
5 
-----------------topological_sort----- 
5 
4 
0 
2 
1 
3 

시도 .. 위상 종류는 항상 역순으로 DFS되어 있습니까? 카운터 예제가 없다면?

특정 그래프에 대한 내 출력이 표시되는 경우 DFS 출력과 그 반전은 그래프의 토폴로지 정렬에도 올바른 해결책입니다 .... CLR 토폴로지 정렬 알고리즘을 읽는 것 또한 토폴로지 정렬과 비슷하게 보입니다. DFS의?

Answer 1

예, 항상 사실입니다. DAG에있는 DFS의 반대는 토폴로지 정렬을 제공합니다.

출처 : http://www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/MyL08.pdf 슬라이드 13