成长路上的小程序之——图的邻接表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。

相关文章

使用Python创建一个功能完整的Windows风格计算器程序

使用Python创建一个功能完整的Windows风格计算器程序

《使用Python创建一个功能完整的Windows风格计算器程序》：本文主要介绍如何使用Python和Tkinter创建一个功能完整的Windows风格计算器程序,包括基本运算、高级科学计算（如三... 目录python实现Windows系统计算器程序（含高级功能）1. 使用Tkinter实现基础计算器2.
阅读更多...
将Java程序打包成EXE文件的实现方式

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》：本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4
阅读更多...
Java程序进程起来了但是不打印日志的原因分析

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》：本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序
阅读更多...
SpringBoot实现微信小程序支付功能

SpringBoot实现微信小程序支付功能

《SpringBoot实现微信小程序支付功能》小程序支付功能已成为众多应用的核心需求之一,本文主要介绍了SpringBoot实现微信小程序支付功能,文中通过示例代码介绍的非常详细,对大家的学习或者工作... 目录一、引言二、准备工作（一）微信支付商户平台配置（二）Spring Boot项目搭建（三）配置文件
阅读更多...
如何用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（人的移动）；代码如下：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2