图的广度遍历

图的广度遍历 1 引言 1.1 背景 图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继。图作为一种非线性数据结构，被广泛的应用于多个技术领域，例如系统工程、化学工程、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些领域中把图结构作为解决问题的数学手段之一。可以采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历采用广度优先遍历进行搜索。 图的遍历算法是求解图的连通性问题，拓扑问题和求关键路径等算法的基础。然而，图的遍历要比树的遍历复杂得多。因为图的任何一顶点都有可能和其余的顶点相邻接。所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该点。为了避免统一顶点被访问多次，在图的遍历过程中，必须先记下每个已访问的顶点。介绍一种对有向图和无向图都适用的遍历图的路径即为广度优先搜索。图的广度优先遍历类似于树的前序遍历，采用的遍历方法的特点是尽可能先对纵深方向进行搜索。而在遍历的过程中，可以采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储，对图的遍历采用广度优先遍历进行序列搜索。 1.2 目标 首先输入图的类型，有向或无向图（因为遍历与权值无关）。然后输入图的顶点数、边数和各条边，之后生成该图的邻接表并输出。再输入要遍历该图的起点，然后从所输入的点广度搜索该图的邻接表，并按遍历顺序输出顶点内容。之后决定是否继续遍历该图或输入另一个需要遍历的图。 2 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 论证 2.1 系统需求 图的遍历算法是求解图的连通性问题，拓扑问题和求关键路径等算法的基础。然而，图的遍历要比树的遍历复杂得多。因为图的任何一顶点都有可能和其余的顶点相邻接。所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该点。为了避免统一顶点被访问多次，在图的遍历过程中，必须先记下每个已访问的顶点。介绍一种对有向图和无向图都适用的遍历图的路径即为广度优先搜索。 图的广度优先遍历类似于树的前序遍历，采用的遍历方法的特点是尽可能先对纵深方向进行搜索。而在遍历的过程中，可以采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储，对图的遍历采用广度优先遍历进行序列搜索。 2.2 功能需求 图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继。图作为一种非线性数据结构，被广泛的应用于多个技术领域，例如系统工程、化学工程、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些领域中把图结构作为解决问题的数学手段之一。 对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。画出搜索顺序示意图。 2.3 运行环境的要求 Visual C++ 6.0和Windows XP电脑一台。 Visual C++6.0不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment,IDE）。Visual C++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。 3 算法实现 3.1 算法思想 （1）邻接表 邻接表是图的一种链式存储结构。在邻接表中，对图中每个定点建立一个单链表，第i个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。 （3）图的广度遍历 （a）从图中某个顶点 出发，首先访问 。 （b）依次访问的各个未被访问的临接点。 （c）分别从这些临接点出发，依次访问他们的各个未被访问的临接点。访问时应保证：如果 和 为当前端接点，且 在 之间被访问，则 所有未被访问的临接点应在 所有未被访问的临接点之前访问，重复<3>,直到所有端结点均没有未被访问的临接点为止。 （d）若此时还有还有顶点未被访问，则选一个未被访问的顶点作为起点，重复以上过程，直至所有顶点均被访问为止。 3.2 模块划分 基于邻接表实现图的广度遍历： (a)Status InitQueue(LinkQueue *Q)根据已知Q初始化队列 (b)Status QueueEmpty (LinkQueue Q)判断队列是否为空 (c)Status EnQueue(LinkQueue *Q, QElemType e)将e压入队尾 (d)Status DeQueue(LinkQueue *Q, QElemType *e)取队头元素e (e)void createALGraph(ALGraph *G)建立无向图的邻接表 (f)void PrintGraph(MGraph G)输出邻接表的无向图 (g) int FirstAdjVex(MGraph G,int v)第一个邻接点的定位 (h)int NextAdjVex(MGraph G,int v,int w)查找下一个邻接点 (i)void BFS(ALGraph G, int v)实现图的一次广度遍历 (g)void BfsTraverse(MGraph G)实现图的广度遍历 (k)Void Main主函数 4 广度搜索顺序示意图 图4-1 广度搜索顺序示意图 5 运行结果 图5-1 基于邻接表实现图的广度优先搜索运行结果 6 设计体会及今后的改进意见 图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继。图的遍历算法是求解图的连通性问题，拓扑问题和求关键路径等算法的基础。然而，图的遍历要比树的遍历复杂得多。 其次，图中任意顶点均有可能与其它顶点相邻，在沿着某一路径依次搜索访问顶点时完全有可能又回到该顶点上；此外，图中某一顶点可能与多个顶点相邻，当访问过该结点后，如何选择下一个要访问的顶点，就成为一个决策问题。图的遍历算法通常有两条遍历路径：深度优先遍历和广度优先遍历。在此我对广度优先遍历的主要内容进行了深入的研究。 邻接表是图的一种链式存储结构。在邻接表中，对图中每个定点建立一个单链表，第i个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点域（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。 图的广度遍历则是从图中某个顶点 出发，首先访问 。依次访问的各个未被访问的临接点。分别从这些临接点出发，依次访问他们的各个未被访问的临接点。访问时应保证：如果 和 为当前端接点，且 在 之间被访问，则 所有未被访问的临接点应在 所有未被访问的临接点之前访问，重复<3>,直到所有端结点均没有未被访问的临接点为止。若此时还有还有顶点未被访问，则选一个未被访问的顶点作为起点，重复以上过程，直至所有顶点均被访问为止。 通过这次课程设计，我对用邻接表实现图的广度优先搜索有了更深层次的理解，对于解决生活中的许多问题都是有帮助的，然而在刚开始的时候，事情并没有想象中的那么顺利，本来以为数据结构刚刚学过图的遍历，做起来会很顺利，但是最后把程序都编写好了的时候才发现运行不出来，无论怎么检查都检查不出错误歘在那里。在这个时候，我有了一种放弃的念头，但又想想，那么多的程序自己一个字一个字的打上去，不能就这样放弃，于是我又找同学帮忙，最后在同学的帮助下，终于检查出了错误出在哪里，进过改正之后，终于运行出了正确的结果。心里也憋得高兴。 在以后的生活中，遇到困难的时候不能轻易地说放弃，如果是自己个人解决不了的，需要去求助别人，毕竟人多力量大，也许在大家的帮助下，就可以顺利的解决问题了。更重要的是不要急躁，在事情不顺的时候需要淡定，调整好情绪在找解决的办法。 参 考 文 献 [1]严蔚敏.数据结构C语言.清华大学出版社.2010. [2]谭浩强.c语言程序设计.清华大学出版社.2009. [3]张铭.数据结构与算法.北京:高等教育出版社，2008． [4]朱战立.数据结构.西安：西安电子科技大学出版社，2003. 附 录 //用邻接表实现无向图的深度优先搜索遍历和广度优先搜索遍历 #include const int n=8;              //表示图中的最大顶点数 const int e=15;                  //图中的最大边数 typedef int elemtype; bool visited[n+1];          //标志数组用于记载某个顶点是否被访问过 class link                  //定义链表类型 { public: elemtype data; link *next; }; class GRAPH              //定义邻接表的表头类型 { public: link a[n+1]; void creatlink()            //建立图的邻接表 { int i,j,k; link *s; for(i=1;i<=n;i++)          //建立邻接表的表头类型 { a[i].data=i; a[i].next=NULL; } for(k=1;k<=e;k++) { cout<<"请输入一条边"; cin>>i>>j;                //输入一条边(i,j) cout<