亲宝软件园·资讯

展开

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

前端技术獭 人气: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
}

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

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仓库

加载全部内容

相关教程
猜你喜欢
用户评论