这篇文章主要介绍“Java图的遍历怎么理解”,在日常操作中,相信很多人在Java图的遍历怎么理解问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java图的遍历怎么理解”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
创新互联专注为客户提供全方位的互联网综合服务,包含不限于成都网站制作、网站建设、塔什库尔干塔吉克网络推广、小程序制作、塔什库尔干塔吉克网络营销、塔什库尔干塔吉克企业策划、塔什库尔干塔吉克品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;创新互联为所有大学生创业者提供塔什库尔干塔吉克建站搭建服务,24小时服务热线:18982081108,官方网址:www.cdcxhl.com
图的遍历跟树的遍历一样,从图中一点出发遍历图中其余顶点,且使每一个顶点仅被访问一次 叫 Traversing Graph
depth first search DFS 深度优先遍历 深度优先搜索 类似与Tree中 前序遍历
具体算法表述如下:
访问初始结点v,并标记结点v为已访问。
查找结点v的第一个邻接结点w。
若w存在,则继续执行4,否则算法结束。
若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
查找结点v的w邻接结点的下一个邻接结点,转到步骤3。
例如下图,其深度优先遍历顺序为 1->2->4->8->5->3->6->7
bool visited[MAX];//初始化全为false 邻接矩阵 深度优化递归 因为边存在1才能访问 // 递归法 void DFS(MGraph G, int i)//从第i个开始遍历 { visited[i] = true; cout<
邻接表bool visited[MAX];//初始化全为false 邻接表 深度优化递归 // 递归法 void DFS(GraphList G, int i)//从第i个开始遍历 { visited[i] = true; EdgeNode *p = NULL; cout << G.adjlist[i].data;//输出 刚刚遍历的那个节点 p = G->adjlist[i].firstedge;//p指向 邻接表的首地址 while(p) { if(!visited[p->adjvex]) { DFS(G, p->adjvex); } p = p->next; } } void DFSTraverse(GraphList G) //邻接矩阵深度遍历操作 { for(int i=0;i对于n个顶点e个边的图来说 邻接矩阵遍历时间复杂度为O(n^2); 而邻接表复杂度为O(n+e); 对于有向图而言只是在对通道存在可行或者不可行,基本算法上差别不太大
到此,关于“Java图的遍历怎么理解”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!
当前题目:Java图的遍历怎么理解
标题URL:http://njwzjz.com/article/joceei.html