数据结构实验报告（三）——图的操作和实现

article/2025/10/4 16:56:59

实验目的

1．掌握图的基本概念、性质与应用问题

2．掌握图的邻接矩阵与邻接表存储方式;

3．掌握图的有关算法，如创建、遍历、连通分量、生成树/最小生成树算法（如Prim、Kruskal算法）等;

实验原理

1.建立与存储

邻接矩阵：采用二维数组来存储顶点之间的相邻关系，若两个顶点之间有直连边，则在数组对应位置赋予相应的权值(自身到自身的权值设置为0)，若两个顶点之间没有直连边,则赋予32267，即int型的最大值，意为无穷大；在输入各边的权值时，写了一个找到顶点对应位置的函数，返回顶点对应的下标，这样输入时就能把权值赋予对应的位置。定义一个结构体,结构体属性包括邻接矩阵、存储顶点信息的数组、边数、顶点数。输出用二重循环即可。

2.遍历

深度优先遍历:

用寻找顶点下标的函数返回‘0’的下标，然后开始遍历。采用递归的方式，在邻接矩阵中，找到第一个邻接边，然后又从另一顶点开始，依次递归下去（访问过的顶点用visited[]数组记录），直到所有顶点均已被遍历。

广度优先遍历:

访问起点的所有邻接点，然后从近到远（即下标从小到大）再访问邻接点的所有邻接点，直到遍历完成。

3最小生成树

普里姆算法：

假设有两个集合，一个U，一个V-U，初始时，U里只有起点u1，V-U则为其余顶点，在V-U中寻找权值最小的（u1，vi），然后把vi加入到U，该边对应也加入到最小生成树中，依次类推最终可以得到n个顶点n-1条边的最小生成树。

4.最短路径算法

狄克斯特拉算法：

设有两个集合，一个U，一个V-U；一维数组dist[]用于存储起点到各顶点的最短路径长度；一维数组path[]用于存储最短路径。初始时，U里只有起点u1，V-U则为其余顶点，dist[]数组置为起点的邻接信息。从V-U中寻找较小的顶点（即从dist的值较小的顶点），将它添加到U中，考查该顶点的邻接信息，若该顶点与其他顶点之间有边，则与原定最短路径长度进行比较，新路径插入了中间点，（如新路径0-1-2与原路径0-2比较）更新最短路径长度（如dist[i]）为较小者。重复上述步骤，直到U中包含所有顶点。

实验源码

定义

#define MaxInt 32767        //表示极大值，即∞ 
#define MVNum 100            //最大顶点个数 
typedef char VerTextType;    //顶点的数据类型 
typedef int ArcType;        //边的数据类型

定位元素

//定位邻接表元素 
int locateVexALG(ALGraph G,VerTextType v){for(int i=1;i<=G.vexnum;i++){if(v==G.vertices[i].data) return i;}
}

创建图——邻接矩阵法

