用哪个软件做网站,怎么做二维码进入公司网站,wordpress文章id连续,建网站 北京实验十一 图
一、实验目的与要求
1#xff09;掌握图的存储表示与操作实现。
2#xff09;掌握图的连通性及其应用。
二、 实验内容
1.用邻接表存储一个图形结构#xff0c;并计算每个顶点的度。 2. 采用深度和广度优先搜索算法#xff0c;遍历上述这张图#xff0c;…实验十一 图
一、实验目的与要求
1掌握图的存储表示与操作实现。
2掌握图的连通性及其应用。
二、 实验内容
1.用邻接表存储一个图形结构并计算每个顶点的度。 2. 采用深度和广度优先搜索算法遍历上述这张图并输出遍历结果。
三、实验结果
1请将调试通过的运行结果截图粘贴在下面并说明测试用例、运行过程和算法步骤。
2请分析算法的时间复杂度。
3请将源代码必要的注释cpp文件压缩上传上传附件。 题目1
1
测试用例
测试用例为总结点数为4、总边数为5的无向图如下图所示。 运行结果 运行过程
通过邻接表创建无向连通图-通过for循环遍历并输出邻接表结果-通过for循环计算并输出各顶点的度数。
2
算法步骤和时间复杂度分析
图的邻接表存储类似于树的孩子链表表示法。对于图中每个顶点vi建立一个链表第i个链表中的结点表示依附于vi的边。每个链表上附设一个头结点和一个尾结点。
假设需要存储的图的顶点数为V边数为E。如果存储的是无向图那么遍历时先访问顶点数组的各个元素再访问其对应的边链表由于有V个节点而且无向图的E条边在边链表中会出现两次即边共出现2E次所以一共的访问次数为V2E。因此算法的时间复杂度为O(|V|2|E|)。 对于n个顶点无向图的邻接表顶点vi的度恰为第i个链表中的结点个数。因此可以计算无向图中每个顶点的度。 3
实验源代码
#include iostream
using namespace std;
#define MVNum 100//最大顶点数 typedef char VerTexType;//顶点信息
typedef int OtherInfo;//和边相关的信息 //边结点
typedef struct ArcNode{int adjvex;//该边所指向的顶点的位置 struct ArcNode *nextarc;//指向下一条边的指针 OtherInfo info;//和边相关的信息
}ArcNode; //顶点
typedef struct VNode{ VerTexType data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];//AdjList表示邻接表类型 typedef struct{ AdjList vertices;//邻接表 int vexnum, arcnum;//图的当前顶点数和边数
}ALGraph;//确定点v在G中的位置
int LocateVex(ALGraph G,VerTexType v){for(int i 0; i G.vexnum; i){if(G.vertices[i].data v){return i;//顶点已经存在返回序号i }}return -1;
}//采用邻接表表示法创建无向图G
void CreateUDG(ALGraph G){int i , k;cout 请输入总顶点数;cin G.vexnum;cout 请输入总边数;cin G.arcnum;cout endl;cout 输入点的名称 endl;for(i 0; i G.vexnum; i){ cout 请输入第 (i1) 个点的名称:;cin G.vertices[i].data;//输入顶点值 G.vertices[i].firstarcNULL;//初始化表头结点的指针域为NULL }cout endl;cout 请输入一条边依附的顶点endl;for(k 0; k G.arcnum;k){VerTexType v1 , v2;//顶点名字 int i,j;cout 请输入第 (k 1) 条边依附的顶点:;cin v1 v2;//输入边的两个顶点 i LocateVex(G, v1);//确定第一个点的位置 j LocateVex(G, v2);//确定第二个点的位置ArcNode *p1new ArcNode;//生成一个新的边结点*p1p1-adjvexj;//邻接点序号为jp1-nextarc G.vertices[i].firstarc; G.vertices[i].firstarcp1;//将新结点*p1插入顶点vi的边表头部ArcNode *p2new ArcNode;//生成另一个对称的新的边结点*p2 p2-adjvexi;//邻接点序号为i p2-nextarc G.vertices[j].firstarc; G.vertices[j].firstarcp2;//将新结点*p2插入顶点vj的边表头部 }
}//输出邻接表
void Show(ALGraph G){coutendl;int i;coutendl邻接表为endl; for(i 0 ; i G.vexnum ; i){VNode temp G.vertices[i];ArcNode *p temp.firstarc;if(p NULL){cout G.vertices[i].data;cout endl;}else{cout temp.data;while(p){cout -;cout p-adjvex;p p-nextarc;}}cout endl;}
}//计算度数
void CountDegree(ALGraph *G){coutendl;int i,j,k,degree;int count10;ArcNode *p;for(i0;iG-vexnum;i){degree0;pG-vertices[i].firstarc;while(p!NULL){degree;pp-nextarc ;} if(i!G-vexnum -1){coutdegree ;}else{coutdegree;}}
}int main(){ALGraph G;CreateUDG(G);Show(G);coutendl各顶点度数依次为endl;CountDegree(G);return 0;
}
题目2
1
测试用例
下图所示的总顶点数的9总边数为10的无向连通图。人为设置从A点开始遍历。 运行结果
深度优先 广度优先 运行过程
深度优先
通过邻接表创建无向连通图-输入遍历起点的名称-判断起点是否在无向图内-调用DFS函数进行深度遍历。
广度优先
通过邻接矩阵和队列创建无向连通图-输入遍历起点的名称-判断起点是否在无向图内-调用BFS函数进行深度遍历。
2
算法步骤和时间复杂度分析
深度优先
假设图的顶点个数为n边的个数为e。本算法的执行时间主要耗费在递归调用DFS函数上。当访问某顶点时DFS的执行时间主要耗费在从该顶点出发搜索其所有邻接点上。采用邻接表作为图的存储结构时对n个顶点访问就需要对所有链表中的e个表结点检查一遍。因此算法的时间复杂度为O(ne)。 广度优先
假设图的顶点个数为n边的个数为e。本算法对图中的每一个顶点均入队一次。当访问某个顶点时执行时间主要耗费在从该顶点出发搜索其所有邻接点上。采用邻接矩阵作为图的存储结构时查找每一个顶点的邻接点所需要的时间为O(n2)。因此算法的时间复杂度为O(n2)。 3
实验源代码
深度优先
//深度优先
#include iostream
#include cstring
#include cstdio
using namespace std;#define MVNum 100
typedef char VerTexType; typedef struct ArcNode{ //边结点 int adjvex; //该边所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针
}ArcNode; typedef struct VNode{ VerTexType data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList表示邻接表类型 typedef struct{AdjList vertices; //邻接表 int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;bool visited[MVNum];//访问标志数组其初值为false //确定点v在G中的位置
int LocateVex(ALGraph G , VerTexType v){for(int i 0; i G.vexnum; i){if(G.vertices[i].data v){return i;}}return -1;
}//采用邻接表表示法创建无向图G
void CreateUDG(ALGraph G){ int i , k;cout 请输入总顶点数总边数;cin G.vexnum G.arcnum;cout endl;cout 输入点的名称 endl;//输入各点构造表头结点表for(i 0; i G.vexnum; i){ cout 请输入第 (i1) 个点的名称:;cin G.vertices[i].data;//输入顶点值 G.vertices[i].firstarcNULL; }cout endl;cout 输入边依附的顶点 endl;//输入各边构造邻接表for(k 0; k G.arcnum;k){ VerTexType v1 , v2;int i , j;cout 请输入第 (k 1) 条边依附的顶点:;cin v1 v2; i LocateVex(G, v1); j LocateVex(G, v2);//确定v1和v2在G中位置即顶点在G.vertices中的序号 ArcNode *p1new ArcNode;//生成一个新的边结点*p1 p1-adjvexj;//邻接点序号为j p1-nextarc G.vertices[i].firstarc; G.vertices[i].firstarcp1; //将新结点*p1插入顶点vi的边表头部ArcNode *p2new ArcNode;//生成另一个对称的新的边结点*p2 p2-adjvexi;//邻接点序号为i p2-nextarc G.vertices[j].firstarc;G.vertices[j].firstarcp2;//将新结点*p2插入顶点vj的边表头部 }
}//深度优先
void DFS(ALGraph G, int v){ cout G.vertices[v].data -; visited[v] true;//访问第v个顶点并置访问标志数组相应分量值为true ArcNode *p G.vertices[v].firstarc;//p指向v的边链表的第一个边结点 //边结点非空while(p ! NULL){ int w p-adjvex; //表示w是v的邻接点 if(!visited[w]){DFS(G, w);//如果w未访问则递归调用DFS }p p-nextarc;//p指向下一个边结点 }
}int main(){ALGraph G;CreateUDG(G);cout endl;cout 无向连通图G创建完成 endl endl;cout 请输入遍历连通图的起始点;VerTexType c;cin c;int i;for(i 0 ; i G.vexnum ; i){if(c G.vertices[i].data){break;}}cout endl;while(i G.vexnum){cout 该点不存在请重新输入 endl;cout 请输入遍历连通图的起始点;cin c;for(i 0 ; i G.vexnum ; i){if(c G.vertices[i].data){break;}}}cout 深度优先搜索遍历图结果为 endl;DFS(G , i);return 0;
}广度优先
//广度优先
#include iostream
using namespace std;#define MVNum 100
#define MAXQSIZE 100 typedef char VerTexType;
typedef int ArcType;
bool visited[MVNum];//访问标志数组其初值为false //图的邻接矩阵存储表示-
typedef struct{ VerTexType vexs[MVNum];//顶点表ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum,arcnum;//图的当前点数和边数
}Graph;//队列
typedef struct{ArcType *base;//初始化的动态分配存储空间int front;//头指针int rear;//尾指针队尾元素的下一个位置
}sqQueue;//构造一个空队列Q
void InitQueue(sqQueue Q){Q.base new ArcType[MAXQSIZE];if(!Q.base){exit(1);}Q.front Q.rear 0;
}//插入元素e为Q的新的队尾元素
void EnQueue(sqQueue Q, ArcType e){if((Q.rear 1) % MAXQSIZE Q.front){return;}Q.base[Q.rear] e;Q.rear (Q.rear 1) % MAXQSIZE;
}//判断是否为空队
bool QueueEmpty(sqQueue Q){if(Q.rear Q.front){return true;}return false;
}//队头元素出队
void DeQueue(sqQueue Q, ArcType u){u Q.base[Q.front];Q.front (Q.front 1) % MAXQSIZE;
}//确定点v在G中的位置
int LocateVex(Graph G , VerTexType v){for(int i 0; i G.vexnum; i){if(G.vexs[i] v){return i;}}return -1;
}//采用邻接矩阵表示法创建无向G
void CreateUDN(Graph G){int i , j , k;cout 请输入总顶点数总边数;cin G.vexnum G.arcnum; cout endl;cout 输入点的名称 endl;for(i 0; i G.vexnum; i){ cout 请输入第 (i1) 个点的名称:;cin G.vexs[i];}cout endl;//初始化邻接矩阵边的权值均置为极大值MaxIntfor(i 0; i G.vexnum; i) for(j 0; j G.vexnum; j) G.arcs[i][j] 0; cout 输入边依附的顶点 endl;for(k 0; k G.arcnum;k){ VerTexType v1 , v2;cout 请输入第 (k 1) 条边依附的顶点:;cin v1 v2; i LocateVex(G, v1); j LocateVex(G, v2);//确定v1和v2在G中的位置即顶点数组的下标 G.arcs[i][j] 1;//边v1, v2的权值置为w G.arcs[j][i] G.arcs[i][j];//置v1, v2的对称边v2, v1的权值为w }
}//返回v的第一个邻接点
int FirstAdjVex(Graph G , int v){int i;for(i 0 ; i G.vexnum ; i){if(G.arcs[v][i] 1 visited[i] false){return i;}}return -1;
}//返回v相对于w的下一个邻接点
int NextAdjVex(Graph G , int u , int w){int i;for(i w ; i G.vexnum ; i){if(G.arcs[u][i] 1 visited[i] false){return i;}}return -1;
}//按广度优先非递归遍历连通图G
void BFS (Graph G, int v){ sqQueue Q;ArcType u;ArcType w;cout G.vexs[v] -; visited[v] true; InitQueue(Q);//辅助队列Q EnQueue(Q, v);//v进队 while(!QueueEmpty(Q)){DeQueue(Q, u);for(w FirstAdjVex(G, u); w 0; w NextAdjVex(G, u, w)){//依次检查u的所有邻接点w FirstAdjVex(G, u)表示u的第一个邻接点 //NextAdjVex(G, u, w)表示u相对于w的下一个邻接点w≥0表示存在邻接点 if(!visited[w]){//w为u的尚未访问的邻接顶点cout G.vexs[w]-; visited[w] true;EnQueue(Q, w);//w进队 }}}
}int main(){Graph G;CreateUDN(G);cout endl;cout 无向连通图G创建完成 endl endl;cout 请输入遍历连通图的起始点;VerTexType c;cin c;int i;for(i 0 ; i G.vexnum ; i){if(c G.vexs[i]){break;}}cout endl;while(i G.vexnum){cout 该点不存在请重新输入 endl;cout 请输入遍历连通图的起始点;cin c;for(i 0 ; i G.vexnum ; i){if(c G.vexs[i]){break;}}}cout 广度优先搜索遍历连通图结果 endl;BFS(G , i);return 0;
}实验十一 图2
一、实验目的与要求
3掌握最小生成树的概念和算法
4掌握最短路径的算法的实现
5掌握拓扑排序的应用。
二、实验内容
1.输出所有可能的路径
有n个结点的有向无环图选取合适的存储方式并找到所有从0到n-1的路径并输出不要求按顺序。二维数组的第i个数组中的单元都表示有向图中i号结点所能到达的结点注有向图是有方向的即规定了a→b你就不能从b→a空就是没有下一个结点了。
示例1 输入graph [[1,2],[3],[3],[]]
输出[[0,1,3],[0,2,3]]
解释有两条路径 0 - 1 - 3 和 0 - 2 - 3
示例2 输入graph [[4,3,1],[3,2,4],[3],[4],[]]
输出[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]] 2.建造物流配送中心问题
给定4个城市之间的交通图如下图所示图中弧上数字表示城市之间的道路长度。要在4个城市之间选择一个城市建造一个物流配送中心并使得到物流配送中心最远的城市到物流配送中心的路程最短。 要求
1设计存储结构表示城市及城市之间的关系
2求出物流配送中心最远城市到物流配送中心的最短路程
3分析算法的时间复杂度。
三、实验结果
1请将调试通过的主要源代码、运行结果截图粘贴在下面并说明测试用例、运行过程。必要的注释、Times New Roman 5号行间距1.5倍
2简述算法步骤选画技术路线图格式如下
S1:
S2:
3请分析算法的时间复杂度。
4请将源代码必要的注释cpp文件一起压缩上传上传附件。 题目1
1.1源代码
#include iostream
#include cstdio
#include vector
using namespace std;//DFS回溯算法——遍历graph[p]寻找下一个元素并进行回溯。
void DFS(vectorvectorint graph,vectorint path,vectorvectorint res,int p){int i;//在graph[p]中找下一个元素for(i0;igraph[p].size();i){//找到最后一个元素将path加入resif(graph[p][i]graph.size()-1){path.push_back(graph.size()-1);res.push_back(path);path.pop_back();continue;}path.push_back(graph[p][i]); //不是最后一个元素继续回溯DFS(graph,path,res,graph[p][i]); //递归调用 path.pop_back();}
}//寻找所有到达路径
vectorvectorint allPathsSourceTarget(vectorvectorint graph) {vectorvectorint res; //res存储一条路径的所有结点 vectorint path{0};DFS(graph,path,res,0); //调用DFS函数 return res;
}//主函数
int main() {int n;cout请输入结点个数;cinn;vectorvectorint store(n);coutendl请依次输入每个结点的出度以及可达结点的编号endlendl;for(int i0;in;i){int m;cout编号为i的结点的出度;cinm;coutendl该结点可达结点的编号;vectorint each(m);for(int j0;jm;j){cineach[j];}coutendl;store[i]each;}vectorvectorint resallPathsSourceTarget(store);coutendl所有的可能路径如下endl;coutendl;for(int k0;kres.size();k){for(int l0;lres[k].size();l){if(l0){coutres[k][l];}else{cout-res[k][l];}}coutendl;}return 0;
}1.2测试用例
测试用例1 如图1所示的4点4边的有向图。寻找0点到3点的所有可能路径。
测试用例2 如图2所示的5点8边的有向图。寻找0点到4点的所有可能路径。
图1
图2
1.3运行结果
测试用例1 测试用例2 1.4运行过程
输入总结点数 - 输入各结点的出度 - 输入当前结点可达的结点 - 调用寻找所有到达路径的函数 - DFS回溯遍历 - 输出所有可能的路径。
2算法步骤
S1DFS回溯函数。该函数不仅包含了递归的过程而且包含了回退的过程。对于一个无向连通图访问图中某个顶点v0后然后访问它的某一个邻接顶点v1然后再从v1出发访问v1的未访问过的邻接顶点。如此下去直至到达所有的领接顶点都被访问过。然后回退一步回到前一次被访问的顶点看是否还有没有访问的顶点。如果有没有访问的顶点那么从这个顶点出发进行向上述的过程一样进行访问如果无没有访问的顶点那么再回退一步进行类似的访问直至所有的顶点都被访问为止。后续该函数将在寻找所有到达路径函数中被调用。 S2寻找所有到达路径函数。利用vectorint向量容器同时调用DFS回溯函数将得到的路径结点顺序存储到res数组中最后返回res数组的结果。后续该函数将在主函数中被调用。 S3主函数。依次输入结点数、每个结点的出度和当前结点指向的结点并用数组储存起来。建立起有向图的结构并明确各个结点之间的连通性。 3算法时间复杂度分析
在遍历有向图时对于图中每个结点DFS函数至多调用一次。一旦某个结点被标志为已访问就不再从当前结点开始进行搜索。对图的遍历实质上是对每个结点查找其邻接点的过程。DFS回溯函数中使用的是二维数组和向量容器进行存储。因此查找每个顶点的邻接点所需时间为O(n2)。
因此本算法的时间复杂度为O(n2)。 题目2
1.1源代码
#include iostream
#include vector
#define inf 99999
using namespace std;//邻接矩阵
int graph[4][4]{{0,8,inf,inf},{10,0,5,inf},{4,inf,0,4},{inf,7,3,0},
}; int path[4][4]{ {0,1,2,3},{0,1,2,3},{0,1,2,3},{0,1,2,3},
}; //最短路径算法
void solve(int graph[4][4],int path[4][4]){int i,j,k;for(k0;k4;k) {for(i0;i4;i) {for(j0;j4;j) {if(graph[i][k]graph[k][j] graph[i][j]) {graph[i][j] graph[i][k]graph[k][j]; //更新最短路径 path[i][j] path[i][k];}}}}
}//输出邻接矩阵
void Output(int graph[4][4]){int i,j;for(i0;i4;i){cout[;for(j0;j4;j){if(graph[i][j]99999){coutinf;}else{cout.width(4);coutgraph[i][j];}if(j!3){cout,;}}cout]\n;}
}//排序最远距离
void Sort(int graph[4][4]){int i,j,maxlen[4];//i行j列 for(j0;j4;j){int maxno0;for(i0;i4;i){if(graph[maxno][j]graph[i][j]){maxnoi;}}maxlen[j]maxno; }cout到当前结点最远的距离依次为;for(int k0;k4;k){coutgraph[maxlen[k]][k] ;//第k列的最大数 }coutendl;cout其中最小的距离为;int mingraph[maxlen[0]][0],minno0;for(i1;i4;i){if(mingraph[maxlen[i]][i]){mingraph[maxlen[i]][i];minnoi;}}coutminendl;cout所以物流配送中心应该建设的地方为;switch(minno){case 0:coutaendl;break;case 1:coutbendl;break;case 2:coutcendl;break;case 3:coutdendl;break;}
}//主函数
int main() {cout初始邻接矩阵:endl; Output(graph);solve(graph,path);coutendl最终邻接矩阵:endl; Output(graph);coutendl;Sort(graph);return 0;
}1.2测试用例
测试用例为如下图所示的4点7边的有向图。
预设置的邻接矩阵为
{0,8,inf,inf}
{10,0,5,inf}
{4,inf,0,4}
{inf,7,3,0} 1.3运行结果 1.4运行过程
预先设置初始邻接矩阵 - 输出初始邻接矩阵 - 将每一个结点进行最小路径函数调用 - 输出最小路径条件下的邻接矩阵 - 排序离当前结点的最远距离 - 寻找最远距离中的最小值和最小值对应的结点并输出。
2算法步骤
S0初始化。预先设置邻接矩阵graph和存储路径的二维数组path。 S1最短路径算法函数。利用三层for循环遍历图的所有路径同时根据判断条件得到当前的最短路径并更新最短路径从而使graph中的数据得以更新。 S2输出邻接矩阵函数。按照矩阵的形式输出结果最短路径算法更新后的邻接矩阵。 S3排序最远距离函数。首先通过两层for循环寻找所有结点到当前结点的最远距离并通过maxlen数组存储。之后通过一层for循环寻找maxlen数组中的最小值并记录最小值对应的结点序号。最后统一输出每一个结点的最远物流距离最小的最远物流距离及其对应结点。 S4主函数。在主函数中依次调用输出邻接矩阵函数最初的状态、最短路径算法函数、输出邻接矩阵函数给每个结点均进行了戴克斯特拉算法的状态、排序最远距离函数即可得到物流中心的建设结果和计算分析过程。 3算法时间复杂度分析
在最短路径算法函数中使用了三层for循环来更新最短路径对于邻接矩阵的每一行而言耗费的时间为O(n3)。
在排序最远距离函数中使用了两层for循环来寻找每个结点的最远物流距离耗费的时间为O(n2)并使用了一层for循环来寻找最远物流距离中的最小值耗费的时间为O(n)。
因此本算法的时间复杂度为O(n3)。
