> 引用：[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;
}
}
~~~
