图的基本概念
图是一种非线性数据结构，它由一系列顶点和边组成。图可以分为有向图和无向图。在有向图中，边是有方向性的；而在无向图中，边没有方向性。
顶点
顶点是图中的基本单元，也称为节点。顶点可以表示现实世界中的实体，例如城市、人等。
边
边是连接两个顶点的连接。在有向图中，边是从一个顶点指向另一个顶点；在无向图中，边是双向的，没有方向性。
权值
在某些图中，边可能带有权值，表示从一个顶点到另一个顶点的距离或成本。
图的表示方法
图可以用多种方式来表示，其中最常用的是邻接矩阵和邻接表。
邻接矩阵
邻接矩阵是一种二维数组，用于表示图中的顶点之间的连接情况。对于一个具有n个顶点的图，邻接矩阵是一个n×n的矩阵。如果图是有向图，则矩阵中的每个元素要么是0（表示没有边），要么是1（表示存在边）。如果图是无向图，则矩阵是对称的。
示例
假设我们有一个无向图，它有三个顶点，顶点分别为A、B和C。边为：AB、AC和BC。那么其邻接矩阵如下所示：
let adjacencyMatrix = [
[0, 1, 1],
[1, 0, 1],
[1, 1, 0]
];优点
- 可以快速判断任意两个顶点之间是否存在边。
- 易于实现和理解。
缺点
- 对于稀疏图（边数远少于顶点数的平方），空间复杂度较高。
邻接表
邻接表是一种更节省空间的表示方法，它使用数组来存储每个顶点及其邻接顶点。邻接表通常由链表或数组列表构成，其中每个链表或数组列表表示一个顶点，并包含该顶点的所有邻接顶点。
示例
继续使用上面的例子，我们用邻接表来表示这个图：
let adjacencyList = {
'A': ['B', 'C'],
'B': ['A', 'C'],
'C': ['A', 'B']
};优点
- 节省空间，特别是对于稀疏图。
- 操作灵活，易于实现插入和删除操作。
缺点
- 判断两个顶点之间是否存在边需要遍历邻接表，效率较低。
权值图的表示
在实际应用中，图中的边常常带有权值。这种图被称为加权图。为了表示加权图，我们可以对邻接矩阵和邻接表进行扩展。
加权邻接矩阵
在加权图中，邻接矩阵中的元素不再是简单的0或1，而是边的权值。如果两个顶点之间没有边，则权值通常设为无穷大（或一个非常大的数字，以表示不存在的边）。
示例
假设我们有一个无向加权图，它有三个顶点，顶点分别为A、B和C。边及其权值为：AB=3，AC=5，BC=2。则其加权邻接矩阵如下所示：
let weightedAdjacencyMatrix = [
[0, 3, 5],
[3, 0, 2],
[5, 2, 0]
];加权邻接表
在加权邻接表中，除了存储每个顶点的邻接顶点外，还需要存储这些邻接顶点之间的权值。
示例
继续使用上面的例子，我们用加权邻接表来表示这个图：
let weightedAdjacencyList = {
'A': [{'vertex': 'B', 'weight': 3}, {'vertex': 'C', 'weight': 5}],
'B': [{'vertex': 'A', 'weight': 3}, {'vertex': 'C', 'weight': 2}],
'C': [{'vertex': 'A', 'weight': 5}, {'vertex': 'B', 'weight': 2}]
};总结
选择哪种表示方法取决于具体的应用场景。邻接矩阵适合于稠密图或需要频繁检查边的情况；而邻接表则更适合稀疏图或需要频繁更新边的情况。对于带权图，根据需要选择相应的加权表示方法即可。