//邻接矩阵 
typedef struct{VerTextType vexs[MVNum];    //存顶点的数组 ArcType arcs[MVNum][MVNum];    //邻接矩阵 int vexnum,arcnum;        //顶点、边的数量 
}AMGraph;
typedef struct ArcNode{int adjvex;                //该边指向的顶点的位置 struct ArcNode *nextarc;//指向下一条边 
}ArcNode;//创建无向图(邻接矩阵法） 
void createAMUDN(AMGraph &G){cout<<"请输入顶点个数：";cin>>G.vexnum;cout<<"请输入边的个数：";cin>>G.arcnum;cout<<"请输入顶点名称：";for(int i=1;i<=G.vexnum;i++){cin>>G.vexs[i];}for(int i=1;i<=G.vexnum;i++){for(int j=1;j<=G.vexnum;j++){G.arcs[i][j]=MaxInt;}}cout<<"请输入顶点与边权："<<endl;for(int k=1;k<=G.arcnum;k++){VerTextType v1,v2;ArcType w;cin>>v1>>v2>>w;int i=locateVexAMG(G,v1);int j=locateVexAMG(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j];//创建有向图就注释掉 } 
}//打印 邻接矩阵法创建的图 
void printAMUDN(AMGraph G){for (int i=1;i<=G.vexnum;i++){for (int j=1;j<=G.vexnum;j++)cout<<G.arcs[i][j]<<"\t";cout<<endl;}
}

创建图——邻接表法

//邻接表首元结点 
typedef struct VNode{VerTextType data;ArcNode *firstarc;
}VNode,AdjList[MVNum]; 
//邻接表
typedef struct
{AdjList vertices;    //存首元 int vexnum,arcnum;    
}ALGraph;//创建无向图(邻接表法）
void createALUDG(ALGraph &G){cout<<"请输入顶点个数："; cin>>G.vexnum;cout<<"请输入边的个数：";cin>>G.arcnum;cout<<"请输入顶点名称：";for (int i=1;i<=G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}cout<<"请输入边连接的顶点："<<endl; for (int k=1;k<=G.arcnum;k++){VerTextType v1,v2;cin>>v1>>v2;int i=locateVexALG(G,v1);int j=locateVexALG(G,v2);ArcNode *p1,*p2;p1=new ArcNode;p1->adjvex=j;p1->nextarc=G.vertices[i].firstarc; //头插 G.vertices[i].firstarc=p1;p2=new ArcNode;p2->adjvex=i;p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;}
} //打印 邻接表法创建的图
void printALUDG(ALGraph G){for (int i=1;i<=G.vexnum;i++){ArcNode *p=G.vertices[i].firstarc;cout<<G.vertices[i].data<<"\t";while (p){cout<<p->adjvex<<"\t";p=p->nextarc;}cout<<endl;}
}

DFS遍历——邻接矩阵法和邻接表法

bool visited[MVNum];        //用于DFS 
//DFS遍历（邻接矩阵法）
void Dfs_AM(AMGraph G,int v){cout<<v<<" ";visited[v]=true;for(int i=1;i<=G.vexnum;i++){//一条路走到黑 if((G.arcs[v][i]!=MaxInt)&&(visited[i]==false)){Dfs_AM(G,i);}}
}//DFS遍历（邻接表法）
void Dfs_AL(ALGraph G,int v){cout<<v<<" ";visited[v]=true;ArcNode *p;p=G.vertices[v].firstarc;while(p!=NULL){int i=p->adjvex;if(!visited[i]) Dfs_AL(G,i);p=p->nextarc;}
}

计算连通分量

int color[MVNum];            //用于计算连通分量 
int c;                    //连通分量个数
//计算连通分量
void Dfs_countConnect(AMGraph G,int i){color[i]=c;for(int k=1;k<=G.vexnum;k++){if(color[k]==-1 && G.arcs[i][k]!=MaxInt) Dfs_countConnect(G,k);}
}
void countConnect(AMGraph G){for(int i=0;i<=G.vexnum;i++){color[i]=-1;} for(int i=1;i<=G.vexnum;i++){if(color[i]==-1){Dfs_countConnect(G,i);c++;}}cout<<"连通分量为："<<c<<endl;
}

最小生成树算法——prim

//最小生成树算法(Prim) 
void MiniSpanTree_Prim(AMGraph G,VerTextType u){int k=locateVexAMG(G,u);for (int j=1;j<=G.vexnum;j++){if (j!=k) closeedge[j]={u,G.arcs[k][j]};}closeedge[k].lowcost=0;int wpl=0;for (int i=2;i<=G.vexnum;i++){int min=MaxInt;for (int j=1;j<=G.vexnum;j++){if (closeedge[j].lowcost!=0&&closeedge[j].lowcost<min){min=closeedge[j].lowcost;k=j;}}wpl+=closeedge[k].lowcost;closeedge[k].lowcost=0;for (int j=1;j<=G.vexnum;j++){if (G.arcs[k][j]<closeedge[j].lowcost)closeedge[j]={G.vexs[k],G.arcs[k][j]};}}cout<<"最小生成树总权值为："<<wpl<<endl;
}

最短路径——迪杰斯特拉

//最短路径(迪杰斯特拉)void ShortestPath_DIJ(AMGraph G,int v0){int n=G.vexnum;int ans=0;int S[MVNum],D[MVNum],Path[MVNum];for (int v=1;v<=n;v++){S[v]=false;D[v]=G.arcs[v0][v];if (D[v]<MaxInt)Path[v]=v0;elsePath[v]=-1;}S[v0]=true;D[v0]=0;int v,w;for (int i=2;i<=n;i++){int min=MaxInt;for (w=1;w<=n;w++){if (!S[w]&&D[w]<min){v=w;min=D[w];}}S[v]=true;for (w=1;w<=n;w++){if (!S[w]&&(D[v]+G.arcs[v][w]<D[w])){D[w]=D[v]+G.arcs[v][w];Path[w]=v;}}}for (int i=1;i<=n;i++)cout<<G.vexs[v0]<<"---->"<<G.vexs[i]<<"的最短路径为:"<<D[i]<<endl;
}

main

int main(){while(true){system("cls");AMGraph G1;ALGraph G2;cout<<"1.建立无向图（邻接矩阵）"<<endl;cout<<"2.建立无向图（邻接表）"<<endl;cout<<"3.DFS遍历（邻接矩阵）"<<endl;cout<<"4.DFS遍历（邻接表）"<<endl;cout<<"5.计算连通分量"<<endl; cout<<"6.最小生成树——普利姆算法"<<endl;cout<<"7.最短路径——迪杰斯特拉算法"<<endl;cout<<"0.退出"<<endl;cout<<"请选择服务：";int ch;cin>>ch;switch(ch){case 1:createAMUDN(G1);cout<<"邻接矩阵："<<endl;printAMUDN(G1);break;case 2:createALUDG(G2);cout<<"邻接表："<<endl;printALUDG(G2);break;case 3:memset(visited,false,sizeof(visited));int v1;cout<<"请输入起始点编号：";cin>>v1;cout<<"深度优先遍历的结果为：";Dfs_AM(G1,v1);  //v1为遍历起始点编号 cout<<endl;break;case 4:memset(visited,false,sizeof(visited));int v2;cout<<"请输入起始点编号：";cin>>v2;cout<<"深度优先遍历的结果为：";Dfs_AL(G2,v2);  //v1为遍历起始点编号 cout<<endl;break;case 5:countConnect(G1);break;case 6:int v3;cout<<"请输入起始点编号：";cin>>v3;MiniSpanTree_Prim(G1,v3);//1表示起始点 break;case 7:int v4;cout<<"请输入起始点编号：";cin>>v4;ShortestPath_DIJ(G1,v4);//1表示起点break;case 0:exit(0);break; } cout<<endl;system("pause");}    return 0;
}

实验结果

创建无向图

邻接矩阵法

邻接表法

其他功能篇幅有限就不展示了

实验心得

  1. 一开始想把的MaxInt当成0（为了方便看），后面写普利姆算法计算最小生成树中，在判断最小边时产生bug，最后还是统一赋予一个整型最大值32267。

2.深度遍历中要用到visited这一数组判断各个顶点是否被访问visited=true/false，然后根据临界边递归调用访问下一顶点，直到所有顶点被访问过一次。

3.计算连通分量时，设置color数组，用于森林中的子树“上色”，当同一子树中所有节点被遍历完，计数+1.

创作时在听《龙卷风》


http://chatgpt.dhexx.cn/article/pyWU8eJo.shtml

相关文章

关于实验室数据结构实验错误本周总结。引用调用bug

关于实验室数据结构实验错误本周总结。引用调用bug

因为学校的实验室本学期没人维护出现了很多bug&#xff0c;但是也有自己的原因。 下面是引用调用的错误。 #include<stdio.h> #include<stdlib.h>typedef struct {int *top;int *base;int sqsize;} Sq;void Init(Sq t){t.top(int*)malloc(sizeof(4*100));t.baset…
阅读更多...
数据结构 实验4——拓扑排序

数据结构 实验4——拓扑排序

一、实验名称&#xff1a;拓扑排序 二、实验学时&#xff1a;6学时 三、实验目的 1.理解拓扑排序的特性和算法&#xff1b; 2.通过构造图的邻接表&#xff0c;掌握拓扑排序算法。 四、实验内容(步骤) 1.建立邻接表存储的图&#xff1b; 2.对图进行拓扑排序&#xff1b; …
阅读更多...
【C语言】数据结构实验报告--单链表

【C语言】数据结构实验报告--单链表

实验内容 一.将单链表按基准划分&#xff0c;以单链表的首节点值x为基准将该单链表分割为两部分&#xff0c;使所有小于x的结点排在大于或等于x的结点之前。 #include<stdio.h> #include"linklist.cpp"void Split(LinkNode *&L) {LinkNode *pre,*p;if(L-&g…
阅读更多...
数据结构实验报告（四）——查找和排序算法

数据结构实验报告（四）——查找和排序算法

实验目的 1. 掌握顺序查找技术和拆半查找技术以及部分排序算法的设计思想&#xff1b; 2. 掌握查找、部分排序算法的实现与执行过程。 实验原理 查找算法 1.顺序查找&#xff1a;从数组第一个元素开始逐个比较&#xff0c;找到后返回相应下标。 2.折半查找&#xff1a;从数组中…
阅读更多...
数据结构实验--个人图书信息管理系统

数据结构实验--个人图书信息管理系统

数据结构实验 第一章 个人图书信息管理系统 第二章 停车场管理 第三章 哈夫曼编码 第一章 个人图书信息管理系统 数据结构实验前言一、需求分析二、概要设计三、详细设计1.全局变量、元素类型、结点类型和指针类型2.顺序表的基本操作3.主函数 总结 前言 线性表的顺序表示又称为…
阅读更多...
【C语言】数据结构实验报告一

【C语言】数据结构实验报告一

目录 题目1.1 求1~n的连续整数和。1.2 对于1到n的每个整数n&#xff0c;输出log2n&#xff0c;根号n&#xff0c;n ,nlog2n ,n^2 ,n^3 ,2^n ,n!的值。1.3 求1~n的素数的个数&#xff0c;并且计算出时间1.4 求1~n的连续整数阶乘的和。 题目 1.1 求1~n的连续整数和。 #include&…
阅读更多...
数据结构实验：电话号码查询系统

数据结构实验：电话号码查询系统

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、问题描述二、问题描述&#xff08;1&#xff09;选用的散列函数&#xff08;2&#xff09;散列因子&#xff08;3&#xff09;解决冲突的方法 三、实验结果…
阅读更多...
数据结构实验报告五 查找

数据结构实验报告五 查找

一、实验目的 1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。 3、学会哈希函数的构造方法&#xff0c;处理冲突的机制以及哈希表的查找。 二、实验内容和要求 1.静态查找表技术 依据顺序查找算法和折半查找算法的…
阅读更多...
数据结构实验公交车系统

数据结构实验公交车系统

数据结构实验公交车系统&#xff08;完整代码私信&#xff09; 1.查询公交车信息 2.查询站点信息 3.查询两个站点之间的路线&#xff08;最多一次换乘&#xff09; 4.添加、删除、修改公交车&#xff0c;站点&#xff0c;路线 创建4个文本文档&#xff08;即txt&#xff09; r…
阅读更多...
数据结构实验报告六 排序

数据结构实验报告六 排序

一、实验目的 1、掌握内部排序的基本算法&#xff1b; 2、分析比较内部排序算法的效率。 二、实验内容和要求 1.运行下面程序&#xff1a; #include <stdlib.h> #include <stdio.h> #define MAX 50 int slist[MAX]; /*待排序序列*/void insertSort(int list[],…
阅读更多...
数据结构实验——哈夫曼编码

数据结构实验——哈夫曼编码

目录 问题描述 基本要求 问题分析 实验代码 运行结果 实验总结 问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率&#xff0c;缩短信息传输时间&#xff0c;降低传输成本。但是&#xff0c;这要求在发送端通过一个编码系统对待传数据预先编码&#xff0c;在接收端…
阅读更多...
数据结构实验C语言实现版

数据结构实验C语言实现版

目录 数据结构实验——顺序表的基本操作 数据结构实验——单链表的基本操作 数据结构实验——顺序栈的建立及基本操作实现 数据结构实验——链队列的建立及基本操作实现 数据结构实验——赫夫曼树构造及赫夫曼编码的实现 数据结构实验——迪杰斯特拉算法求最短路径 数据结…
阅读更多...
数据结构实验报告

数据结构实验报告

数据结构与算法实验一&#xff08;顺序表的操作&#xff09; 一、实验目的 1&#xff0e;掌握线性表的顺序存储结构的表示和实现方法。 2&#xff0e;掌握顺序表基本操作的算法实现。 3&#xff0e;了解顺序表的应用。 二、实验内容 1&#xff0e;建立顺序表。 2&#xff0…
阅读更多...
【数据结构】实验项目：顺序表，也就那么回事

【数据结构】实验项目：顺序表，也就那么回事

目录 序 嗨&#xff0c;这里是狐狸~~ 简介 顺序表的结构定义&#xff1a; 声明顺序表类型变量&#xff1a; 实验内容&#xff1a; 实验说明 : 实验思路 1、 输入一组整型元素序列&#xff08;不少于10个&#xff09;&#xff0c;建立顺序表。 2&#xff0e; 在该顺…
阅读更多...
数据结构（实验一）

数据结构（实验一）

第一次写报告&#xff0c;虽然有点简单&#xff0c;但还是要勉励自己再接再厉。加油 继续努力。 1.实验目的&#xff08;结出本次实验所涉及并要求掌握的知识点&#xff09; 1.掌握顺序表的存储结构形式及描述方法和基本运算的实现&#xff1b; 2.掌握用顺序表设计合理的数据…
阅读更多...
数据结构实验

数据结构实验

1.有序数组的插入 代码&#xff1a; bool Insert( List L, ElementType X ){//溢出if(L->LastMAXSIZE-1) return false;//插入在最后一位if(L->Data[L->Last] > X){L->Data[L->Last1]X;L->Last;return true;}int tp0;int find0;int tmp0;for(int i0;i &l…
阅读更多...
网络传输大文件使用什么软件可以高速传输？

网络传输大文件使用什么软件可以高速传输？

网络传输大文件使用什么软件可以高速传输&#xff1f;通过网络传输文件总是在速度上得不到很好的体现&#xff0c;更不用说是传输大文件了。本身支持大文件网络传输的工具就是不是很多&#xff0c;很多的传输工具对文件的大小都有所限制&#xff0c;要是想要找到一个高速传输大…
阅读更多...
.mmap文件用什么软件可以打开？

.mmap文件用什么软件可以打开？

1.下载MindManager专属打开它的软件 2。
阅读更多...
什么是Saas软件？

什么是Saas软件？

人们常常会提及Saas&#xff08;萨斯&#xff09;软件&#xff0c;那么什么是Saas软件呢&#xff1f;首先大家通过百度可以看到百度百科的解释 相信大多数的伙伴们看了之后的感想就是一脸蒙圈&#xff0c;如果让自己给别人介绍什么是Saas软件还是记不住解释不清楚&#xff0c;那…
阅读更多...
测试移动信号频率的软件,手机信号工作频段侦测软件

测试移动信号频率的软件,手机信号工作频段侦测软件

手机信号来源于基站发射的信号。但是常常会遇见的手机信号差&#xff0c;信号弱&#xff0c;上网速度慢等&#xff0c;都有可能是源于信号弱带来的。那么我们看见的手机上显示的信号弱&#xff0c;到底是什么信号弱&#xff1f;如何判别&#xff1f; 这里推荐一款APP软件&#…
阅读更多...
推荐文章

Copyright @ 2022~2023