日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

數據結構TypeScript之鄰接表實現示例詳解_其它

作者：前端技術獺 ? 更新時間： 2023-03-26 編程語言

圖的結構特點

圖由頂點和頂點之間的邊構成，記為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
}

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

  • 頂點不存在：執(zhí)行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
}

圖的遍歷

顏色標記

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

  • 白色：未發(fā)現的頂點
  • 灰色：被發(fā)現的頂點
  • 黑色：已遍歷過的頂點
// 初始化所有頂點顏色，作為初始的狀態(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)先搜索（隊列）

實現思路：

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

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

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

原文鏈接：https://juejin.cn/post/7193720313635405881

欄目分類
最近更新