dfs

dfs.cpp

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;
static const int MAX = 10000;

vector<int> G[MAX];
list<int> out;
bool V[MAX];
int N;

void dfs(int u){
    V[u] = true;
    for (int i=0; i< G[u].size(); i++){
        int v = G[u][i];
        if(!V[v]) dfs(v);
    }
    out.push_front(u);
}

int main(){
    int s, t, M;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        V[i] = false;
    }
    for(int i = 0; i < M; i++){
        cin >> s >> t;
        G[s].push_back(t);
    }
    for(int i = 0; i < N; i++){
        if(!V[i]) dfs(i);
    }
    for (list<int>::iterator it = out.begin(); it != out.end(); it++){
        cout << *it << endl;
    }
    return 0;
}

dfs.js

const _ = require("lodash");

class Graph {
    constructor(edges) {
        this.vertexes = [];
        this.nearMap = {}

        this.edges = _.clone(edges);
        _.forEach(this.edges, edge => {
            if (!_.includes(this.vertexes, edge.self_id)){
                this.vertexes.push(edge.self_id);
            }
            if (!_.includes(this.vertexes, edge.next_id)){
                this.vertexes.push(edge.next_id);
            }
        })
        // console.log(this.vertexes);


        _.forEach(this.vertexes, vertex => {
            this.nearMap[vertex] = new Array();
            // console.log({vertex}, this.nearMap)
        });

        _.forEach(this.edges, edge => {
            // console.log(this.nearMap, edge.self_id);
            // this.nearMap[edge.next_id].push(edge.self_id);
            this.nearMap[edge.self_id].push(edge.next_id);
        })
        this.sort2 = []

    }


    TOPOLOGICAL_SORT(){
        this.globalTime = 1;
        this.nodes = _.map(this.vertexes, vertex=>({id: vertex, color: 'white'}))
        _.forEach( this.nodes, node => {
            if (node.color == 'white'){
                this.DFS_VISIT(node)
            }
        })
        console.log(this.nodes);
        const sortedNodes = _.sortBy(this.nodes, 'f_time')

        console.log(sortedNodes)
        console.log(this.sort2);
        


    }
    DFS_VISIT(node){
        this.globalTime += 1
        node.d_time = this.globalTime
        node.color = 'gray'
        console.log("VISIT",  node.id);
    
        // console.log("near:",this.nearMap[node.id]);
        
        _.forEach( this.nearMap[node.id], (near_id) => {
            let near_node = _.find(this.nodes, {id: near_id});
            // console.log("near_node:",near_node);

            if (near_node && near_node.color == 'white') {
                // node.children.push(child)
                // child.pi = node
    
                this.DFS_VISIT(near_node)
            }
        })
        node.color = 'black'
        this.globalTime += 1
        node.f_time = this.globalTime
        this.sort2.unshift(node)
    }
}


let edges = [
    { self_id: 0, next_id: 1 },
    { self_id: 1, next_id: 2 },
    { self_id: 3, next_id: 1 },
    { self_id: 3, next_id: 4 },
    { self_id: 4, next_id: 5 },
    { self_id: 5, next_id: 2 },
]
let g = new Graph(edges);
console.log(g);
g.TOPOLOGICAL_SORT();