利用邻接矩阵实现无向图遍历及顶点度数计算

在IT和计算机科学的领域中，邻接矩阵是用于表示图形的一种方法，它是一个二维数组。在本次实验中，我们将会使用邻接矩阵来表示一个无向图，并通过它来实现图的基本操作，比如输入输出邻接矩阵、计算每个顶点的度、进行广度优先遍历（Breadth-First Search, BFS）和深度优先遍历（Depth-First Search, DFS）。 邻接矩阵是一种在图的节点数量确定时非常直观的数据结构。对于一个含有n个顶点的无向图，其邻接矩阵是一个n×n的二维数组。如果顶点i和顶点j之间有边相连，则邻接矩阵中的array[i][j]和array[j][i]的位置将会被标记，通常是将它们的值设置为1或其他非零值表示边的存在；如果两个顶点之间没有边相连，则相应的值为0。由于无向图中任意顶点对之间的连接是无方向性的，所以邻接矩阵是关于其主对角线对称的。 在存储无向图时，邻接矩阵具有以下特点： 1. 空间复杂度是固定的，与图中的边数无关，只与顶点数n有关，空间复杂度为O(n²)。 2. 能够快速判断任意两个顶点之间是否存在边（时间复杂度为O(1)）。 3. 通过邻接矩阵表示的无向图，在进行遍历时不需要额外的空间来存储已访问的顶点信息，因为遍历算法可以通过矩阵的修改来标记访问状态。 在本实验中，我们需要实现以下几个知识点： 1. 输入输出邻接矩阵：首先，需要能够创建一个邻接矩阵并正确地输入顶点和边的信息来构建无向图。之后，要能够输出该邻接矩阵，以可视化图的结构。 2. 计算每个顶点的度：无向图中顶点的度是指与该顶点相连的边的数量。在邻接矩阵中，可以通过累加顶点所在行或列的元素值（不包括对角线上的值，因为它们代表顶点自身与自身的连接），来计算出每个顶点的度。顶点i的度可以通过公式deg(i) = Σarray[i][j] (j=1 到 n, 且 i ≠ j)来得到。 3. 广度优先遍历（BFS）：广度优先遍历是一种按照“先来先服务”的顺序遍历图的算法。在无向图的BFS遍历中，通常需要一个队列来记录访问顺序。算法从一个起始顶点开始，将其标记为已访问，并将其加入队列中。随后，不断地从队列中取出一个顶点，并将其相邻且未访问过的顶点标记为已访问并加入队列，直到队列为空。 4. 深度优先遍历（DFS）：深度优先遍历是另一种遍历图的方法，它尽可能深地沿着一条路径探索，直到这条路径到达一个“死胡同”，然后再回溯到上一个分叉点继续探索另一条路径。在邻接矩阵的DFS遍历中，通常使用递归或栈来实现。算法从一个起始顶点开始，访问它，然后递归地访问一个未访问的邻接顶点，直到所有顶点都被访问过。 本实验将会帮助理解图的基本概念，掌握图的邻接矩阵表示法，以及实现图的基本遍历算法。通过这样的实践，可以加深对数据结构中图论部分的理解，并为处理更复杂的图算法打下坚实的基础。对于想要深入学习算法和数据结构的计算机科学学生或者从业者来说，这是一个很好的入门实验，也是理解后续更高级图算法（如最短路径、最小生成树、拓扑排序等）的基础。