图是一种复杂的数据结构，用于表示多对多的关系。它由一组顶点（或节点）以及连接这些顶点的边（或弧）组成。在计算机科学中，图常用于表示网络，如社交网络、通信网络和交通网络等。图可以是有向的（边有方向）或无向的（边没有方向），可以是加权的（边有权值）或非加权的。本文将介绍两种常见的图表示方法：邻接矩阵和邻接表，并通过C#语言的例子来演示它们的使用。

邻接矩阵

邻接矩阵是表示图的一种方法，其中矩阵的每个元素表示顶点之间的关系。对于无向图，邻接矩阵是对称的；对于有向图，则不一定。在邻接矩阵中，如果顶点i和顶点j之间有边相连，则矩阵的(i, j)位置为1（或边的权重，如果是加权图），否则为0。

例子1：无向非加权图的邻接矩阵

考虑一个无向非加权图，有4个顶点，边如下：

C#
1 -- 2
|  /
| /
3 -- 4

该图的邻接矩阵表示为：

text
  1 2 3 4
1 0 1 1 0
2 1 0 1 0
3 1 1 0 1
4 0 0 1 0

在C#中，我们可以使用二维数组来实现邻接矩阵：

C#
int[,] adjacencyMatrix = {
    { 0, 1, 1, 0 },
    { 1, 0, 1, 0 },
    { 1, 1, 0, 1 },
    { 0, 0, 1, 0 }
};

例子2：有向加权图的邻接矩阵

现在考虑一个有向加权图，顶点和边如下：

C#
1 --> 2 (3)
1 --> 3 (2)
3 --> 4 (4)

其邻接矩阵表示为：

text
  1  2  3  4
1 0  3  2  0
2 0  0  0  0
3 0  0  0  4
4 0  0  0  0

在C#中的表示：

C#
int[,] adjacencyMatrix = {
    { 0, 3, 2, 0 },
    { 0, 0, 0, 0 },
    { 0, 0, 0, 4 },
    { 0, 0, 0, 0 }
};

邻接表

邻接表是另一种图的表示方法，它使用数组或链表来表示每个顶点的邻接顶点。相比邻接矩阵，邻接表在稀疏图中更节省空间，因为它只存储存在的边。

例子3：无向非加权图的邻接表

使用同样的无向非加权图：

C#
1 -- 2
|  /
| /
3 -- 4

邻接表的表示为：

• 顶点 1 与顶点 2 和顶点 3 相连
• 顶点 2 与顶点 1 和顶点 3 相连
• 顶点 3 与顶点 1、顶点 2 和顶点 4 相连
• 顶点 4 只与顶点 3 相连

text
1: 2 -> 3
2: 1 -> 3
3: 1 -> 2 -> 4
4: 3

在C#中，我们可以使用列表的列表来实现邻接表：

C#
List<List<int>> adjacencyList = new List<List<int>>() {
    new List<int> { 2, 3 },  // 邻接于顶点1
    new List<int> { 1, 3 },  // 邻接于顶点2
    new List<int> { 1, 2, 4 }, // 邻接于顶点3
    new List<int> { 3 }       // 邻接于顶点4
};

例子4：有向加权图的邻接表

对于之前的有向加权图：

C#
1 --> 2 (3)
1 --> 3 (2)
3 --> 4 (4)

邻接表表示为（这里使用元组来表示权重）：

text
1: (2, 3) -> (3, 2)
2:
3: (4, 4)
4: 

在C#中的表示：

C#
List<List<Tuple<int, int>>> adjacencyList = new List<List<Tuple<int, int>>>() {
    new List<Tuple<int, int>> { Tuple.Create(2, 3), Tuple.Create(3, 2) }, // 邻接于顶点1
    new List<Tuple<int, int>> { }, // 邻接于顶点2
    new List<Tuple<int, int>> { Tuple.Create(4, 4) }, // 邻接于顶点3
    new List<Tuple<int, int>> { } // 邻接于顶点4
};

结论

邻接矩阵和邻接表是表示图的两种主要方法。选择哪一种取决于具体的应用场景和图的特性。邻接矩阵易于实现和理解，但可能会浪费空间，特别是在稀疏图中。相反，邻接表更加节省空间，特别是当图中的边远少于顶点对时，但它的实现可能会更复杂一些。在实际应用中，应根据图的大小和密度来选择最合适的表示方法。