图的邻接矩阵与邻接表实现及算法

本实验报告主要探讨了图的两种数据结构表示方法——邻接矩阵和邻接表，并在C语言中进行了实现。报告涵盖了无向网的构建、基本图操作以及图的遍历算法，包括广度优先遍历和深度优先遍历。 一、邻接矩阵 邻接矩阵是表示图的一种常用方式，特别是在处理稠密图时效率较高。对于无向图，邻接矩阵是一个n×n的二维数组，其中n是图中顶点的数量。数组的每个元素代表两个顶点之间是否存在边。如果顶点i和j之间有边，那么矩阵的acr[i][j]和acr[j][i]值均为1；否则，值为0。在C语言中，可以使用如下的数据结构来表示邻接矩阵： ```c typedef struct graph { int arc[n][n]; char vex[n]; int node_num, edge_num; } gr; ``` 基本操作包括： 1. Creat()：初始化矩阵，输入边和点的关系。 2. near()：输入查找的点，查找相应行的存在的点。 3. 求图中与顶点i邻接的第一个顶点。 4. 求图中顶点i相对于顶点j的下一个邻接点。 5. 图的广度优先遍历和深度优先遍历。 二、邻接表 邻接表适用于稀疏图，它通过链表存储与每个顶点相邻的边。每个顶点对应一个链表，链表中节点包含邻接顶点的信息。在C语言中，可以使用如下的数据结构表示邻接表： ```c typedef struct edgenode { int adjvex; struct edgenode* next; } edgenode; typedef struct node { char data; edgenode* first; } node, adj[maxvex]; typedef struct { adj ad; int vexnum, edge_num; } gr; ``` 同样，邻接表也支持与邻接矩阵相同的基本操作，包括建立无向网的邻接表、寻找与顶点i邻接的第一个顶点、找到下一个邻接点等。 三、图遍历算法 1. 广度优先遍历（BFS）：使用队列进行层次遍历，先访问离起点近的顶点，再访问远的顶点。 2. 深度优先遍历（DFS）：使用栈或递归实现，沿着某条路径深入探索，直到无法再深入时回溯。 在C语言中，遍历算法通常会涉及一个布尔数组`visited[]`，用于标记顶点是否已被访问，避免重复访问。 总结，邻接矩阵和邻接表是图论中两种重要的数据结构，它们各有优缺点，适用于不同类型的图。邻接矩阵在处理稠密图时效率高，而邻接表在处理稀疏图时内存效率更高。了解和掌握这两种数据结构及其操作，对于理解和实现图的算法至关重要。