C语言实现图的邻接矩阵操作：深度优先与广度优先遍历

需积分: 9 20 浏览量更新于2024-09-11 收藏 18KB TXT 举报

身份认证购VIP最低享 7 折!

30元优惠券

本文将介绍如何使用邻接矩阵来实现图的数据结构，包括深度优先遍历（DFS）和广度优先遍历（BFS），以及弧的插入与删除操作。在C语言环境下，可能需要对指针传递方式进行调整，如将引用符"&"改为"*"以适应某些编译器。在计算机科学中，图是一种非常重要的数据结构，用于表示对象之间的关系。邻接矩阵是图的一种常用存储方式，其中的二维数组表示图中各个顶点之间的连接关系。对于一个有向图，邻接矩阵是一个方阵，其中的每个元素表示从一个顶点到另一个顶点是否存在边；对于无向图，邻接矩阵是对称的，因为每条边可以双向通行。在邻接矩阵中，行和列代表图中的顶点，矩阵的元素表示顶点之间的连接。如果矩阵中的元素为1，则表示对应的两个顶点之间有一条边；若为0，则表示没有边。对于无向图，邻接矩阵是对称的，即如果矩阵[i][j]为1，则[j][i]也为1。在给出的代码中，定义了一个名为`MGraph`的结构体，包含了以下成员： 1. `VertexType vexs[MAX_VERTEX_NUM+1]`：存储顶点信息的数组。 2. `AdjMatrix arcs`：表示邻接矩阵的二维数组，每个元素是`VRType`类型，用于存储边的存在性。 3. `int vexnum, arcnum`：分别表示当前图中顶点的数量和边的数量。 4. `GraphKind kind`：表示图的类型，可以是有向图（DG）或无向图（UG）。 `MGraph`结构体提供了一系列操作方法，如创建图、显示图信息、销毁图、定位顶点、获取/设置顶点信息、计算顶点的度、添加/删除弧以及进行深度优先遍历和广度优先遍历。深度优先遍历（DFS）和广度优先遍历（BFS）是图遍历的两种主要方法，用于访问图中所有顶点。DFS通常采用递归方式，从给定的起点开始，沿着边尽可能深地探索图的分支，直到访问到所有可达的顶点。BFS则使用队列，先访问起点的所有邻居，再依次访问它们的邻居，直至遍历完所有顶点。在实现这些操作时，需要注意邻接矩阵的更新，例如在`InsertArc`和`DeleteArc`函数中，不仅要在起点的行对应位置设置1，对于无向图，还要在终点的列对应位置设置1。同样，在进行遍历时，需要借助`visit`数组来跟踪已访问过的顶点，避免重复访问。在实际编程中，为确保在不同的编译环境下正常运行，可能会需要对指针的传递方式进行调整，比如在某些编译器中，可能需要将引用符`&`改为指针`*`。这是因为C语言不支持引用，而C++支持。在C语言中，通常使用指针来模拟引用的效果。总结起来，邻接矩阵是一种直观且易于实现的图数据结构，适用于存储图的边信息，并能方便地执行图的各种操作，如遍历和边的增删。在实际应用中，根据具体的编程环境和需求，可能需要适当地调整代码细节。

资源详情

资源推荐

1. 题目
ADT Graph {

数据对象V： V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
R＝{VR} VR＝{<v1,v2>| v1,v2∈V且P(v1,v2)，<v1,v2>表示从v1到v2的弧，谓词P(v1,v2)
定义了弧<v1,v2>的意义或信息 }
基本操作P：
结构的建立和销毁:
CreateGraph(&G); // 按V和VR的定义构造图G。
CreatDG(&G); // 构造有向图
CreatUG(&G)；// 构造无向图
Display(&G);//打印图的相关信息
DestroyGraph(&G); // 销毁图G。
对顶点的访问操作:
LocatVex(&G, u); // 若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。
GetVex(&G, v); // 返回v的值。
PutVex(&G , i , v); // 对第i个顶点赋值v。
Degree(&G , i); // 求第i个顶点的出度，入度和总度数
插入和删除弧:
InsertArc( & G, v1, v2); // 在G中增添弧<v1,v2>，若G是无向的，则还增添对称弧<v2,v1>。
DeleteArc( & G, v1, v2); //在G中删除弧<v1,v2>，若G是无向的，则还删除对称弧<v2,v1>。
遍历:
DFSTraverse(&G, i); //从第i个顶点起深度优先遍历，对每个顶点调用函数，Visit一次且仅一次。
BFSTraverse(&G , i) //从第i个顶点起深度优先遍历，对每个顶点调用函数，Visit一次且仅一次。

｝

2．存储结构定义
存储结构：图的邻接矩阵表示