而类似于下图的图是有方向的 ? 我们称之为有向图(Directed Graph)，在有向图中，只能够从起始顶点出发到达方向末端的相邻顶点，相反则不可以。...在无向图中，一个顶点的度(degree)，就是这个顶点相邻的边数，这里也是在说简单图，不考虑自环边和平行边。但在一个有向图中，一个顶点的度的概念不同。...所以我们可以看到下图中0这个顶点有两个邻边0-1、0-3，所以0这个顶点的度就是2. 无权无向图的邻接矩阵 ? ?...时间复杂度 O(V + E) 无权无向图的非递归深度优先遍历 我们来看一下二分搜索树的非递归前序遍历 public void preOrderNR() {...无向图的环检测 当我们要判断一个图中是否有环的时候，不论这个图是否有多个联通分量。
图的遍历算法是求解图的连通性，拓扑排序和关键路径等算法的基础。 根剧搜索路径的方向，通常有两条遍历图的路径： 深度优先搜索（DFS）和广度优先搜索（BFS）。 对于有向图和无向图都适用。...深度优先搜索遍历连通图 1）从图中某个顶点出发，访问v，并置visited[v]的值为true. 2) 依次检查v的所有的邻接点w，如果visited[w]的值为false,再从w出发进行递归遍历，...visited[w]) DFS(G,w);//对v尚未访问的邻接点w递归调用DFS; } 那么对于非连通图的遍历，我们可以看做是一个个连通分量，循环调用多少次，那么就有多少个连通分量。...用深度优先遍历非连通图 void DFS(Graph G){//对非连通图G做深度优先遍历 for(v = 0;v < G.num;++v) visited[v] = false;...，并写代码做题了 DFS算法思想：一直往深处走，直到找到解或者走不下去为止； 一般DFS使用栈保存未被检测的结点，结点深度优先的次序被访问并被依次压入栈中，并以相反的次序出栈进行新的检测。
垃圾收集 无向图的环检测:在无向图中，BFS或DFS可以用来检测循环。在有向图中，只有深度首先可以使用搜索。 在Ford-Fulkerson算法中，可以使用广度先或深度先遍历，找到最大流。...visited[*i]) DFS(*i, visited); } 应用 对于无权图，DFS可以生成最小生成树。 检测图中是否有循环。...查找给定节点uv之间是否有路径 拓扑排序 判断一个图是否可以二分 寻找图的强连通分量 迷宫问题 深度优先遍历的非递归实现 void DFS(int s, vector &visited) {...检测有向图中是否有环 ? 如在上图中，是存在0->2->0这样的环。3->3的环。当且仅当存在一条后向边才可以认为图中有环。...后向边(u,v)是指节点u连接到其在深度优先搜索树中的一个祖先节点v这样的一条边。3->3这样的自循环也可以认为是一条后向边。 为了检测图中的后向边，对DFS递归函数的中递归栈进行跟踪。
那么本文就结合具体的算法题，来说两个图论算法：有向图的环检测、拓扑排序算法。...这两个算法既可以用 DFS 思路解决，也可以用 BFS 思路解决，相对而言 BFS 解法从代码实现上看更简洁一些，但 DFS 解法有助于你进一步理解递归遍历数据结构的奥义。...看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。...很显然，如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。 但是我们这道题和拓扑排序有什么关系呢？...环检测算法（BFS 版本） 刚才讲了用 DFS 算法利用 onPath 数组判断是否存在环；也讲了用 DFS 算法利用逆后序遍历进行拓扑排序。
[在这里插入图片描述] 连通图 - 无向图 - 图G中任意两个顶点之间都有路径相通 - 连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。...- 有向图 - 强连通图：任意两个顶点之间都存在一条有向路径 - 强连通分量：极大强连通子图 [在这里插入图片描述] 极小连通子图： 该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通...visited[w]) DFS(G, w); // 如果w未访问，则递归调用DFS p = p->nextarc; // p指向下一个边结点 } } --- DFS算法效率分析 用邻接矩阵来表示图...广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。 因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。...} } } 非连通图 /*------------广度优先非递归遍历连通图G（非连通图）------------*/ void BFSTraverse(Graph G){ for(v = 0; v
拓扑排序还可以用于检测一个有向图是否有环。相关的概念还有 AOV 网，这里就不展开了。 算法流程： 1、在开始排序前，扫描对应的存储空间（使用邻接表），将入度为 0 的结点放入队列。...2、只要队列非空，就从队首取出入度为 0 的结点，将这个结点输出到结果集中，并且将这个结点的所有邻接结点（它指向的结点）的入度减 1，在减 1 以后，如果这个被减 1 的结点的入度为 0 ，就继续入队。...---- DFS 原理是通过 DFS 判断图中是否有环。..., marked)) return false; } // 在遍历的过程中，一直 dfs 都没有遇到已经重复访问的结点，就表示有向图中没有环 // 所有课程任务可以完成，应该返回 true...for (auto gra : graph[i]) { // 层层递归返回 true ，表示图中存在环 if (dfs(gra, graph, marked)) return true
课程表—拓扑排序篇一上，增加了一个记录拓扑序列的功能，因此建议没有看前一篇的同学，先看前一篇，再来阅读本篇 ---- 拓扑排序—BFS 引言: 「拓扑排序」是专门应用于有向图的算法； 「拓扑排序」的结果不唯一...； 删除结点的操作，通过「入度数组」体现，这个技巧要掌握； 「拓扑排序」的一个附加效果是：能够顺带检测有向图中是否存在环，这个知识点非常重要，如果在面试的过程中遇到这个问题，要把这一点说出来。...2、只要队列非空，就从队首取出入度为 0 的结点，将这个结点输出到结果集中，并且将这个结点的所有邻接结点（它指向的结点）的入度减 1，在减 1 以后，如果这个被减 1 的结点的入度为 0 ，就继续入队。..., marked, res)) return vector(); } // 在遍历的过程中，一直 dfs 都没有遇到已经重复访问的结点，就表示有向图中没有环 // 所有课程任务可以完成...for (auto p : adj[i]) { // 层层递归返回 true ，表示图中存在环 if (dfs(p, adj, marked, res)) return true
争哥把图比作成微信的好友关系，其实非常的形象。比如，上面图中的顶点都代表一个微信的用户。 整个微信的好友关系就可以用一张图来表示。...其实有向无环图也好理解的，“有向”指的是有方向，准确的说应该是同一个方向，“无环”则指够不成闭环，像上面例子的图。很多时候有向图，多指的是有向无环图。...这是不可能的。 这道题剥去包装的外衣后，其实是「有向图检测是否有环问题」，有环则代表修完全部课程不能实现。...当 queue 非空时，依次将队首节点出队，在课程安排图中删除此节点 pre： 但并不是真正从邻接表中删除此节点 pre，而是将此节点对应所有邻接节点 cur 的入度 -1，即 indegrees[cur...DFS的操作步骤如下（递归方式）：1，初始化每个节点，令其访问标志为0 2，对初识节点调用DFS访问， 只要p不空即（即边表不空)，如该节点没被访问过就递归调用DFS来访问，访问过以后标志记为1，否则p
邻接矩阵法 所谓邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系）。...因此，在实际存储邻接矩阵时只需要存储上（或下）三角矩阵的元素即可 对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度；对于有向图，邻接矩阵的第i行（或第i列）非0元素的个数正好是第...但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。...image.png DFS算法是一个递归算法，需要借助一个递归工作栈，最坏情况下（一个竖排），它的空间复杂度为O(|V|)。...弗洛伊德算法同样也适用与带权无向边 关键路径 带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图为用边表示活动的网络，简称为AOE网。
---- 广度优先遍历（BFS） BFS 算法的思想是:对一个无向连通图,在访问图中某一起始顶点 v 后,由 v 出发,依次访问 v 的所有未访问过的邻接顶点 w1, w2, w3, …wt;然后再顺序访问...的未访问的连接点为起点，DFS搜索图，直至图中所有与v0路径相通的顶点都被访问。...3）若该图为非连通图，则图中一定还存在未被访问的顶点，选取该顶点为起点，重复上述DFS过程，直至图中全部顶点均被访问过为止。...//非递归深度优先遍历DFS void DFS2(int vertex){ stack stack; stack.push(vertex); //当前结点入栈...（DFS）序列为："<<endl; graph.DFS1(now); cout<<endl; graph.reset(); cout<<"非递归深度优先遍历（DFS）
有向环的检测问题是拓扑排序的基础问题，可以采用两种思路DFS&&BFS，DFS的想法很简单，先简单说说。...这是典型的无状态记录递归方法，而因为在一条DFS调用链上，我们得利用重复访问结点这个性质来检测有向环，所以把它带入到了DFS的参数列表中，比如我们DFS(V)时，紧接着DFS(W)，在DFS(X)，此时若没有有向环...那如何确保不存在有向环呢，用onStack去检测，它在递归返回时，会还原现场，当然得还原，否则就出现了第一个版本提到的问题，检测出错。一旦检测出有向环，整个函数返回。...除非DFS的运气很好，一眼看准了有向环，直接检测出来，但多少受限于数据输入分布。...理解了有向环的检测，拓扑排序就很容易实现了。
有向图数据结构 初始化时构造一张图，但只有顶点个事，顶点之间没有边相连。 用邻接表表示有向图。 调用addEdge()方法可以将课程之间先修关系写到图中。...} public Iterable adj(int v) { return adj[v]; } } 判断有向图中是否有环...用一个数组boolean[] onStack保存递归调用期间栈上的所有顶点. onStack[v]=true,记录顶点v出现在这次dfs中，在这次dfs结束后，是onStack[v]=false 在递归执行...dfs的过程中，记录当前下当前顶点在递归调用栈中，这样以后的递归调用栈只要判断它的相连点是否在之前的递归调用栈中出现过，就能判断是否有环。...顶点v是否在栈中 private boolean hasCycle; // 有向图中是否环 public DirectedCycle(Digraph G)
3.2.1 先序遍历 递归实现先序遍历 非递归方式实现先序遍历 （栈） 3.2.2 中序遍历 递归实现中序遍历 非递归实现中序遍历 3.2.3 后序遍历 递归实现后续遍历 非递归实现后序遍历 一、二叉树的性质...从上面的图中我们可以分析出，二叉树每个节点至少是有一个数据域，然后还有两个子节点，所以可以构建出如下数据结构 数据结构用代码实现如下 public class TreeNode { int val;...DFS DFS 即深度优先搜索，同 BFS，在树和图中也是非常常见的。...= null) rightNode.frontShow(); } } 非递归方式实现先序遍历 （栈） 走完一遍递归的节点遍历方式，接下来我们走一遍非递归 的先序遍历。...答：我们使用递归可以解决的问题，那么就一定有非递归的方法解决问题，在上述的 “遍历过程中” ，有一个重要的点就是，当我们的一个节点访问到头了（这个节点没有子节点），就需要回溯 到上一个节点，然后完成剩下的遍历任务
虽然有圈图没有拓扑序列，但是我们可以利用拓扑排序的算法来判断一个有向图是否有圈。 算法描述如下： 1. 将所有入度为0的顶点放入队列； 2....否则，说明总 有顶点入度不为0，没有放入队列中，即该有向图有圈。...DFS 关于DFS的介绍请戳我，通过稍微修改DFS，利用递归的特点，也可以判断有向图是否有圈。...用如下样例模拟出递归过程帮助理解。 图解如下（好吧，画的有点丑，将就看吧(●'◡'●)）： 样例一（有环）： 3 3 1 2 2 3 3 1 ?...\n"); } return 0; } 上述利用DFS判断有向图是否有圈实际上是利用了深度优先生成树的性质：有向图无圈当且仅当其深度优先生成树没有回退边， 而上述算法中的vis[graph
欧拉图 本文从哥尼斯堡七桥的故事说起。 哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个话题：怎样不重复地走遍七桥，最后回到出发点。...欧拉图的几个概念： 欧拉回路：指在图（无向图或有向图）中，经过图中所有边且只经过边一次所形成的回路，称为欧拉回路。具有欧拉回路的图称为欧拉图。...欧拉图的判定法： 无向图是欧拉图当且仅当：非零度顶点是连通的；顶点的度数都是偶数。 无向图是半欧拉图当且仅当：非零度顶点是连通的；恰有 2 个奇度顶点。...有向图是欧拉图当且仅当：非零度顶点是强连通的；每个顶点的入度和出度相等。...有向图是半欧拉图当且仅当：非零度顶点是弱连通的；至多一个顶点的出度与入度之差为 1；至多一个顶点的入度与出度之差为 1；其他顶点的入度和出度相等。 2.
顶点的入度，表示有多少条边指向这个顶点； 顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。 ? 2. 存储方法 2.1 邻接矩阵 Adjacency Matrix ?...首先，邻接矩阵的存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。 其次，用邻接矩阵存储图的另外一个好处是方便计算（矩阵运算）。...（0无向图，1有向图） int v; //顶点个数 int e; //边数量 int ew[MaxNum][MaxNum...('E'); ag.dfs_r('A','H'); ag.dfs('E');//非递归版本dfs貌似路径不太合理, // 如 B E G H F D C A && E G...H F C D A B //可能非递归版的dfs就不叫dfs了，我瞎说的 ag.dfs('A','H'); ?
类型 图的类型分为很多种，具体如下： 3.1 有向图 & 无向图 3.2 连通图 定义 图中任意顶点都是连通的图 具体相关概念 对于有向图 & 无向图，连通图的的具体概念又不同，具体如下...对于无向图： 对于有向图： 3.3 其余类型图 4....图的遍历 数据结构：图文详解二叉树（遍历、类型、操作） 5.1 定义 从图中某1顶点出发，遍历图中其余所有顶点 & 使每1个顶点仅被访问1次 5.2 遍历方式 深度优先遍历（DFS）、广度优先遍历（BFS...） 5.3 具体介绍 5.3.1 深度优先遍历（ DFS ） 简介 算法示意图 具体实现：递归 & 非递归 此处图的存储结构 = 邻接矩阵 import java.util.Stack; public...最小生成树 本节主要讲解 图中的 最小生成树 6.1 定义 构造 连通网图 的最小成本生成树 网图：带有权值的图 最小成本：用（n-1）条边将 含n个顶点的连通图 连接起来 & 使得权值和最小 6.2
图的遍历是图论中的基本操作之一，通过遍历图中的所有节点和边，可以理解图的结构并解决实际问题。常见的图遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS）。...深度优先搜索的步骤 从起始节点开始，将其标记为已访问。 对于当前节点的每个相邻节点： 如果相邻节点未被访问，递归地执行深度优先搜索。 回溯到上一个节点，继续探索其他未被访问的相邻节点。...和BFS都可以用于寻找图中的路径。...连通性检查：通过DFS或BFS，可以检查图的连通性，确定图中是否存在路径连接所有节点。 最短路径搜索：BFS适用于在无权图中寻找两个节点之间的最短路径。...拓扑排序：在有向无环图（DAG）中，可以使用DFS进行拓扑排序。 环路检测：通过DFS可以检测图中是否存在环路。 四、总结 图的遍历是理解图结构和解决图论问题的重要工具。
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。 注意： 以下假定遍历过程中访问顶点的操作是简单地输出顶点。...（1）一个图的DFS序列不一定惟一 当从某顶点x出发搜索时，若x的邻接点有多个尚未访问过，则我们可任选一个访问之。...5、算法分析 对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。...从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。 ...3、上一节我们实现了一个基于堆栈的程序，然后用递归改写了它，用函数调用的栈帧实现同样的功能。本节的DSF算法是基于堆栈的，请把它改写成递归的程序。
顶点相连接的边的条数就被称为度（degree），图中顶点 A 的度就是 3 。 ? 还有一种图，图中的边是有方向的，如图所示，则将这种图称为有向图。度这种概念在有向图中又被扩展为入度和出度。...邻接表 图的另一种存储方法，是使用邻接表（Adjacency List）。如图所示，有向图中的每个顶点对应一个链表，该链表中存储的是该顶点指向的顶点。...深度优先搜索采用的思想是回溯思想，这种思想比较适合使用递归。我们使用递归的方式实现一下 DFS。相比 BFS，DFS 多了一个 find 变量，这个变量用于判断是否有找到顶点的。...在图的遍历这小节内容，你会看到非递归的方式。 ★深度优先搜索找到的并不是最短路径。...这两种算法适用于图不大的情况。 深度优先搜索主要借助了栈的方式，这个栈可以是函数调用栈也可以是栈这种数据结构（因为递归也可以转化为非递归的方式）。广度优先搜索主要使用队列。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
