TypeScript 邻接表实现图结构：增删改查与 BFS/DFS 遍历完整指南

图的结构特点

图是一种非线性数据结构，由顶点集合 V 和边集合 E 构成，通常记作 G(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 仓库 👇

项目地址：

Algorithmlib｜Graph

Algorithmlib｜Graph Traversal

以上就是数据结构 TS 之邻接表实现示例详解的详细内容，更多关于 TS 数据结构邻接表的资料请关注本站其它相关文章！

TypeScript 实现图数据结构：邻接表构建与遍历详解