图的存储与操作.docx

实验七 图的存储与操作1. 实验内容 建立无向图的邻接矩阵存储；对建立的无向图，进行深度优先遍历；对建立的无向图，进行广度优先遍历。 建立一个有向图的邻接表存储结构；对建立的有向图，进行深度优先遍历； 对建立的有向图，进行广度优先遍历。2. 无向图建立和遍历的实现提示 本题采用图的邻接矩阵存储，即用一维数组存储图中顶点的信息，用二维数组存储图中边的信息（即各顶点之间的邻接关系）。 假设无向图G（V，E）有n个顶点，则邻接矩阵是一个nn的方阵，定义为： 设计实验用邻接矩阵类MGraph，包括遍历操作。const int MaxSize=10; /图中最多顶点个数template class MGraphpublic: MGraph(T a , int n, int e); /构造函数，初始化具有n个顶点e条边的无向图 void DFSTraverse(int v); /深度优先遍历图 void BFSTraverse(int v); /广度优先遍历图private: T vertexMaxSize; /存放图中顶点的数组 int arcMaxSizeMaxSize; /存放图中边的数组 int vertexNum, arcNum; /图的顶点数和边数; 设计构造函数，建立一个无向图的邻接矩阵存储。 假设图的顶点信息存放在数组an中，边的信息（即边所依附的顶点）由键盘输入，建立一个无向图的邻接矩阵存储的算法如下： 深度优先遍历算法 广度优先遍历算法3. 有向图建立和遍历的实现提示 邻接表存储结构是基于顺序存储与链接存储相结合的存储方法，基本思想是：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有顶点的边表的头指针和存储顶点信息的一维数组构成了顶点表。所以，在邻接表中存在两种结点结构，分别是顶点表结点和边表结点，如图6-1所示。 用C+中的结构类型描述上述结点。struct ArcNode /定义边表结点 int adjvex; /邻接点域 ArcNode *next;template struct VertexNode /定义顶点表结点 T vertex; ArcNode *firstedge; ; 设计实验用邻接表类ALGraph，包括遍历操作。const int MaxSize=10; /图的最大顶点数template class ALGraphpublic: ALGraph(T a , int n, int e); /构造函数，初始化一个有n个顶点e条边的有向图 ALGraph( ); /析构函数，释放邻接表中各边表结点的存储空间 void DFSTraverse(int v); /深度优先遍历图 void BFSTraverse(int v); /广度优先遍历图private: VertexNode adjlistMaxSize; /存放顶点表的数组 int vertexNum, arcNum; /图的顶点数和边数; 设计构造函数，建立有向图的邻接表存储。 深度优先遍历算法如下： 广度优先遍历算法如下：#includestdio.h#includestdlib.h#include #define MaxVertexNum 100 /定义最大顶点数typedef structchar vexsMaxVertexNum; /顶点表int edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表int n, e; /图中的顶点数n和边数eMGraph; /用邻接矩阵表示的图的类型/=建立邻接矩阵=void CreatMGraph(MGraph *G)int i, j, k;char a;printf(InputVertexNum(n) and EdgesNum(e): );scanf_s(%d,%d, &G-n, &G-e); /输入顶点数和边数scanf_s(%c, &a);printf(InputVertex string:);for (i = 0; in; i+)scanf_s(%c, &a);G-vexsi = a; /读入顶点信息，建立顶点表for (i = 0; in; i+)for (j = 0; jn; j+)G-edgesij = 0; /初始化邻接矩阵printf(Inputedges,Creat Adjacency Matrixn);for (k = 0; ke; k+) /读入e条边，建立邻接矩阵scanf_s(%d%d, &i, &j); /输入边（Vi，Vj）的顶点序号G-edgesij = 1;G-edgesji = 1; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句/=定义标志向量，为全局变量=typedef enum FALSE, TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(MGraph *G, int i) /以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是，矩阵int j;printf(%c, G-vexsi); /访问顶点Vivisitedi = TRUE; /置已访问标志for (j = 0; jn; j+) /依次搜索Vi的邻接点if (G-edgesij = 1 & !visitedj)DFSM(G, j); /（Vi，Vj）E，且Vj未访问过，故Vj为新出发点void DFS(MGraph *G)int i;for (i = 0; in; i+)visitedi = FALSE; /标志向量初始化for (i = 0; in; i+)if (!visitedi) /Vi未访问过DFSM(G, i); /以Vi为源点开始DFS搜索/=BFS：广度优先遍历=void BFS(MGraph *G, int k) /以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索int i, j, f = 0, r = 0;int cqMaxVertexNum; /定义队列 for (i = 0; in; i+)visitedi = FALSE; /标志向量初始化for (i = 0; in; i+)cqi = -1; /队列初始化printf(%c, G-vexsk); /访问源点Vkvisitedk = TRUE;cqr = k; /Vk已访问，将其入队。注意，实际上是将其序号入队while (cqf != -1) /队非空则执行i = cqf; f = f + 1; /Vf出队for (j = 0; jn; j+) /依次Vi的邻接点Vjif (G-edgesij = 1 & !visitedj) /Vj未访问printf(%c, G-vexsj); /访问Vjvisitedj = TRUE; r = r + 1; cqr = j; /访问过Vj入队/=main=void main()int i;MGraph *G;G = (MGraph *)malloc(sizeof(MGraph); /为图