首頁  >  文章  >  web前端  >  使用 Javascript 處理圖形資料結構

使用 Javascript 處理圖形資料結構

WBOY
WBOY原創
2024-08-12 18:43:23624瀏覽

Approaching Graphs Data Structure using Javascript

鄰接列表鄰接矩陣是電腦科學中表示的兩種常見方法。

鄰接清單:

  1. 鄰接表將圖表示為鍊錶陣列。
  2. 陣列的索引代表一個頂點,其鍊錶中的每個元素代表與該頂點形成邊的其他頂點。

優點:

  1. 表示稀疏圖(邊較少的圖)的空間效率。
  2. 增加頂點更容易。

缺點:

  1. 對於某些類型的查詢效率較低,例如檢查兩個頂點之間是否存在邊。 更複雜的資料結構。

鄰接矩陣:

  1. 鄰接矩陣將圖表示為二維數組,其中第 i 行第 j 列的單元表示頂點 i 和 j 之間的邊。

優點:

  1. 易於理解和實作。
  2. 對於密集圖(有更多邊的圖)非常有效。
  3. 快速檢查兩個頂點之間是否存在邊。

缺點:

  1. 需要更多空間(O(V^2),其中 V 是頂點數)。 增加頂點的時間複雜度為 O(V^2),可能比鄰接清單慢。

重要提示

  1. 事先告知面試官你將採用哪種方法,並告訴他/她的優點和缺點。

圖遍歷

  1. DFS(深度優先搜尋)(堆疊)
  2. BFS(呼吸優先搜尋)(隊列)

找出最短路徑BFS會更好

*有向圖與無向圖:*

  1. 有向圖,也稱為有向圖,是每條邊都有一個方向的圖。邊從一個頂點指向另一個頂點。

  2. 無向圖是邊沒有方向的圖。邊 (x, y) 與邊 (y, x) 相同。

加權與未加權圖表:

  1. 加權圖是為每條邊分配權重或成本的圖。這對於某些邊具有不同重要性或長度的問題非常有用。

  2. 未加權圖是所有邊的權重或成本相等的圖。

自循環:

  1. 自環是將頂點連接到自身的邊。

稀疏圖與密集圖:

  1. 稀疏圖是邊數接近最小邊數的圖。換句話說,頂點之間的邊很少。

  2. 稠密圖是邊數接近最大可能邊數的圖。換句話說,頂點之間有很多條邊。

循環圖與非循環圖:

  1. 循環圖是一種至少包含一個循環的圖(一條邊和頂點的路徑,其中頂點可以從自身到達)。

  2. 非循環圖是沒有循環的圖。一種特殊類型的無環圖稱為樹,是一種無環的連通無向圖。

// Weighted graph adjacency list would look like

{
1: [ {node: 2, weight: 50}, {node: 3, weight: 60}]
...
6: [{node: 1, weight: 40}, {node:5, weight:30 }, {node:4, weight: 90}]
}
class Graph {
    constructor() {
        this.adjList = {};
    }

    addNode(value) {
        this.adjList[value] = []
    }

    addEdge(node1, node2) {
        this.adjList[node1].push(node2);
        this.adjList[node2].push(node1);
    }

    removeEdge(node1, node2) {
        this.removeElement(node1, node2);
        this.removeElement(node2, node1);
    }

    removeElement(node, value) {
        const index = this.adjList[node].indexOf(value);
        this.adjList[node] = [...this.adjList[node].slice(0, index), ...this.adjList[node].slice(index+1)];
    }

    removeNode(node) {
        const connectedNodes = this.adjList[node];

        for (let connectedNode of connectedNodes) {
            this.removeElement(connectedNode, node);
        }

        delete this.adjList[node];
    }
depthFirstTraversal(startNode) {
        const stack = [];
        const visited = {};

        stack.push(startNode);
        visited[startNode] = true;

        while(stack.length > 0) {
            const currentNode = stack.pop();
            const connectedNodes = this.adjList[currentNode];
            console.log(currentNode);
            connectedNodes.forEach(connectedNode => {
                if (!visited[connectedNode]) {
                    visited[connectedNode] = true;
                    stack.push(connectedNode);
                }
            })
        }
    }

    breathFirstTraversal(startNode) {
        const queue = [];
        const visited = {}

        queue.push(startNode);
        visited[startNode] = true;

        while(queue.length > 0) {
            const currentElement = queue.shift();
            const connectedNodes = this.adjList[currentElement];
            console.log(currentElement);
            connectedNodes.forEach(connectedNode => {
                if (!visited[connectedNode]) {
                    visited[connectedNode]=true;
                    queue.push(connectedNode);
                }
            });
        }
    }
}

const test = new Graph();

test.addNode(1);
test.addNode(2);
test.addNode(3);
test.addNode(4);
test.addNode(5);
test.addNode(6);
test.addEdge(1,2)
test.addEdge(1,3)
test.addEdge(1,6)
test.addEdge(2, 3);
test.addEdge(2, 5);
test.addEdge(2, 4);
test.addEdge(3, 4);
test.addEdge(3, 5);
test.addEdge(4, 5);
test.addEdge(4, 6);
test.addEdge(5, 6);
console.log('After adding all node and Edge --> ', test.adjList)

test.removeNode(4);

console.log('After Removing node 4 --> ', test.adjList)
console.log('----------Depth First Traversal -------------')
test.depthFirstTraversal(1);
console.log('----------Breath First Traversal -------------')
test.breathFirstTraversal(1);

/*
After adding all node and Edge -->  {
  '1': [ 2, 3, 6 ],
  '2': [ 1, 3, 5, 4 ],
  '3': [ 1, 2, 4, 5 ],
  '4': [ 2, 3, 5, 6 ],
  '5': [ 2, 3, 4, 6 ],
  '6': [ 1, 4, 5 ]
}
After Removing node 4 -->  {
  '1': [ 2, 3, 6 ],
  '2': [ 1, 3, 5 ],
  '3': [ 1, 2, 5 ],
  '5': [ 2, 3, 6 ],
  '6': [ 1, 5 ]
}
----------Depth First Traversal -------------
1
6
5
3
2
----------Breath First Traversal -------------
1
2
3
6
5
*/

以上是使用 Javascript 處理圖形資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn