数据结构

2024-07-11 17:47:58| 来源: 网络整理| 查看: 265

数据结构——图的基本操作实现

图的基本操作不算很多，但是从记忆的角度来看算法比较的长，相对而言比较的困难。图的操作以遍历为主，其应用为最小生成树、最短路径、拓扑排序和关键路径求解。其中，最小生成树和最短路径的求法及过程需要大家掌握，而关键路径和拓扑排序只需要掌握过程，算法不要求掌握。这里为了更好的帮助大家理解以及掌握相应的算法，图的每一个操作本人都进行了实现。如果其中有什么不对的地方，还请各位大神指出！

一、图的类型定义。 1.邻接矩阵存储 typedef struct { VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum; }AMGraph;

这个存储方式是图的常用存储方式，后面的应用中主要以邻接矩阵的形式呈现。

2.邻接表存储 typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; // OtherInfo info; }ArcNode; typedef struct VNode { VerTexType data; ArcNode *firstarc; }VNode,AdjList[MVNum]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph;

相较于邻接矩阵，邻接表的形式比较的复杂，在后面的关键路径中采用这种方式实现。

此外，书上还介绍了十字链表和邻接多重表进行存储，由于在后面的应用中涉及不到，在这里就不进行展示了，有兴趣的话大家可以自己看看。

二、图的建立 1.邻接矩阵建立无向图（有向图） Status CreateUDN(AMGraph &G) { coutG.vexnum; coutG.arcnum; cout VerTexType 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]; //这一句话在建立有向图时注释掉 } return OK; } 2.邻接表建立无向图 Status CreateUDG(ALGraph &G) { coutG.vexnum; coutG.arcnum; cout VerTexType 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; } return OK; }

关于图的建立这部分，一个比较重要的函数是LocateVex这个函数，具体的实现过程在最后的完整代码中实现。

三、图的遍历 1.DFS——深度优先搜索

深度优先算法是图的一个很重要的算法，不管是利用邻接表还是邻接矩阵，都要牢牢掌握其算法要领，这里完成二者在连通图的条件下的代码实现：

