图的广度遍历.doc

图的广度遍历 1 引言 背景图是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系,每个元素只有一个直接前驱和一个直接后继。图作为一种非线性数据结构,被广泛的应用于多个技术领域,例如系统工程、化学工程、统计力学、遗传学、控制论、人工智能、编译系统等领域,在这些领域中把图结构作为解决问题的数学手段之一。可以采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历采用广度优先遍历进行搜索。图的遍历算法是求解图的连通性问题,拓扑问题和求关键路径等算法的基础。然而, 图的遍历要比树的遍历复杂得多。因为图的任何一顶点都有可能和其余的顶点相邻接。所以在访问了某个顶点之后,可能沿着某条路径搜索之后,又回到该点。为了避免统一顶点被访问多次,在图的遍历过程中,必须先记下每个已访问的顶点。介绍一种对有向图和无向图都适用的遍历图的路径即为广度优先搜索。图的广度优先遍历类似于树的前序遍历, 采用的遍历方法的特点是尽可能先对纵深方向进行搜索。而在遍历的过程中,可以采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储,对图的遍历采用广度优先遍历进行序列搜索。 目标首先输入图的类型,有向或无向图(因为遍历与权值无关)。然后输入图的顶点数、边数和各条边,之后生成该图的邻接表并输出。再输入要遍历该图的起点,然后从所输入的点广度搜索该图的邻接表,并按遍历顺序输出顶点内容。之后决定是否继续遍历该图或输入另一个需要遍历的图。 2 方案论证 系统需求图的遍历算法是求解图的连通性问题,拓扑问题和求关键路径等算法的基础。然而, 图的遍历要比树的遍历复杂得多。因为图的任何一顶点都有可能和其余的顶点相邻接。所以在访问了某个顶点之后,可能沿着某条路径搜索之后,又回到该点。为了避免统一顶点被访问多次,在图的遍历过程中,必须先记下每个已访问的顶点。介绍一种对有向图和无向图都适用的遍历图的路径即为广度优先搜索。图的广度优先遍历类似于树的前序遍历,采用的遍历方法的特点是尽可能先对纵深方向进行搜索。而在遍历的过程中,可以采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储,对图的遍历采用广度优先遍历进行序列搜索。 功能需求图是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系,每个元素只有一个直接前驱和一个直接后继。图作为一种非线性数据结构,被广泛的应用于多个技术领域,例如系统工程、化学工程、统计力学、遗传学、控制论、人工智能、编译系统等领域,在这些领域中把图结构作为解决问题的数学手段之一。对任意给定的图(顶点数和边数自定) ,建立它的邻接表并输出,然后利用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)实现图的广度优先搜索遍历。画出搜索顺序示意图。 运行环境的要求 Visual C++ 和Windows XP电脑一台。 Visual C++ 不仅是一个 C++ 编译器,而且是一个基于 Windows 操作系统的可视化集成开发环境( integrated development environment,IDE )。Visual C++ 由许多组件组成,包括编辑器、调试器以及程序向导 AppWizard 、类向导 Class Wizard 等开发工具。这些组件通过一