鄰接列表和鄰接矩陣是電腦科學中表示圖的兩種常見方法。
鄰接清單:
優點:
缺點:
鄰接矩陣:
優點:
缺點:
重要提示
圖遍歷
找出最短路徑BFS會更好
*有向圖與無向圖:*
有向圖,也稱為有向圖,是每條邊都有一個方向的圖。邊從一個頂點指向另一個頂點。
無向圖是邊沒有方向的圖。邊 (x, y) 與邊 (y, x) 相同。
加權與未加權圖表:
加權圖是為每條邊分配權重或成本的圖。這對於某些邊具有不同重要性或長度的問題非常有用。
未加權圖是所有邊的權重或成本相等的圖。
自循環:
稀疏圖與密集圖:
稀疏圖是邊數接近最小邊數的圖。換句話說,頂點之間的邊很少。
稠密圖是邊數接近最大可能邊數的圖。換句話說,頂點之間有很多條邊。
循環圖與非循環圖:
循環圖是一種至少包含一個循環的圖(一條邊和頂點的路徑,其中頂點可以從自身到達)。
非循環圖是沒有循環的圖。一種特殊類型的無環圖稱為樹,是一種無環的連通無向圖。
// 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中文網其他相關文章!