做网站购买模板,国外商业网站建设,企业网站建设兴田德润怎么联系,网站建设公司友情链接文章目录 一#xff0c;实验目的二#xff0c;实验内容三#xff0c;实验要求四#xff0c;算法分析五#xff0c;示例代码8-1.cpp源码graph.h源码 六#xff0c;操作步骤七#xff0c;运行结果 一#xff0c;实验目的
1#xff0e;掌握图的邻接矩阵、邻接表的表示方… 文章目录 一实验目的二实验内容三实验要求四算法分析五示例代码8-1.cpp源码graph.h源码 六操作步骤七运行结果 一实验目的
1掌握图的邻接矩阵、邻接表的表示方法及建立算法 2掌握图的深度优先遍历、广度优先遍历等基本操作的算法 3掌握图的最小生成树、关键路径等应用问题的求解算法 4进一步加深对图的几种基本应用算法的理解逐步培养解决实际问题的编程能力。
二实验内容
已知无向连通图G如下图所示。完成图的下列基本操作 1建立图的邻接矩阵输出邻接矩阵 2建立图的邻接表输出邻接表 3求邻接表表示的图的深度优先遍历序列 4求邻接矩阵表示的图的深度优先遍历序列 5求邻接表表示的图的广度优先遍历序列 6求邻接矩阵表示的图的广度优先遍历序列。
三实验要求
1建立头文件graph.h其中定义了图的邻接矩阵和邻接表表示的存储结构本实验的其它实验题目也可共享使用其代码如下
#define MAXV 30 // 最大顶点数
typedef int InfoType;
//以下定义图的邻接矩阵数据结构
typedef struct { //定义图的顶点结构int no; //顶点编号InfoType info; //顶点其它信息可用于
} VertexType;
typedef struct { //定义图邻接矩阵VertexType vexs[MAXV]; //顶点向量int arcs[MAXV][MAXV]; //邻接矩阵int vexnum, arcnum; //图的当前顶点数和边数
} MGraph;
//以下定义图的邻接表数据结构
typedef struct ArcNode { //定义表结点类型int adjvex; //顶点序号int weight; //边或弧的权值struct ArcNode *nextarc; //指向下一个表结点的指针
} ArcNode;
typedef struct VNode { //定义头结点类型VertexType data;ArcNode *firstarc;
} VNode
//typedef VNode AdjList[MAXV]; //定义头结点数组
typedef struct { //定义图的邻接表类型VNode vertices[MAXV];int vexnum, arcnum;
} LGraph;2完善参考程序在程序中的下划线处填写适当的语句。 3设计测试数据调试、测试完善后的参考程序保存和打印测试结果对结果进行分析。
四算法分析
1深度优先搜索遍历算法 从图中某顶点v出发 ① 访问顶点v ② 依次从v的未被访问的邻接点出发对图进行深度优先遍历直至图中和v有路径相通的顶点都被访问 ③ 若此时图中尚有顶点未被访问则从一个未被访问的顶点出发重新进行深度优先遍历直到图中所有顶点均被访问过为止。
2广度优先搜索遍历算法 从图中某顶点vi出发 ① 访问顶点vi ② 访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ③ 依次从这些邻接点在步骤②中访问的顶点出发访问它们的所有未被访问的邻接点; 依此类推直到图中所有访问过的顶点的邻接点都被访问 ④ 若此时图中尚有顶点未被访问则从一个未被访问的顶点出发重新进行广度优先搜索遍历直到图中所有顶点均被访问过为止。 为实现③需要保存在步骤②中访问的顶点而且访问这些顶点的邻接点的顺序为先保存的顶点其邻接点先被访问。
五示例代码
8-1.cpp源码
#include iostream
#include cstdio
#include cstdlib
#include graph.h// 访问标志数组
int visited[MAXV];
// 广度优先遍历存储队列
int queue[MAXV];// 建立图的邻接矩阵
void CreatMG(MGraph mg) {int i, j;int A[7][7];mg.vexnum 7;mg.arcnum 9;for (i 0; i mg.vexnum; i) {for (j 0; j mg.vexnum; j) {A[i][j] 0;}}A[0][1] A[0][2] A[0][6] 1;A[1][3] 1;A[2][3] A[2][5] A[2][6] 1;A[3][4] 1;A[5][6] 1;for (i 1; i mg.vexnum; i) {for (j 0; j i; j) {A[i][j] A[j][i];}}for (i 0; i mg.vexnum; i) {for (j 0; j mg.vexnum; j) {mg.arcs[i][j] A[i][j];}}
}// 由图的邻接矩阵创建图的邻接表
void CreatLG(LGraph* lg, MGraph mg) {int i, j;ArcNode* p;lg (LGraph*)malloc(sizeof(LGraph));for (i 0; i mg.vexnum; i) {lg-vertices[i].firstarc NULL;}for (i 0; i mg.vexnum; i) {for (j mg.vexnum - 1; j 0; j--) {if (mg.arcs[i][j] ! 0) {p (ArcNode*)malloc(sizeof(ArcNode));p-adjvex j;p-weight mg.arcs[i][j];p-nextarc lg-vertices[i].firstarc;lg-vertices[i].firstarc p;}}}lg-vexnum mg.vexnum;lg-arcnum mg.arcnum;
}// 输出图的邻接矩阵
void OutputMG(MGraph mg) {int i, j;for (i 0; i mg.vexnum; i) {for (j 0; j mg.vexnum; j) {printf(%3d, mg.arcs[i][j]);}printf(\n);}
}// 输出图的邻接表
void OutputLG(LGraph* lg) {int i;ArcNode* p;for (i 0; i lg-vexnum; i) {p lg-vertices[i].firstarc;if (p) {printf(%3d, i);}while (p) {printf(%3d, p-adjvex);p p-nextarc;}printf(\n);}
}// 邻接表表示的图的递归深度优先遍历
void LDFS(LGraph* lg, int i) {ArcNode* p;printf(%3d, i);visited[i] 1;p lg-vertices[i].firstarc;while (p) {if (visited[p-adjvex] 0) {LDFS(lg, p-adjvex);}p p-nextarc;}
}// 邻接矩阵表示的图的递归深度优先遍历
void MDFS(MGraph mg, int i) {int j;printf(%3d, i);visited[i] 1;for (j 0; j mg.vexnum; j) {if (mg.arcs[i][j] ! 0 visited[j] 0) {MDFS(mg, j);}}
}// 邻接表表示的图的广度优先遍历
void LBFS(LGraph* lg, int s) {int i, v, w, front, rear;ArcNode* p;for (i 0; i lg-vexnum; i) {visited[i] 0;}front rear 0;printf(%3d, s);visited[s] 1;queue[rear] s;while (front rear) {v queue[front];for (p lg-vertices[v].firstarc; p ! NULL; p p-nextarc) {w p-adjvex;if (visited[w] 0) {printf(%3d, w);visited[w] 1;queue[rear] w;}}}
}// 邻接矩阵表示的图的广度优先遍历
void MBFS(MGraph mg, int s) {int i, j, v, front, rear;for (i 0; i mg.vexnum; i) {visited[i] 0;}front rear 0;printf(%3d, s);visited[s] 1;queue[rear] s;while (front rear) {v queue[front];for (i 0; i mg.vexnum; i) {for (j 0; j mg.vexnum; j) {if (mg.arcs[v][j] ! 0 visited[j] 0) {printf(%3d, j);visited[j] 1;queue[rear] j;}}}}
}int main() {LGraph* lg;MGraph mg;int i;CreatMG(mg);CreatLG(lg, mg);printf(1当前图的邻接矩阵是\n);OutputMG(mg);printf(2当前图的邻接表是\n);OutputLG(lg);for (i 0; i mg.vexnum; i) {visited[i] 0;}getchar();printf(3邻接表表示的图的深度优先遍历序列是);LDFS(lg, 0);getchar();for (i 0; i mg.vexnum; i) {visited[i] 0;}printf(4邻接矩阵表示的图的深度优先遍历序列是);MDFS(mg, 0);getchar();printf(5邻接表表示的图的广度优先遍历序列是);LBFS(lg, 0);getchar();printf(6邻接矩阵表示的图的广度优先遍历序列是);MBFS(mg, 0);printf(\n);return 0;
}graph.h源码
#pragma once
#ifndef GRAPH_H
#define GRAPH_H// 定义图的最大顶点数
const int MAXV 100;// 定义弧节点结构体
typedef struct ArcNode {int adjvex;int weight;struct ArcNode* nextarc;
} ArcNode;// 定义顶点结构体
typedef struct VNode {ArcNode* firstarc;
} VNode;// 定义邻接表结构体
typedef struct {VNode vertices[MAXV];int vexnum, arcnum;
} LGraph;// 定义邻接矩阵结构体
typedef struct {int arcs[MAXV][MAXV];int vexnum, arcnum;
} MGraph;#endif 六操作步骤
1双击Visual Studio程序快捷图标启动程序。
2之前创建过项目的话直接打开即可这里选择【创建新项目】。
3单击选择【空项目】——单击【下一步】按钮。
4编辑好项目的名称和存放路径然后单击【创建】按钮。
5创建C程序文件右击【源文件】——选择【添加】——【新建项】。 6输入项目名称8-1.cpp单击【添加】按钮。
7输入项目名称graph.h单击【添加】按钮此文件要定义 MGraph、LGraph、ArcNode 等类型同时定义 MAXV 常量。
8编写代码单击运行按钮运行程序。
七运行结果
1实验要求的测试结构。
2编写代码运行后的结果。
