数据结构 — 图 之 广度优先遍历
发布日期:2021-06-30 19:49:30
浏览次数:2
分类:技术文章
本文共 2341 字,大约阅读时间需要 7 分钟。
【描述】: 图的bfs
【输入】:
8 1 2 -1 0 3 4 -1 0 5 6 -1 1 7 -1 1 7 -1 2 7 -1 2 7 -1 3 4 5 6 -1
【输出】:
0 1 2 3 4 5 6 7
/* *图的广度优先遍历 *1.链式队列(链表的头节点中存数据、节点的尾插法、头节点的删除) *2.bfs 8 1 2 -1 0 3 4 -1 0 5 6 -1 1 7 -1 1 7 -1 2 7 -1 2 7 -1 3 4 5 6 -1 */#include【运行结果】:#include using namespace std;/* 宏定义 */#define MAX_NUM 50#define ElementType int/* 定义动态链式队列节点 */typedef struct QueueNode{ ElementType data; struct QueueNode *next;}QueueNode,*QueuePointer;/* 邻接表表节点 */typedef struct TableNode{ ElementType vertex; struct TableNode *next;}TableNode,*TablePointer;/* 头节点数组 */TablePointer graph[MAX_NUM];/* 定义visited数组 */bool visited[MAX_NUM];/* 顶点数 */int vertices;/* * 动态链式队列 * 1.addq -> 入队 * 2.deleteq -> 出队 *//*在链式队列的队尾插入元素*/void addq(QueuePointer &front, QueuePointer &rear, ElementType item){ QueuePointer temp = new QueueNode; temp->data = item; temp->next = NULL; //插入 if(front){ rear->next = temp; }else{ front = temp; } rear = temp;}/*从链式队列的头部出队*/ElementType deleteq(QueuePointer &front){ QueuePointer temp = front; ElementType item; //出队 item = temp->data; front = temp->next; delete temp; return item;}/* * 邻接表存储的图 * 1.创建图 * 2.bfs *//*创建*/void CreateGraph(){ ElementType ch; TablePointer pnew,qnode; pnew = qnode = NULL; for(int i = 0; i < vertices; i++){ cin>>ch; if(ch == -1) continue; /*当ch 为-1是结束该vertex的创建*/ //链表的头节点 pnew = new TableNode; pnew->vertex = ch; pnew->next = NULL; //将头节点存入 头节点数组 graph[i] = pnew; //尾插法创建链表 cin>>ch; while(ch != -1){ //申请内存、处理数据域、处理指针域 qnode = new TableNode; qnode->vertex = ch; qnode->next =NULL; //插入 pnew->next = qnode; //更新尾指针 pnew = qnode; cin>>ch; } } }/*bfs*/void bfs(ElementType v){ TablePointer w; QueuePointer front, rear; front = rear = NULL; //将第一个节点输入、标记、进队 cout< < next){ if(!visited[w->vertex]){ cout< vertex<<" "; visited[w->vertex] = true; addq(front, rear, w->vertex); } } } cout< >vertices; CreateGraph(); cout<<"广度优先遍历"<
转载地址:https://lipenglin.blog.csdn.net/article/details/49963697 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月29日 22时27分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
tf rnn输入输出的维度和权重的维度
2019-04-30
检验是否服从同一分布
2019-04-30
tf callbacks
2019-04-30
keras、tf、numpy实现logloss对比
2019-04-30
Ubuntu20.04安装微信
2019-04-30
Restful风格的使用
2019-04-30
Swagger基础入门整合SpringBoot
2019-04-30
MyBatisPlus简单入门(SpringBoot)
2019-04-30
攻防世界web进阶区NewsCenter详解
2019-04-30
攻防世界web进阶PHP2详解
2019-04-30
如何解决词达人问题(新)
2019-04-30
攻防世界web进阶区surpersqli详解
2019-04-30
攻防世界web进阶区easytornado详解
2019-04-30
攻防世界web进阶区web2详解
2019-04-30
xss-labs详解(上)1-10
2019-04-30
xss-labs详解(下)11-20
2019-04-30
攻防世界web进阶区ics-05详解
2019-04-30
攻防世界web进阶区FlatScience详解
2019-04-30
攻防世界web进阶区ics-04详解
2019-04-30
攻防世界web进阶区Cat详解
2019-04-30