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

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

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

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

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

圖的分類

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

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

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

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

圖的表示

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

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

// 有向圖
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 },
}
// 帶權(quán)有向圖
let graph = {
    A: { B: 20, C: 20 },
    B: { C: 40 },
    C: {},
}
// 帶權(quán)無向圖
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
    }
}

增加頂點和邊

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

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

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

頂點不存在：執(zhí)行addVertex增加頂點。
有向圖：兩個頂點間建立一條關(guān)聯(liá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
}

刪除頂點和邊

頂點刪除：需要刪除與這個頂點與其他頂點關(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
}

邊刪除：有向圖，刪除一個頂點關(guān)聯(liá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
}

圖的遍歷

顏色標記

為圖中的每一個頂點標記顏色，作為狀態(tài)記錄。三種顏色狀態(tài)分別如下：

白色：未發(fā)現(xiàn)的頂點
灰色：被發(fā)現(xià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)先搜索（隊列）

實現(xiàn)思路：

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

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)先搜索（棧）

實現(xiàn)思路：與廣度優(yōu)先搜索步驟相同，隊列換為棧即可。需要注意的是深度優(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倉庫 ??

項目地址：

Algorithmlib｜Graph

Algorithmlib｜Graph Traversal

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

您可能感興趣的文章: