【数据结构】超级简单的图算法，图文并茂，学不会你来打我

class Vertex {
    constructor (uuid) {
        this.uuid = uuid
        // ...你可以在这里添加others props
    }
}

class Graph {
    constructor(vertexNumber) {
        this.vertexs = [] // 存放节点
        this.edges = {} // 存放邻接表
        this.marked = {} // 记录标记
    }
}

class Graph {
    // 增加节点
    addNodes (uuid) {
        this.vertexs.push(new Vertex(uuid))
        this.edges[uuid] = []
        this.marked[uuid] = false
    }
}

class Graph {
    // 增加边
    addEdges (source, target) {
        // 分别给对方的邻接表添加边
        this.edges[source].push(target)
        this.edges[target].push(source)
    }
}

class Graph {
    // 展示图
    showGraoh () {
        this.vertexs.forEach(vertex => console.log(
            vertex.uuid,
            '->',
            this.edges[vertex.uuid].toString()
        ))
    }
}

const graph = new Graph()
[1, 2, 3, 4, 5, 6].forEach((n) => graph.addNodes(n))
graph.addEdges(1, 2)
graph.addEdges(1, 3)
graph.addEdges(1, 4)
graph.addEdges(3, 4)
graph.addEdges(2, 5)
graph.addEdges(5, 6)
graph.showGraoh()
// 1 '->' '2,3,4'
// 2 '->' '1,5'
// 3 '->' '1,4'
// 4 '->' '1,3'
// 5 '->' '2,6'
// 6 '->' '5'

// 深度优先搜索
dfs (uuid) {
    this.visited[uuid] = true // 深度优先单独标记，以免影响广度优先算法和最短路径算法
    console.log('dfs', uuid)
    // 循环邻接表中子节点
    this.edges[uuid].forEach(edge => {
        // 如果没有标记，就继续下钻
        if (!this.visited[edge]) this.dfs(edge) // 递归
    })
}

 // 广度优先搜索
bfs (uuid) {
    // 1.先初始化一个空队列
    const queue = []
    this.marked[uuid] = true
    // 2.将起始节点放入队列
    queue.push(uuid)
    console.log('bfs', uuid)
    while (queue.length) {
        // 3.弹出队列第一个节点，并且访问它子节点
        const uuid_ = queue.shift()
        this.edges[uuid_].forEach(edge => {
            // 4.如果没有被标记，那就标记它，并放入队列
            if (!this.marked[edge]) {
                this.marked[edge] = true
                console.log('bfs', edge)
                queue.push(edge)
            }
        })
    }
}

graph.dfs(1)
console.log(`<=========>`)
graph.bfs(1)
// dfs 1
// dfs 2
// dfs 5
// dfs 6
// dfs 3
// dfs 4
// <=========>
// bfs 1
// bfs 2
// bfs 3
// bfs 4
// bfs 5
// bfs 6

// 记得添加这个属性
this.edgeTo = {}
// 对广度优先搜索改造
bfs (uuid) {
    const queue = []
    this.marked[uuid] = true
    queue.push(uuid)
    console.log('bfs', uuid)
    while (queue.length) {
        const uuid_ = queue.shift()
        this.edges[uuid_].forEach(edge => {
            if (!this.marked[edge]) {
                this.edgeTo[edge] = uuid_ // 记录每个节点的父节点
                this.marked[edge] = true
                console.log('bfs', edge)
                queue.push(edge)
            }
        })
    }
    console.log(this.edgeTo) // 打印每个节点对应父节点的信息
}
// 找出目标节点到根节点的路径
pathTo (uuid) {
    const source = this.vertexs[0].uuid
    const path = []
    if (this.marked[uuid]) {
        for(let i = uuid; i !== source; i = this.edgeTo[i]) {
            path.push(i)
        }
    }
    path.push(source)
    return path
}
// 格式化展示
printMinPathTo (uuid) {
    const path = this.pathTo(uuid).join('->')
    console.log(path)
}

graph.printMinPathTo(6)
// 依次打印
// {
//   2: 1,
//   3: 1,
//   4: 1,
//   5: 2,
//   6: 5
// }
// 6->5->2->1