成长路上的小程序之——图的邻接表DFS、BFS

2024-06-14 03:58
文章标签 程序 bfs dfs 成长 邻接 路上

本文主要是介绍成长路上的小程序之——图的邻接表DFS、BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第八次数据结构上机内容：使用图的邻接表存储结构完成图的DFS、BFS遍历

本来提前就用邻接矩阵写完了，但昨晚一个贱人突然告诉我老师要求用邻接表写。。。于是加班加点，终于在今早搞出来了！

上机课的时候因为没带书，所以完全是自己敲的，期间被一个无限循环困住了！！！

在邻接链表插入新节点过程中，为p申请新空间，插入后就释放空间

在刘文斌大神的帮助下，我理解了开辟、释放空间这个概念。

我在创建图的过程中，更改了p的指向，并且最后释放p时，p为空指针，所以没有错误。

释放空间时，要确保能够找到之前创建的所有空间并释放！！！！

应该在使用完成后释放空间！！

以后再申请新空间时，无论如何也要放在最后释放空间，这样不容易出错。

代码中还有一个问题就是在FirstAdjVex()和NextAdjVex()函数中，没有释放空间，因为试过只要释放空间就无法使DFS函数结束。

解决方法是在创建空间的时候，另设一个标志指针指向该位置，使用完成后释放标志指针所指空间即可

再次感谢刘文斌大神

得意

代码如下：


#define MAX 20typedef char VertexType;typedef struct ArcNode{int adjvex;int w;struct ArcNode *nextarc;
}ArcNode;typedef struct VNode{VertexType data;ArcNode *firstarc;
}VNode,AdjList[MAX];typedef struct{AdjList vertices;   int vexnum;int arcnum;int kind;
}ALGraph;int Locate(ALGraph G,char x)
{for(int i=0; i<G.vexnum; i++)if(G.vertices[i].data==x) return i;return -1; 
} Status CreateDG(ALGraph &G)//创建有向图 
{char v1,v2; int  j; ArcNode *p;printf("\nplease enter the vexnum and arcnum:\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar();printf("\nplease enter the vexs in order:\n");for(int i=0; i<G.vexnum; i++){scanf("%c",&G.vertices[i].data);G.vertices[i].firstarc=NULL;} printf("\nplease enter edge:\n");for(int i=0; i<G.arcnum; i++){getchar(); scanf("%c %c",&v1,&v2); j=Locate(G,v1); //定位v1位置  p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=Locate(G,v2);p->w=0;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;//不可以在这里释放空指针！！！} printf("\nHere are the ALGraph:\n"); for(int i=0; i<G.vexnum; i++){printf("%c",G.vertices[i].data);p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[i].firstarc;while(p)     {printf(" -> %d",p->adjvex);p=p->nextarc;    }printf("\n\n");} return OK;
}Status CreateDN(ALGraph &G)//创建有向网 
{char v1,v2; int  j,w; ArcNode *p;printf("\nplease enter the vexnum and arcnum:\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar();printf("\nplease enter the vexs in order:\n");for(int i=0; i<G.vexnum; i++){scanf("%c",&G.vertices[i].data);G.vertices[i].firstarc=NULL;} printf("\nplease enter edge:\n");for(int i=0; i<G.arcnum; i++){getchar(); scanf("%c %c %d",&v1,&v2,&w); j=Locate(G,v1); //定位v1位置  p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=Locate(G,v2);p->w=w;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;//不可以在这里释放空指针！！！ }printf("\nHere are the ALGraph:\n"); for(int i=0; i<G.vexnum; i++){printf("%c",G.vertices[i].data);p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[i].firstarc;while(p)     {printf("->[ %d weight:%d ]",p->adjvex,p->w);p=p->nextarc;    }printf("\n\n");}return OK;
}Status CreateUDG(ALGraph &G)//创建无向图 
{char v1,v2; int  j,k; ArcNode *p,*q,*flag;printf("\nplease enter the vexnum and arcnum:\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar();printf("\nplease enter the vexs in order:\n");for(int i=0; i<G.vexnum; i++){scanf("%c",&G.vertices[i].data);G.vertices[i].firstarc=NULL;} printf("\nplease enter edge:\n");for(int i=0; i<G.arcnum; i++){getchar(); scanf("%c %c",&v1,&v2); j=Locate(G,v1); //定位v1位置  k=Locate(G,v2);p=(ArcNode *)malloc(sizeof(ArcNode)); q=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=k;p->w=0;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;q->adjvex=j;q->w=0;q->nextarc=G.vertices[k].firstarc;G.vertices[k].firstarc=q;//不可以在这里释放空指针！！！} printf("\nHere are the ALGraph:\n"); for(int i=0; i<G.vexnum; i++){printf("%c",G.vertices[i].data);p=G.vertices[i].firstarc;while(p)     {printf(" -> %d",p->adjvex);p=p->nextarc;    }printf("\n\n");}return OK;
}Status CreateUDN(ALGraph &G)//创建无向网 
{char v1,v2; int  j,w,k; ArcNode *p,*q;printf("\nplease enter the vexnum and arcnum:\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar();printf("\nplease enter the vexs in order:\n");for(int i=0; i<G.vexnum; i++){scanf("%c",&G.vertices[i].data);G.vertices[i].firstarc=NULL;} printf("\nplease enter edge:\n");for(int i=0; i<G.arcnum; i++){getchar(); scanf("%c %c %d",&v1,&v2,&w); j=Locate(G,v1); //定位v1位置  k=Locate(G,v2);p=(ArcNode *)malloc(sizeof(ArcNode)); q=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=k;p->w=w;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;//不可以在这里释放空指针！！！ q->adjvex=j;q->w=w;q->nextarc=G.vertices[k].firstarc;G.vertices[k].firstarc=q;}printf("\nHere are the ALGraph:\n"); for(int i=0; i<G.vexnum; i++){printf("%c",G.vertices[i].data);p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[i].firstarc;while(p)     {printf("->[ %d weight:%d ]",p->adjvex,p->w);p=p->nextarc;    }printf("\n\n");}return OK;
}void CreateMenu(ALGraph &G)
{printf("please enter the Graph's kind:\n");printf("\n0 present DG(有向图)\n");printf("\n1 present DN(有向网)\n");printf("\n2 present UDG(无向图)\n");printf("\n3 present UDN(无向网)\n");char ch=getchar();switch(ch){case '0':CreateDG(G);break;    case '1':CreateDN(G);break;    case '2':CreateUDG(G);break;    case '3':CreateUDN(G);break;    }return ;
} ArcNode *p;
bool visited[MAX];int FirstAdjVex(ALGraph G, int v)
{p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[v].firstarc;if(p)return p->adjvex;else return -1;
}int NextAdjVex(ALGraph G, int v, int w)
{p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[v].firstarc;for(int i=0; i<MAX; i++){if(p->adjvex==w){ if(p->nextarc){ return p->nextarc->adjvex;} else return -1;}elsep=p->nextarc;}
}void DFS(ALGraph G, int v)
{visited[v]=true;printf("%c   ",G.vertices[v].data);for(int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w)){if(!visited[w])DFS(G,w);}return ;
}void DFSTraverse(ALGraph G)
{printf("\n\n\nHere are the results of DFSTraverse:\n\n");int v;for(v=0; v<G.vexnum; v++)visited[v]=false;for(v=0; v<G.vexnum; v++)if(!visited[v])DFS(G,v);printf("\n");return ;
}//----------队列 void BFSTraverse(ALGraph G)
{int que[MAX]={-1}; int u;int rear=0,front=0;printf("\n\n\nHere are the results of BFSTraverse:\n\n");for(int v=0; v<G.vexnum; v++)visited[v]=false;for(int v=0; v<G.vexnum; v++)if(!visited[v]){visited[v]=true;printf("%c   ",G.vertices[v].data);que[++rear]=v;while(rear!=front){u=que[++front];for(int w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=true;printf("%c   ",G.vertices[w].data);que[++rear]=w;   }      } }printf("\n");
}void menu(ALGraph G)
{printf("\n\npleae choice the traverse:");printf("\n\n1.DFS\n\n2.BFS\n\n");getchar();char ch=getchar();if(ch=='1')return DFSTraverse(G);else if(ch=='2')return BFSTraverse(G);
}



main函数：

#include <cstdlib>
#include <iostream>
#include "constant.h"
#include "graph.h"using namespace std;int main(int argc, char *argv[])
{ArcNode *p,*flag; ALGraph G;CreateMenu(G);menu(G);for(int i=0; i<G.vexnum; i++){p=G.vertices[i].firstarc;while(p)     {flag=p->nextarc;free(p);p=flag;}}system("PAUSE");return EXIT_SUCCESS;
}


这篇关于成长路上的小程序之——图的邻接表DFS、BFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1059306。

相关文章

如何用java对接微信小程序下单后的发货接口

如何用java对接微信小程序下单后的发货接口

《如何用java对接微信小程序下单后的发货接口》：本文主要介绍在微信小程序后台实现发货通知的步骤,包括获取Access_token、使用RestTemplate调用发货接口、处理AccessTok... 目录配置参数 调用代码获取Access_token调用发货的接口类注意点总结配置参数 首先需要获取Ac
阅读更多...
基于Python开发PDF转Doc格式小程序

基于Python开发PDF转Doc格式小程序

《基于Python开发PDF转Doc格式小程序》这篇文章主要为大家详细介绍了如何基于Python开发PDF转Doc格式小程序,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 用python实现PDF转Doc格式小程序以下是一个使用Python实现PDF转DOC格式的GUI程序，采用T
阅读更多...
将java程序打包成可执行文件的实现方式

将java程序打包成可执行文件的实现方式

《将java程序打包成可执行文件的实现方式》本文介绍了将Java程序打包成可执行文件的三种方法：手动打包（将编译后的代码及JRE运行环境一起打包）,使用第三方打包工具（如Launch4j）和JDK自带... 目录1.问题提出2.如何将Java程序打包成可执行文件2.1将编译后的代码及jre运行环境一起打包2
阅读更多...
在不同系统间迁移Python程序的方法与教程

在不同系统间迁移Python程序的方法与教程

《在不同系统间迁移Python程序的方法与教程》本文介绍了几种将Windows上编写的Python程序迁移到Linux服务器上的方法,包括使用虚拟环境和依赖冻结、容器化技术（如Docker）、使用An... 目录使用虚拟环境和依赖冻结1. 创建虚拟环境2. 冻结依赖使用容器化技术（如 docker）1. 创
阅读更多...
windos server2022里的DFS配置的实现

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS？优势：应用场景：DFS配置步骤什么是DFS？DFS指的是分布式文件系统（Distr
阅读更多...
hdu1254（嵌套bfs，两次bfs）

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
hdu 2489 (dfs枚举 + prim)

hdu 2489 (dfs枚举 + prim)

题意： 对于一棵顶点和边都有权值的树，使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值，找到一个该图含有m 个顶点的子图，并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析： 因为数据量不大，先用dfs枚举搭配出m个子节点，算出点和，然后套个prim算出边和，每次比较大小即可。 dfs没有写好，A的老泪纵横。 错在把index在d
阅读更多...
poj 3050 dfs + set的妙用

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵，求由多少个由连续6个元素组成的不一样的字符的个数。 解析： dfs + set去重搞定。 代码： #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm
阅读更多...
poj 2195 bfs+有流量限制的最小费用流

poj 2195 bfs+有流量限制的最小费用流

题意： 给一张n * m（100 * 100）的图，图中” . " 代表空地， “ M ” 代表人， “ H ” 代表家。 现在，要你安排每个人从他所在的地方移动到家里，每移动一格的消耗是1，求最小的消耗。 人可以移动到家的那一格但是不进去。 解析： 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了，先抽象出源点s和汇点t。 令源点与每个人相连，容量为1，费用为
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2