数据结构 — 图之邻接表存储创建和深度优先遍历
发布日期:2021-06-30 19:49:29
浏览次数:3
分类:技术文章
本文共 1461 字,大约阅读时间需要 4 分钟。
【描述】: 该graph采用邻接表存储,首先创建图,然后对其进行深度优先遍历。
【输入】:
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 3 7 4 5 2 6
/* * 无向图的邻接表创建81 2 -10 3 4 -10 5 6 -11 7 -11 7 -12 7 -12 7 -13 4 5 6 -1*/#include#include using namespace std;#define MAX_VERTICES 50 /* 顶点最大数 */#define ElementType int /* 元素的数据类型 */bool visited[MAX_VERTICES]; /* 记录顶点是否被访问 */typedef struct node { /* 表节点结构体 */ ElementType vertex; struct node *next;}NodeType,*NodePointer;NodePointer graph[MAX_VERTICES]; /* 头节点数组 */int vertices; /* 顶点数量 */void CreateGraph(){ ElementType ch; NodePointer pnew,qnode; pnew = qnode = NULL; for(int i = 0; i < vertices; i++){ cin>>ch; if(ch == -1) continue; /*当ch 为-1是结束该vertex的创建*/ //链表的头节点 pnew = new NodeType; pnew->vertex = ch; pnew->next = NULL; //将头节点存入 头节点数组 graph[i] = pnew; //尾插法创建链表 cin>>ch; while(ch != -1){ //申请内存、处理数据域、处理指针域 qnode = new NodeType; qnode->vertex = ch; qnode->next =NULL; //插入 pnew->next = qnode; //更新尾指针 pnew = qnode; cin>>ch; } }}void dfs(int v){ NodePointer np; //访问该vertex visited[v] = true; cout< <<" "; /* * 图深度优先遍历 * 1、访问该节点并且记录 * 2、当该节点的next节点没被visited,dfs(next节点) * 3、当该节点的next节点都被visited,结束for,退到上一个visited的节点执行2步骤 * 4、都被访问了,函数自然结束 */ for(np = graph[v]; np!=NULL; np = np->next){ if(!visited[np->vertex]) dfs(np->vertex); }}int main(){ memset(visited,false,sizeof(visited)); cout<<"输入顶点数"< >vertices; CreateGraph(); cout<<"深度优先遍历"<
转载地址:https://lipenglin.blog.csdn.net/article/details/49947351 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月27日 07时06分48秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【工具使用】使用pip与conda安装、更新与卸载Pytorch和torchvision
2019-04-30
【工具使用】Google免费云环境Colaboratory使用
2019-04-30
【深度学习笔记】卷积层,全连接层,池化层的相关输出参数计算
2019-04-30
【NLP学习笔记】文本分类概述
2019-04-30
【深度学习笔记】文本分类
2019-04-30
【转载】炼丹实验室:深度学习网络调参技巧
2019-04-30
【论文阅读笔记】文本分类论文汇总
2019-04-30
【NLP学习笔记】One-hot encoding:独热编码
2019-04-30
【工具使用】CSDN编辑器markdown字体、颜色与字号的设置
2019-04-30
【NLP学习笔记】词共现矩阵
2019-04-30
【NLP学习笔记】NLP基础知识框架图
2019-04-30
【工具和环境】Linux下安装pycharm
2019-04-30
【工具与环境】Windows下安装Sublime Text 3
2019-04-30
【工具与环境】Excel中批量插入行
2019-04-30
【学习笔记】对vanilla的一些个人理解
2019-04-30