数据结构TypeScript之邻接表实现示例详解

时间:2023-02-03 前端技术獭人气:0

图的结构特点

图由顶点和顶点之间的边构成，记为G(V, E)。其中V是顶点集合，E是边集合。作为一种非线性的数据结构，顶点之间存在多对多关系。

图的分类

无向图：两个顶点之间有两条互相关联的边。A和B之间为双向互通。

有向图：两个顶点之间有一条或两条关联的边。从A到B或者从B到A，只能单向通过。

带权无向图：在无向图的基础上增加一个权值，代表距离等衡量单位。

带权有向图：在有向图的基础上增加一个权值，代表距离等衡量单位。

图的表示

图的表示分为两种方法：邻接矩阵和邻接表。

基于邻接表的概念手动构建四种类型的图，演示如下：

// 有向图
let graph = {
    A: { B: null, C: null },
    B: { C: null },
    C: {},
}
// 无向图
let graph = {
    A: { B: null, C: null },
    B: { A: null, C: null },
    C: { A: null, B: null },
}
// 带权有向图
let graph = {
    A: { B: 20, C: 20 },
    B: { C: 40 },
    C: {},
}
// 带权无向图
let graph = {
    A: { B: 20, C: 30 },
    B: { A: 20, C: 40 },
    C: { A: 30, B: 40 },
}

面向对象方法封装邻接表

构造函数

class Graph {
    length: number
    vertices: { [key: string]: { [key: string]: null | number } }
    isDirected: boolean
    constructor(isDirected: boolean = false) {
        this.length = 0
        this.vertices = {}
        this.isDirected = isDirected
    }
}

增加顶点和边

顶点增加：利用传入key参数在顶点集合新建一个属性，值为一个空对象用于存储边。

addVertex(...vertices: string[]): Graph {
    vertices.forEach((key: string) => {
        this.vertices[key] = {}
        this.length++
    })
    return this
}

边增加需要处理的三种情况：

顶点不存在：执行addVertex增加顶点。
有向图：两个顶点间建立一条关联的边。
无向图：两个顶点间建立互相关联的两条边。

addEdge(v: string, edges: { [key: string]: null | number}): Graph {
    if (!this.vertices[v]) { this.addVertex(v) }
    for (const key in edges) {
        if (!this.vertices[key]) { this.addVertex(key) }
        this.vertices[v][key] = edges[key]
        if (!this.isDirected) {
            this.vertices[key][v] = edges[key]
        }
    }
    return this
}

删除顶点和边

顶点删除：需要删除与这个顶点与其他顶点关联的边。

removeVertex(v: string): Graph {
    delete this.vertices[v]
    for (const key in this.vertices) {
        if (!!this.vertices[key][v]) {
            delete this.vertices[key][v]
        }
    }
    this.length--
    return this
}

边删除：有向图，删除一个顶点关联的边即可；无向图，删除两条顶点互相关联的边。

removeEdge(v: string, w: string): Graph {
    delete this.vertices[v][w]
    if (!this.isDirected) {
        delete this.vertices[w][v]
    }
    return this
}

图的遍历

颜色标记

为图中的每一个顶点标记颜色，作为状态记录。三种颜色状态分别如下：

白色：未发现的顶点
灰色：被发现的顶点
黑色：已遍历过的顶点

// 初始化所有顶点颜色，作为初始的状态
const initColor = (vertices: { [key: string]: { [key: string]: null | number } })
    : { [key: string]: 'white' | 'gray' | 'black' } => {
    let color = {}
    for (const key in vertices) {
        color[key] = 'white'
    }
    return color
}

广度优先搜索（队列）

实现思路：

初始化所有的顶点状态为白色，选择一个初始顶点入队开始进行搜索。
当队列不为空，被选中的初始顶点出队。将这个顶点（通过边）关联的其他顶点入队，并为其标记为灰色。
当执行完第二步后，将初始顶点标记为黑色。然后第二步入队的顶点都会重复二、三步骤直到队列为空。

const breadthFirstSearch = (graph: Graph, startVertex: string): string[] => {
    let result: string[] = []
    let v: string = startVertex
    const color = initColor(graph.vertices)
    const queue = new Queue()
    queue.enqueue(v)
    while (!queue.isEmpty()) {
        v = queue.dequeue()
        for (const key in graph.vertices[v]) {
            if (color[key] === 'white') {
                queue.enqueue(key)
                color[key] = 'gray'
            }
        }
        color[v] = 'black'
        result.push(v)
    }
    return result
}

深度优先搜索（栈）

实现思路：与广度优先搜索步骤相同，队列换为栈即可。需要注意的是深度优先搜索结果不唯一。

const depthFirstSearch = (graph: Graph, startVertex: string): string[] => {
    let result: string[] = []
    let v: string = startVertex
    const color = initColor(graph.vertices)
    const stack = new Stack()
    stack.push(v)
    while (!stack.isEmpty()) {
        v = stack.pop()
        for (const key in graph.vertices[v]) {
            if (color[key] === 'white') {
                stack.push(key)
                color[key] = 'gray'
            }
        }
        color[v] = 'black'
        result.push(v)
    }
    return result
}

本文相关代码已放置我的Github仓库

加载全部内容