JavaEE鸿蒙应用开发HTML&JS+前端Python+大数据开发人工智能开发电商视觉设计软件测试新媒体+短视频直播运营产品经理集成电路应用开发(含嵌入式)Linux云计算+运维开发C/C++拍摄剪辑+短视频制作PMP项目管理认证电商运营Go语言与区块链大数据PHP工程师Android+物联网iOS.NET

云计算大数据教程图论介绍

来源:黑马程序员

浏览23609人

2019.10.31

图论算法在计算机科学中扮演着很重要的角色,它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题,然后用图论的基本算法加以解决。

一笔画问题

图论的起源可以追溯到大数学家欧拉诞生的那个年代。当时哥尼斯堡城有一个著名的七桥问题,就是每座桥恰好走过一遍并回到原出发点,然而没有人成功过。下图是哥尼斯堡的简化图。

1.png

这个问题的要求:在穿过每座桥仅一次的情况下穿过这个城市

1.每座桥:意味着所有桥都被穿过

2.只穿过一次:意味着每座桥不能被穿越两次及以上

欧拉没有试图去解决这个问题,而是去证明其不可解决。首先,把每一块连通的陆地作为一个顶点,每一座桥当成图的一条边,那么就可以把哥尼斯堡的七座桥抽象成下面的图。

2.png

对于图中的每一个顶点,它相连的边的数量定义为它的度(Degree)

定理:如果一个图能够从一个顶点出发,每条边不重复地遍历回到这个顶点,那么每一顶点的度必须是偶数。

哥尼斯堡抽象的图中,存在多个顶点的度为奇数,所以这个图无法从一个顶点出发,遍历每条边各一次然后回到这个顶点。

图的基本概念

一个图(G)定义为一个偶对(V,E) ,记为G=(V,E) 。其中: V是顶点(Vertex)的非空有限集合,记为V(G);E是无序集V&V的一个子集,记为E(G) ,其元素是图的弧(Arc)。

弧(Arc) :表示两个顶点v和w之间存在一个关系,用顶点偶对<v,w>表示。通常根据图的顶点偶对将图分为有向图和无向图。

有向图(Digraph): 若图G的关系集合E(G)中,顶点偶对<v,w>的v和w之间是有序的,称图G是有向图。

无向图(Undigraph): 若图G的关系集合E(G)中,顶点偶对<v,w>的v和w之间是无序的,称图G是无向图。

图的遍历

图的遍历(Travering Graph):从图的某一顶点出发,访遍图中的其余顶点,且每个顶点仅被访问一次。图的遍历算法是各种图的操作的基础,有深度优先搜索算法和广度优先搜索算法。采用的数据结构是(正)邻接链表。

广度优先搜索算法

广度优先搜索(Breadth-First Search,简称BFS)就像水波一样逐渐向外扩展搜索,它先要尽可能“广”地访问每个节点所直接连接的其他节点。

3.png

例如从A出发,先访问直接和A相连的节点B和C,然后看看有哪些节点和已经访问过的节点相连,如D和E与B相连,F、G和H与C相连,然后访问D、E等节点,直到把所有节点都访问过一遍为止。

深度优先搜索算法

深度优先搜索(Depth-First Search,简称DFS)就像一条路走到黑的搜索,它先要尽可能“深”地访问每个节点。

4.png

例如从A出发,随便找一个相连的节点,比如B,然后从B出发到下一个节点,比如E,再从E出发到下一个节点I,直到找不到更远的节点,在往回找,看看中间是否有尚未访问的节点,如此也可以访问所有的节点。

深度优先搜索算法和广度优先搜索算法都可以保证访问到全部节点,但是不论采用哪种方法,都应该用一个小本本记录已经访问过的节点,避免同一个节点访问多次获这漏掉某个节点,这个小本本就是邻接链表


相关阅读