首页技术文章正文

图论算法介绍[大数据培训]

更新时间:2019-10-16 来源:黑马程序员 浏览量:

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

一笔画问题

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


1571210855807_图论1.jpg


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

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

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

欧拉没有试图去解决这个问题,而是去证明其不可解决。首先,把每一块连通的陆地作为一个顶点,每一座桥当成图的一条边,那么就可以把哥尼斯堡的七座桥抽象成下面的图。【推荐里了解黑马程序员大数据培训课程

1571210888542_图论2.jpg


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

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

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

图的基本概念

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

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

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

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

图的遍历

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

广度优先搜索算法

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

1571210916095_图论3.jpg


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

深度优先搜索算法

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

1571210928214_图论3.jpg


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

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

猜你喜欢

什么是数据库?数据库有什么特点?

Spring Security框架视频教程[黑马程序员]

分享到:
在线咨询 我要报名
和我们在线交谈!