C++中图的定义及其相关概念

在计算机科学中，图是一种用于表示物体之间关系的数据结构。它由一组节点和一组连接这些节点的边组成。

C++中，图可以使用邻接表或邻接矩阵等数据结构来表示。

邻接表是由一组链表组成，每个节点对应一个链表，该节点的所有邻居节点都存储在该链表中。

邻接矩阵是由一个二维数组组成，其中每个元素表示两个节点之间是否有边。

图的相关概念包括：

1. 节点/顶点：图中的基本单位，代表一个实体或对象。

2. 边：节点之间的连接。

3. 有向图：每条边都有一个方向。

4. 无向图：每条边没有方向。

5. 权重：边可以带有一个数值，表示该边的权重。

6. 连通：在无向图中，如果从一个节点可以到达另一个节点，则这两个节点是连通的。

7. 强连通：在有向图中，如果从一个节点可以到达另一个节点，并且从另一个节点也可以到达该节点，则这两个节点是强连通的。

8. 出度和入度：对于有向图中的一个节点，它的出度是指从该节点出发的边的数量，入度是指指向该节点的边的数量。

9. 子图：由原图中一部分节点和边构成的图称为子图。

10. 连通分量：无向图中的极大连通子图称为连通分量，有向图中的极大强连通子图称为强连通分量。

在图的遍历中，常见的算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。

邻接矩阵和邻接表是图的两种常用存储方式。它们分别有什么特点和适用场景？

邻接矩阵：

邻接矩阵是图的一种存储方式，它用一个二维数组来表示图中所有顶点之间的关系。对于有 $n$ 个顶点的无向图或有向图，邻接矩阵的大小为 $n \\times n$。如果顶点 $i$ 与顶点 $j$ 之间存在一条边，则邻接矩阵中 $a_{ij}$ 的值为 $1$，否则为 $0$。对于有权图，邻接矩阵中的元素可以存储边的权值。

邻接矩阵的优点是易于实现和理解，可以快速地查询任意两个顶点之间是否有边。但是，对于稀疏图（即边数相对于总边数很少的图），邻接矩阵会浪费大量空间，因为矩阵中大部分元素都是 $0$，而且在添加或删除边时，需要修改矩阵中的元素，这个过程比较费时。

邻接表：

邻接表是图的另一种存储方式，它用一个数组和一些链表来表示图中所有顶点之间的关系。数组中每个元素对应一个顶点，而链表中存储了与该顶点相邻的所有顶点。对于无向图，邻接表中每条边都会被表示两次，因为每条边都连接了两个顶点。对于有向图，只有一个方向会被存储。

邻接表的优点是可以有效地存储稀疏图，因为只需要存储存在的边，而不需要存储不存在的边，节省了空间。在添加或删除边时，只需要修改链表中的指针，效率比邻接矩阵高。但是，查询任意两个顶点之间是否有边需要遍历链表，效率相对较低。

因此，邻接矩阵适用于稠密图，而邻接表适用于稀疏图。如果要同时兼顾空间和时间效率，可以采用邻接表的变体，比如邻接多重表、十字链表等。

以下是几种常见图的示意图：

1. 无向图

   1 -- 2
   |    |
   4 -- 3

1. 有向图

   1 -> 2 -> 3
   |         |
   v         v
   4 <- 5 <- 6

1. 带权图

       1(1) -- 2(2)
      /  |    /  |
   (3)   |(5)(2) |
    /    v  /    v
  4(4)   3(6)   5(1)

1. 有环图

  1 -> 2 -> 3 -> 4 -> 1

1. 无环图

   1 -> 2 -> 3
         ^    |
         |    v
         6 <- 5

1. 完全图

   1 -- 2 -- 3 -- 4
   |    |    |    |
   5 -- 6 -- 7 -- 8

注意：以上仅是示意图，实际上一个图可能更加复杂。