博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
用邻接表实现DFS和BFS
阅读量:6270 次
发布时间:2019-06-22

本文共 5162 字,大约阅读时间需要 17 分钟。

#include 
#include
#define MAXVERTEX 10typedef char VertexType; //顶点类型typedef int EdgeType; //边的类型typedef int ElemType; //队列中元素类型typedef struct EdgeNode{ int adjvex; EdgeType weight; struct EdgeNode *next;}EdgeNode; //在邻接表中存放邻接顶点下标值的结点typedef struct VertexNode{ int Flag; int vertex; VertexType data; EdgeNode *firstedge;}VertexNode,AdjList[MAXVERTEX]; //定义一个MAXVERTEX个顶点的邻接表typedef struct GraphAdjList{ AdjList adjList; int numVertex; int numEdge;}GraphAdjList; //定义一个图typedef struct QNode{ ElemType qData; struct QNode *nextNode;}QNode; //定义队列的结点typedef struct QueueList{ QNode *front; QNode *rear;}QueueList,*queue; //定义一个队列 //初始化队列void InitQueue(QueueList *Q){ Q->front = (QNode*)malloc(sizeof(QNode)); if( Q->front == NULL ) { printf("Error!"); exit(0); } Q->rear = Q->front;// Q->rear = NULL; Q->front->nextNode = NULL;} //插入一个结点到队列void InsertQueue(QueueList *Q,ElemType *e){ QNode *p; p = (QNode *)malloc(sizeof(QNode)); p->qData = *e; p->nextNode = NULL; Q->rear->nextNode = p; Q->rear = p;} //删除队列中的结点(出队列)void DeleteQueue(QueueList *Q,ElemType *e){ QNode *s; if(Q->front == Q->rear) { return; } s = Q->front->nextNode; *e = s->qData; Q->front->nextNode = s->nextNode; if(Q->front->nextNode == NULL) { Q->rear = Q->front; } free(s); return;}void CreateGraph(GraphAdjList *G) //构建一个我们要遍历的图{ int i = 0,j = 0,k = 0; EdgeNode *s; VertexType c; printf("请输入图的顶点数和边数,中间用英文逗号隔开 :\n"); scanf("%d,%d",&G->numVertex,&G->numEdge); printf("请输入各个顶点中存放的数据:\n"); fflush(stdin); scanf("%c",&c); while(i < G->numVertex) { if(c == '\n') { break; } G->adjList[i].data = c; G->adjList[i].Flag = 0; G->adjList[i].vertex = i; G->adjList[i].firstedge = NULL; i++; scanf("%c",&c); } fflush(stdin); for(k = 0;k < G->numEdge;k++) { printf("请输入边Vi~Vj依附的顶点下标 i 和 j :\n"); scanf("%d,%d",&i,&j); s = (EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex = j; s->next = G->adjList[i].firstedge; G->adjList[i].firstedge = s; s = (EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex = i; s->next = G->adjList[j].firstedge; G->adjList[j].firstedge = s; }} //查看邻接表是否构建的正确,这个函数只是为了验证void print(GraphAdjList *G){ int i = 0; EdgeNode *p; for(i = 0;i < G->numVertex;i++) { printf("\n %d->",i); p = G->adjList[i].firstedge; while(p) { printf("%d->",p->adjvex); p = p->next; } printf("End\n"); }} //DFS遍历void DFSTraverse(GraphAdjList *G,int i){ int j = 0; EdgeNode *p; G->adjList[i].Flag = 1; printf("%c->",G->adjList[i].data); p = G->adjList[i].firstedge; while(p != NULL) { if(G->adjList[p->adjvex].Flag == 0) { DFSTraverse(G,p->adjvex); } p = p->next; }} //判断队列是否为空int QueueEmpty(QueueList *Q){ if(Q->front == Q->rear) return 0; else return 1;} //BFS遍历void BFSTraverse(GraphAdjList *G){ int i = 0,k = 0,flag = 0; EdgeNode *s; QueueList Q; InitQueue(&Q); for(i = 0;i < G->numVertex;i++) { G->adjList[i].Flag = 0; } for(i = 0;i < G->numVertex;i++) { if(G->adjList[i].Flag == 0) { G->adjList[i].Flag = 1;// printf("%c ",G->adjList[i].data); InsertQueue(&Q,&i); while(QueueEmpty(&Q)) { DeleteQueue(&Q,&i); printf("%c->",G->adjList[i].data); s = G->adjList[i].firstedge; while(s != NULL) { k = s->adjvex; if(G->adjList[k].Flag == 0) { G->adjList[k].Flag = 1;// printf("%c ",G->adjList[k].data); InsertQueue(&Q,&(s->adjvex)); } s = s->next; } } } } printf("End\n");}int main(){ int k = 0; //深度优先遍历从第1个顶点(按输入顺序)开始 GraphAdjList *G; CreateGraph(G); printf("\n顶点的邻接表为:\n"); print(G); //按照头插法得到的邻接表 printf("\nDFS的结果是:\n"); DFSTraverse(G,k); //深度优先遍历 printf("End\n"); printf("\nBFS的结果是:\n"); BFSTraverse(G); //广度优先遍历 return;}

  

posted on
2014-12-21 21:07 阅读(
...) 评论(
...)

转载于:https://www.cnblogs.com/devinblog/p/4177045.html

你可能感兴趣的文章
CF 375D. Tree and Queries【莫队 | dsu on tree】
查看>>
Maven最佳实践 划分模块 配置多模块项目 pom modules
查看>>
Hadoop学习笔记——WordCount
查看>>
Unity应用架构设计(4)——设计可复用的SubView和SubViewModel(Part 1)
查看>>
Java-Spring-获取Request,Response对象
查看>>
opencv项目报错_pFirstBlock==pHead解决办法
查看>>
MySQL日志
查看>>
Oracle性能优化之Oracle里的执行计划
查看>>
电脑如何连接远程服务器?听语音
查看>>
使用Xcode 查看objective-C的汇编代码
查看>>
Vue.js——60分钟快速入门
查看>>
设计模式 - 模板方法模式(template method pattern) 具体解释
查看>>
mysql判断一个字符串是否包含某子串 【转】
查看>>
a bad dream
查看>>
FD_CLOEXEC用法及原因_转
查看>>
element UI 的学习一,路由跳转
查看>>
RabbitMQ三种Exchange模式(fanout,direct,topic)的性能比较
查看>>
Spring JavaBean属性值的注入方式( 属性注入, 特殊字符注入 <![CDATA[ 带有特殊字符的值 ]]> , 构造器注入 )...
查看>>
【Linux】Linux下统计当前文件夹下的文件个数、目录个数
查看>>
Hibernate_14_数据连接池的使用
查看>>