js版本无向图的寻路

/*from数组应该被返回，这里为了和最基本的dfs/bfs进行对照，尽量少的修改了代码。*/
let generateGraph=require("./graph").generateGraph
//let V=10
//var edges=[[1,0],[1,3],[3,4],[6,4],[8,1],[7,8],[5,9],[6,8]]

let V=1000
var edges=[]
for(let i=0;i<V;i++){
    let x=Math.floor(Math.random()*V)
    let y=Math.floor(Math.random()*V)
    edges.push([x,y])
}
console.log(G=generateGraph(V,edges))

console.log(G=generateGraph(V,edges))



function dfs(v,G){
    var marked=[]
    var from=[]
    from[v]=v
    for(let i=0;i<V;i++){
        marked[i]=false
    }
    dfs_(v,G,marked,from)
    console.log("dfs from-->",from)
    return marked
}

function dfs_(v,G,marked,from){
    marked[v]=true
    for(let j in G[v]){
        let w=G[v][j]
        if(!marked[w]){
            from[w]=v
            dfs_(w,G,marked,from)
        }
    }
}

function dfsStack(v,G){
    var marked=[]
    var from=[]
    from[v]=v
    for(let i=0;i<V;i++){marked[i]=false}
    var stack=[]
    stack.push(v)
    while(stack.length>0){
        //console.log(stack,from)
        var v_=stack.pop()
        //if(!marked[w])必须加，不然一个点可能被处理多次
        if(!marked[v_]){
            marked[v_]=true
            for(let j in G[v_]){
                let w=G[v_][j]
                //if(!marked[w])必须加，否则w的上家会被重复修改，只要出现环就以最后一个临界点为上家
                if(!marked[w]){            
                    from[w]=v_
                    stack.push(w)
                }
            }
        }
    }
    console.log("dfsStack from-->",from)
    return marked
}

/*可以发现dfsStackError和dfs的搜索逻辑(顺序？)不太一样，
比如012组成1个环，从0出发，那么dfs得到from一定是[0,0,1]或者[0,1,0],
而dfsStackError是[0,0,0]。所以这个错误的深度优先搜索的逻辑。*/
function dfsStackError(v,G){
    var marked=[]
    var from=[]
    from[v]=v
    for(let i=0;i<V;i++){marked[i]=false}
    var stack=[]
    marked[v]=true
    stack.push(v)
    while(stack.length>0){
        //console.log(stack)
        var v_=stack.pop()
        for(let j in G[v_]){
            let w=G[v_][j]
            if(!marked[w]){
                from[w]=v_
                marked[w]=true
                stack.push(w)
            }
        }
    }
    console.log("dfsStackError from-->",from)
    return marked
}

function bfs(v,G){
    var marked=[]
    var from=[]
    from[v]=v
    for(let i=0;i<V;i++){marked[i]=false}
    var queue=[]
    marked[v]=true
    queue.push(v)
    while(queue.length>0){
        //console.log(queue)
        var v_=queue.shift()
        for(let j in G[v_]){
            let w=G[v_][j]
            if(!marked[w]){
                from[w]=v_
                marked[w]=true
                queue.push(w)
            }
        }
    }
    console.log("bfs from-->",from)
    return marked
}



console.log(marked1=dfs(0,G))
console.log(marked2=dfsStackError(0,G))
console.log(marked3=dfsStack(0,G))
console.log(marked4=bfs(0,G))
console.log(JSON.stringify(marked1)==JSON.stringify(marked2))
console.log(JSON.stringify(marked1)==JSON.stringify(marked3))
console.log(JSON.stringify(marked1)==JSON.stringify(marked4))