[数据结构与算法] DFS中的概念——树边、回溯边、前向边、交叉边

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> DFS中的概念——树边、回溯边、前向边、交叉边 -> 正文阅读

[数据结构与算法]DFS中的概念——树边、回溯边、前向边、交叉边

根据在有向图G上进行深度优先遍历所产生的深度优先森林，可以把图中的边分为四类：

?树边：（Tree edge）
后向边：又称回溯边（Back edge）
前向边：（Forward edge）
交叉边：（Cross edge）
树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树（森林），在这个树上才有了这些概念。对图进行DFS，可以从任意的顶点开始，遍历的方式也是多样的，所以不同的遍历会得到不同的DFS树，进而产生不同的树边，前向边，后向边，横叉边。所以这4种边，是一个相对的概念。