「java图的广度优先遍历」图的广度优先遍历用到的数据结构
今天给各位分享java图的广度优先遍历的知识，其中也会对图的广度优先遍历用到的数据结构进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
图的遍历方法主要包括
图的遍历方法主要包括深度优先搜索法和广度（宽度）优先搜索法两种算法。
广度优先遍历（Breadth First Search），又称为广度优先搜索，简称BFS。深度优化遍历( Depth First Search )，也有称为 深度优化搜索 ，简称为 DFS 。事实上，我们在树的遍历中早已涉及DFS，层序遍历、中序遍历和后序遍历都属于深度优先遍历的方式，因为这些遍历方式本质上都归结于栈。
图的遍历方法复杂性介绍
① 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
图的遍历：深度优先遍历，广度优先遍历
连通图的深度优先遍历类似与树的先根遍历
DFS结果是213546
■用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行
行，时间复杂度为O(n7)。
■用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可
完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+ e)。
稠密图适于在邻接矩阵.上进行深度遍历;
稀疏图适于在邻接表上进行深度遍历。
●如果使用邻接矩阵，则BFS对于每个被访问到的顶点， 都要循巩
检测矩阵中的整整一行( n个元素) ,总的时间代价为O(n7)。
●用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即
可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。
●空间复杂度相同，都是O(n)(借用了堆栈或队列) ;
●时间复杂度只与存储结构(邻接矩阵或邻接表)有关，而与搜索路径无
关。
广度优先遍历是什么？
1.广度优先遍历的思想广度优先遍历类似树的按层次遍历。设初始状态时图中的所有顶点未被访问，则算法思想为：首先访问图中某指定的起始顶点v，并将其标记为已访问过，然后由v出发依次访问v的各个未被访问的邻接点v1，v2，…，vk；并将其均标识为已访问过，再分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v路径相通的顶点都被访问到。
若G是连通图，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述搜索过程，直至图G中所有顶点均被访问为止。
2.广度优先遍历示例例如，对图7－18（a）所示的图G，假设指定从顶点v1开始进行广度优先遍历，首先访问v1，因与v1相邻并且未被访问过的顶点有v2和v6，则访问v2和v6，然后访问与v2相邻并未访问的邻接点v2，v7，再访问与v6相邻并且未被访问过的邻接点v5，按这样的次序依次访问与v2相邻并且未被访问过的邻接点v4，v8，与v7相邻并且未被访问过的邻接点v9，此时，与v5，v4，v8，v9相邻并且未被访问过的邻接点没有了，即图G中的所有顶点访问完，其遍历序列为：v1－＞v2－＞v6－＞v2－＞v7－＞v5－＞v4－＞v8－＞v9。这种顺序不是唯一的，如果从v1出发后，相邻的多个顶点优先选择序号大的顶点访问，其遍历序列为：v1－＞v6－＞v2－＞v5－＞v7－＞v2－＞v4－＞v9－＞v8。同理，图7－18（b）是假设从v1开始，相邻的多个顶点优先选择序号小的顶点访问，其遍历序列为：v1－＞v2－＞v2－＞v4－＞v5－＞v6－＞v7－＞v8；相邻的多个顶点优先选择序号大的顶点访问，其遍历序列为：v1－＞v2－＞v2－＞v7－＞v6－＞v5－＞v4－＞v8。图7－18（c）假设从a开始，相邻的多个顶点优先选择ASCII码小的顶点访问，其遍历序列为：a－＞b－＞d－＞e－＞f－＞c－＞g；相邻的多个顶点优先选择ASCII码大的顶点访问，其遍历序列为：a－＞f－＞e－＞d－＞b－＞g－＞c。
2.广度优先遍历的算法在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点的访问顺序，将访问的每个顶点入队，然后再依次出队。
在广度优先遍历过程中，为了避免重复访问某个顶点，也需要创建一个一维数组visited［n］（n是图中顶点的数目），用来记录每个顶点是否已被访问过。
关于java图的广度优先遍历和图的广度优先遍历用到的数据结构的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。