快捷導(dǎo)航

數(shù)據(jù)結(jié)構(gòu)TypeScript之鄰接表實(shí)現(xiàn)示例詳解

更新時(shí)間：2023年01月30日 09:18:38 作者：前端技術(shù)獺

這篇文章主要為大家介紹了數(shù)據(jù)結(jié)構(gòu)TypeScript之鄰接表實(shí)現(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

圖的結(jié)構(gòu)特點(diǎn)

圖由頂點(diǎn)和頂點(diǎn)之間的邊構(gòu)成，記為G(V, E)。其中V是頂點(diǎn)集合，E是邊集合。作為一種非線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)，頂點(diǎn)之間存在多對(duì)多關(guān)系。

圖的分類(lèi)

無(wú)向圖：兩個(gè)頂點(diǎn)之間有兩條互相關(guān)聯(lián)的邊。A和B之間為雙向互通。

有向圖：兩個(gè)頂點(diǎn)之間有一條或兩條關(guān)聯(lián)的邊。從A到B或者從B到A，只能單向通過(guò)。

帶權(quán)無(wú)向圖：在無(wú)向圖的基礎(chǔ)上增加一個(gè)權(quán)值，代表距離等衡量單位。

帶權(quán)有向圖：在有向圖的基礎(chǔ)上增加一個(gè)權(quán)值，代表距離等衡量單位。

圖的表示

圖的表示分為兩種方法：鄰接矩陣和鄰接表。

基于鄰接表的概念手動(dòng)構(gòu)建四種類(lèi)型的圖，演示如下：

// 有向圖
let graph = {
    A: { B: null, C: null },
    B: { C: null },
    C: {},
}
// 無(wú)向圖
let graph = {
    A: { B: null, C: null },
    B: { A: null, C: null },
    C: { A: null, B: null },
}
// 帶權(quán)有向圖
let graph = {
    A: { B: 20, C: 20 },
    B: { C: 40 },
    C: {},
}
// 帶權(quán)無(wú)向圖
let graph = {
    A: { B: 20, C: 30 },
    B: { A: 20, C: 40 },
    C: { A: 30, B: 40 },
}

面向?qū)ο蠓椒ǚ庋b鄰接表

構(gòu)造函數(shù)

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
    }
}

增加頂點(diǎn)和邊

頂點(diǎn)增加：利用傳入key參數(shù)在頂點(diǎn)集合新建一個(gè)屬性，值為一個(gè)空對(duì)象用于存儲(chǔ)邊。

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

邊增加需要處理的三種情況：

頂點(diǎn)不存在：執(zhí)行addVertex增加頂點(diǎn)。
有向圖：兩個(gè)頂點(diǎn)間建立一條關(guān)聯(lián)的邊。
無(wú)向圖：兩個(gè)頂點(diǎn)間建立互相關(guān)聯(lián)的兩條邊。

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
}

刪除頂點(diǎn)和邊

頂點(diǎn)刪除：需要?jiǎng)h除與這個(gè)頂點(diǎn)與其他頂點(diǎn)關(guān)聯(lián)的邊。

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
}

邊刪除：有向圖，刪除一個(gè)頂點(diǎn)關(guān)聯(lián)的邊即可；無(wú)向圖，刪除兩條頂點(diǎn)互相關(guān)聯(lián)的邊。

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

圖的遍歷

顏色標(biāo)記

為圖中的每一個(gè)頂點(diǎn)標(biāo)記顏色，作為狀態(tài)記錄。三種顏色狀態(tài)分別如下：

白色：未發(fā)現(xiàn)的頂點(diǎn)
灰色：被發(fā)現(xiàn)的頂點(diǎn)
黑色：已遍歷過(guò)的頂點(diǎn)

// 初始化所有頂點(diǎn)顏色，作為初始的狀態(tài)
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
}

廣度優(yōu)先搜索（隊(duì)列）

實(shí)現(xiàn)思路：

初始化所有的頂點(diǎn)狀態(tài)為白色，選擇一個(gè)初始頂點(diǎn)入隊(duì)開(kāi)始進(jìn)行搜索。
當(dāng)隊(duì)列不為空，被選中的初始頂點(diǎn)出隊(duì)。將這個(gè)頂點(diǎn)（通過(guò)邊）關(guān)聯(lián)的其他頂點(diǎn)入隊(duì)，并為其標(biāo)記為灰色。
當(dāng)執(zhí)行完第二步后，將初始頂點(diǎn)標(biāo)記為黑色。然后第二步入隊(duì)的頂點(diǎn)都會(huì)重復(fù)二、三步驟直到隊(duì)列為空。

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
}

深度優(yōu)先搜索（棧）

實(shí)現(xiàn)思路：與廣度優(yōu)先搜索步驟相同，隊(duì)列換為棧即可。需要注意的是深度優(yōu)先搜索結(jié)果不唯一。

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
}

本文相關(guān)代碼已放置我的Github倉(cāng)庫(kù) ??

項(xiàng)目地址：

Algorithmlib｜Graph

Algorithmlib｜Graph Traversal

以上就是數(shù)據(jù)結(jié)構(gòu)TS之鄰接表實(shí)現(xiàn)示例詳解的詳細(xì)內(nèi)容，更多關(guān)于TS數(shù)據(jù)結(jié)構(gòu)鄰接表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: