> 引用：[https://blog.csdn.net/zjw\_python/article/details/85158998](https://blog.csdn.net/zjw_python/article/details/85158998)
[toc]
# 圖的存儲
存儲分為以下方法：
- 鄰接矩陣
- 鄰接表
- 十字鏈表
- 鄰接多重表
## 鄰接矩陣
用 `二維數組` 的方式來存儲圖結構。
- 無向圖
缺點：
1. 太浪費空間
2. 圖中的頂點經常是動態的，需要添加和刪除，二維數組尺寸是固定的不方便
- 有向圖
- 有向帶權圖
## 鄰接表
`數組+鏈表` 進行存儲。
圖的每一個頂點都是一個頭節點，其后連接著該頂點能夠直接達到的相鄰頂點。
## 鄰接多重表
鄰接多重表是 `無向圖` 的一種存儲方式。
## 逆鄰接表
每一個頂點作為鏈表的頭節點，后繼節點所存儲的是 `能夠直接達到該頂點` 的相鄰頂點。
## 十字鏈表
每一個頂點作為鏈表的頭節點，都可以有兩個鏈：
1. 所有這個節點可以到達的節點
2. 所有可以到達該節點的節點
# 代碼實現-鄰接表
~~~
class Graph {
constructor () {
this.vertices = []; // 用來存放圖中的頂點
this.adjList = new Set(); // 用來存放圖中的邊
}
// 向圖中添加一個新頂點
addVertex (v) {
if (!this.vertices.includes(v)) {
this.vertices.push(v);
this.adjList.set(v, []);
}
}
// 向圖中添加a和b兩個頂點之間的邊
addEdge (a, b) {
// 如果圖中沒有頂點a，先添加頂點a
if (!this.adjList.has(a)) {
this.addVertex(a);
}
// 如果圖中沒有頂點b，先添加頂點b
if (!this.adjList.has(b)) {
this.addVertex(b);
}
this.adjList.get(a).push(b); // 在頂點a中添加指向頂點b的邊
this.adjList.get(b).push(a); // 在頂點b中添加指向頂點a的邊
}
// 獲取圖的vertices
getVertices () {
return this.vertices;
}
// 獲取圖中的adjList
getAdjList () {
return this.adjList;
}
toString() {
let s = '';
this.vertices.forEach((v) => {
s += `${v} -> `;
this.adjList.get(v).forEach((n) => {
s += `${n} `;
});
s += '\n';
});
return s;
}
}
~~~
