全国咨询/投诉热线:400-618-9090

首页技术文章正文

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

更新时间: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框架视频教程[黑马程序员]

javaee

python

web

ui

cloud

test

c

netmarket

pm

Linux

movies

robot

http://www.itcast.cn/subject/uizly/index.shtml?seozxuids

14天免费试学

基础班入门课程限时免费

申请试学名额

15天免费试学

基础班入门课程限时免费

申请试学名额

15天免费试学

基础班入门课程限时免费

申请试学名额

15天免费试学

基础班入门课程限时免费

申请试学名额

20天免费试学

基础班入门课程限时免费

申请试学名额

8天免费试学

基础班入门课程限时免费

申请试学名额

20天免费试学

基础班入门课程限时免费

申请试学名额

5天免费试学

基础班入门课程限时免费

申请试学名额

0天免费试学

基础班入门课程限时免费

申请试学名额

12天免费试学

基础班入门课程限时免费

申请试学名额

5天免费试学

基础班入门课程限时免费

申请试学名额

5天免费试学

基础班入门课程限时免费

申请试学名额

10天免费试学

基础班入门课程限时免费

申请试学名额
在线咨询 我要报名