C语言数据结构之图的遍历实例详解-创新互联
C语言数据结构之图的遍历实例详解
创新互联-专业网站定制、快速模板网站建设、高性价比梅江网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式梅江网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖梅江地区。费用合理售后完善,10年实体公司更值得信赖。输入一组顶点,建立无向图的邻接矩阵。输入一组顶点,建立有向图的邻接表。分别对无向图和有向图进行DFS(深度优先遍历)和BFS(广度优先遍历)。写出深度优先遍历的递归和非递归算法。根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列。
实现代码:
#include#include #define MAX 20 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct{ char data; ArcNode *firstarc; }AdjList[MAX]; typedef struct{ AdjList vertices; int vexnum; int arcnum; }ALGraph; typedef struct{ int *base; int front,rear; }CqQueue; void InitQueue(CqQueue &Q) {//初始化一个队列 Q.base=(int*)malloc(MAX*sizeof(int)); Q.front=Q.rear=0; } int QueueEmpty(CqQueue Q) {//判断队列是否为空 if(Q.rear==Q.front) return 1; return 0; } void EnQueue(CqQueue &Q,int e) {//入队操作 if((Q.rear+1)%MAX==Q.front) return; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAX; } void DeQueue(CqQueue &Q,int &e) {//出队操作 if(Q.rear==Q.front) return; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAX; } int LocateVex(ALGraph G,char v) {//查找顶点v在图G中的位置 for(int i=0;i adjvex=j; s->nextarc=NULL; if(!G.vertices[i].firstarc) G.vertices[i].firstarc=s; else{ p=G.vertices[i].firstarc; while(p->nextarc) p=p->nextarc; p->nextarc=s; } s=(ArcNode*)malloc(sizeof(ArcNode)); s->adjvex=i; s->nextarc=NULL; if(!G.vertices[j].firstarc) G.vertices[j].firstarc=s; else{ p=G.vertices[j].firstarc; while(p->nextarc) p=p->nextarc; p->nextarc=s; } } } int visited[MAX]; void DFS(ALGraph G,int v) {//从顶点v开始对图G进行深度优先搜索 ArcNode *p; printf("%3c",G.vertices[v].data); visited[v]=1; for(p=G.vertices[v].firstarc;p;p=p->nextarc) if(!visited[p->adjvex]) DFS(G,p->adjvex); } void DFSTraverse(ALGraph G) {//对用邻接表存储的无向图G进行深度优先遍历 int v; for(v=0;v nextarc) if(!visited[p->adjvex]){ printf("%3c",G.vertices[p->adjvex].data); visited[p->adjvex]=1; EnQueue(Q,p->adjvex); } } } } int main(){ ALGraph G; printf("建立无向图的邻接表:\n"); CreateAdjList(G); printf("无向图的深度优先遍历序列如下:\n"); DFSTraverse(G); printf("\n\n无向图的广度优先遍历序列如下:\n"); BFSTraverse(G); printf("\n"); return 0; }
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
当前题目:C语言数据结构之图的遍历实例详解-创新互联
网站网址:http://myzitong.com/article/cosdhj.html