pathfinding

pathfinding.js

// 图
class Graph {
    constructor(count, adj_list) {
        this.count = count          // 记录顶点的个数
        this.adj = new Array(count)    // 邻接表
        // 初始化邻接表
        for (let i = 0; i < count; i++) {
            this.adj[i] = new Array()
        }
        for (let j = 0, len = adj_list.length; j < len; j++) {
            let vw = adj_list[j]
            this.adj[vw[0]].push(vw[1])
        }
    }
    showGraph() {
        let str = ''
        for (let i = 0; i < this.count; i++) {
            str += (i + " -> ")
            for (let j = 0, len = this.adj[i].length; j < len; j++) {
                if (this.adj[i][j] != undefined) {
                    str += (this.adj[i][j] + ' ')
                }
            }
            str += "\n"
        }
        console.log(str)
    }
    build_path(edgeTo, end, start) {
        const path = []
        for (let i = end; i != start; i = edgeTo[i]) {
            path.push(i)
        }
        path.push(start)
        return path.reverse()
    }
    find_path(start, end) {
        const que = [], edgeTo = [], visited = []
        visited[start] = true
        que.push(start)
        while (que.length > 0) {
            let v = que.shift()
            for (let w of this.adj[v]) {
                if (!visited[w]) {
                    visited[w] = true
                    edgeTo[w] = v
                    que.push(w)
                    if (w == end) {
                        return this.build_path(edgeTo, end, start)
                    }
                }
            }
        }
    }
}
const count = 4
const g = new Graph(count, [[0,1], [0,2], [1,0], [1,2], [1,3], [2,0], [2,1], [3,0], [3,1]])
g.showGraph()
for (let i = 0; i < count; i++) {
    for (let j = 0; j < count; j++) {
        if (i != j) {
            console.log(i + '->' + j, g.find_path(i, j))
        }
    }
}