bool visited[MVNum]; void DFS_AM(AMGraph G,int v) { cout cout VerTexType adjvex; ArcType lowcost; }closeedge[MVNum]; void MiniSpanTree_Prim(AMGraph G,VerTexType u) { int k=LocateVexAMG(G,u); for (int j=0;ju,G.arcs[k][j]}; } closeedge[k].lowcost=0; int wpl=0; for (int i=1;i if (closeedge[j].lowcost!=0&&closeedge[j].lowcost if (G.arcs[k][j] VerTexType Head; VerTexType Tail; ArcType lowcost; }Edge[1000]; int Vexset[MVNum]; bool cmp(node a,node b) { return a.lowcost for (int j=0;j Edge[k].Head=G.vexs[i]; Edge[k].Tail=G.vexs[j]; Edge[k].lowcost=G.arcs[i][j]; k++; } } } sort(Edge,Edge+k,cmp); for (int i=0;i cout int n=G.vexnum; int ans=0; int S[MVNum],D[MVNum],Path[MVNum]; for (int v=0;v int min=MaxInt; for (w=0;w v=w; min=D[w]; } } S[v]=true; for (w=0;w D[w]=D[v]+G.arcs[v][w]; Path[w]=v; } } } for (int i=0;i for (int j=0;j for (int i=0;i if (D[i][k]+D[k][j] for (int j=0;j" VertexType data;//顶点的数据域 ArcNode * firstarc;//指向邻接点的指针 }VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组 typedef struct { AdjList vertices;//图中顶点及各邻接点数组 int vexnum,arcnum;//记录图中顶点数和边或弧数 }ALGraph; //找到顶点对应在邻接表数组中的位置下标 int LocateVex(ALGraph G,VertexType u){ for (int i=0; i return i; } } return -1; } //创建AOE网，构建邻接表 void CreateAOE(ALGraph **G){ *G=(ALGraph*)malloc(sizeof(ALGraph)); scanf("%d%d",&((*G)->vexnum),&((*G)->arcnum)); for (int i=0; ivexnum; i++) { scanf("%d",&((*G)->vertices[i].data)); (*G)->vertices[i].firstarc=NULL; } VertexType initial,end,dut; for (int i=0; iarcnum; i++) { scanf("%d%d%d",&initial,&end,&dut); ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=LocateVex(*(*G), end); p->nextarc=NULL; p->dut=dut; int locate=LocateVex(*(*G), initial); p->nextarc=(*G)->vertices[locate].firstarc; (*G)->vertices[locate].firstarc=p; } } //结构体定义栈结构 typedef struct stack{ VertexType data; struct stack * next; }stack; stack *T; //初始化栈结构 void initStack(stack* *S){ (*S)=(stack*)malloc(sizeof(stack)); (*S)->next=NULL; } //判断栈是否为空 bool StackEmpty(stack S){ if (S.next==NULL) { return true; } return false; } //进栈，以头插法将新结点插入到链表中 void push(stack *S,VertexType u){ stack *p=(stack*)malloc(sizeof(stack)); p->data=u; p->next=NULL; p->next=S->next; S->next=p; } //弹栈函数，删除链表首元结点的同时，释放该空间，并将该结点中的数据域通过地址传值给变量i; void pop(stack *S,VertexType *i){ stack *p=S->next; *i=p->data; S->next=S->next->next; free(p); } //统计各顶点的入度 void FindInDegree(ALGraph G,int indegree[]){ //初始化数组，默认初始值全部为0 for (int i=0; i ArcNode *p=G.vertices[i].firstarc; while (p) { indegree[p->adjvex]++; p=p->nextarc; } } } bool TopologicalOrder(ALGraph G){ int indegree[G.vexnum];//创建记录各顶点入度的数组 FindInDegree(G,indegree);//统计各顶点的入度 //建立栈结构，程序中使用的是链表 stack *S; //初始化栈 initStack(&S); for (int i=0; i if (!indegree[i]) { push(S, i); } } int count=0; //栈为空为结束标志 while (!StackEmpty(*S)) { int index; //弹栈，并记录栈中保存的顶点所在邻接表数组中的位置 pop(S,&index); //压栈，为求各边的最晚开始时间做准备 push(T, index); ++count; //依次查找跟该顶点相链接的顶点，如果初始入度为1，当删除前一个顶点后，该顶点入度为0 for (ArcNode *p=G.vertices[index].firstarc; p ; p=p->nextarc) { VertexType k=p->adjvex; if (!(--indegree[k])) { //顶点入度为0，入栈 push(S, k); } //如果边的源点的最长路径长度加上边的权值比汇点的最长路径长度还长，就覆盖ve数组中对应位置的值，最终结束时，ve数组中存储的就是各顶点的最长路径长度。 if (ve[index]+p->dut>ve[k]) { ve[k]=ve[index]+p->dut; } } } //如果count值小于顶点数量，表明有向图有环 if (count if (!TopologicalOrder(G)) { return ; } for (int i=0 ; i pop(T, &j); for (ArcNode* p=G.vertices[j].firstarc ; p ; p=p->nextarc) { k=p->adjvex; //构建Vl数组，在初始化时，Vl数组中每个单元都是18，如果每个边的汇点-边的权值比源点值小，就保存更小的。 if (vl[k]-p->dut for (ArcNode*p = G.vertices[j].firstarc; p ;p = p->nextarc) { k = p->adjvex; //求各边的最早开始时间e[i],等于ve数组中相应源点存储的值 int ee = ve[j]; //求各边的最晚开始时间l[i]，等于汇点在vl数组中存储的值减改边的权值 int el = vl[k]-p->dut; //判断e[i]和l[i]是否相等，如果相等，该边就是关键活动，相应的用*标记；反之，边后边没标记 char tag = (ee==el)?'*':' '; printf("%3d%3d%3d%3d%3d%2c\n",j,k,p->dut,ee,el,tag); } } } int main(){ ALGraph *G; CreateAOE(&G);//创建AOE网 initStack(&T); TopologicalOrder(*G); CriticalPath(*G); return 0; } 五、完整代码的实现 #include #define Status int #define OK 1 #define MaxInt 32767 #define MVNum 100 using namespace std; typedef char VerTexType; typedef int ArcType; typedef struct { VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum; }AMGraph; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; // OtherInfo info; }ArcNode; typedef struct VNode { VerTexType data; ArcNode *firstarc; }VNode,AdjList[MVNum]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; void Menu() { cout for (int i=0;i coutG.vexnum; coutG.arcnum; cout VerTexType 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]; } return OK; } void PrintUDN(AMGraph G) { for (int i=0;i coutG.vexnum; coutG.arcnum; cout VerTexType 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; } return OK; } void PrintUDG(ALGraph G) { for (int i=0;i cout if ((G.arcs[v][w]!=0)&&(!visited[w])) DFS_AM(G,w); } } void DFS_AL(ALGraph G,int v) { cout VerTexType adjvex; ArcType lowcost; }closeedge[MVNum]; void MiniSpanTree_Prim(AMGraph G,VerTexType u) { int k=LocateVexAMG(G,u); for (int j=0;ju,G.arcs[k][j]}; } closeedge[k].lowcost=0; int wpl=0; for (int i=1;i if (closeedge[j].lowcost!=0&&closeedge[j].lowcost if (G.arcs[k][j] VerTexType Head; VerTexType Tail; ArcType lowcost; }Edge[1000]; int Vexset[MVNum]; bool cmp(node a,node b) { return a.lowcost for (int j=0;j Edge[k].Head=G.vexs[i]; Edge[k].Tail=G.vexs[j]; Edge[k].lowcost=G.arcs[i][j]; k++; } } } sort(Edge,Edge+k,cmp); for (int i=0;i cout int n=G.vexnum; int ans=0; int S[MVNum],D[MVNum],Path[MVNum]; for (int v=0;v int min=MaxInt; for (w=0;w v=w; min=D[w]; } } S[v]=true; for (w=0;w D[w]=D[v]+G.arcs[v][w]; Path[w]=v; } } } for (int i=0;i for (int j=0;j for (int i=0;i if (D[i][k]+D[k][j] for (int j=0;j" system("cls"); AMGraph G1; ALGraph G2; Menu(); int x; cin>>x; switch(x) { case 1: if (CreateUDN(G1)==1) { cout

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

数据结构

数据结构

今日新闻

点击排行

推荐新闻

图片新闻

专题文章