鄰接列表和鄰接矩陣是電腦科學中表示圖的兩種常見方法。
鄰接清單：
優點：
缺點：
鄰接矩陣：
優點：
缺點：
重要提示
圖遍歷
找出最短路徑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中文網其他相關文章！
