更新时间:2019年10月16日15时36分 来源:传智播客 浏览次数:
图论算法在计算机科学中扮演着很重要的角色,它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题,然后用图论的基本算法加以解决。
一笔画问题
图论的起源可以追溯到大数学家欧拉诞生的那个年代。当时哥尼斯堡城有一个著名的七桥问题,就是每座桥恰好走过一遍并回到原出发点,然而没有人成功过。下图是哥尼斯堡的简化图。
这个问题的要求:在穿过每座桥仅一次的情况下穿过这个城市
1. 每座桥:意味着所有桥都被穿过
2. 只穿过一次:意味着每座桥不能被穿越两次及以上
欧拉没有试图去解决这个问题,而是去证明其不可解决。首先,把每一块连通的陆地作为一个顶点,每一座桥当成图的一条边,那么就可以把哥尼斯堡的七座桥抽象成下面的图。
对于图中的每一个顶点,它相连的边的数量定义为它的度(Degree)
定理:如果一个图能够从一个顶点出发,每条边不重复地遍历回到这个顶点,那么每一顶点的度必须是偶数。
哥尼斯堡抽象的图中,存在多个顶点的度为奇数,所以这个图无法从一个顶点出发,遍历每条边各一次然后回到这个顶点。
图的基本概念
一个图(G)定义为一个偶对(V,E) ,记为G=(V,E) 。其中: V是顶点(Vertex)的非空有限集合,记为V(G);E是无序集V&V的一个子集,记为E(G) ,其元素是图的弧(Arc)。
弧(Arc) :表示两个顶点v和w之间存在一个关系,用顶点偶对
有向图(Digraph):若图G的关系集合E(G)中,顶点偶对
无向图(Undigraph): 若图G的关系集合E(G)中,顶点偶对
图的遍历
图的遍历(Travering Graph):从图的某一顶点出发,访遍图中的其余顶点,且每个顶点仅被访问一次。图的遍历算法是各种图的操作的基础,有深度优先搜索算法和广度优先搜索算法。采用的数据结构是(正)邻接链表。[推荐了解大数据培训课程]
广度优先搜索算法
广度优先搜索(Breadth-First Search,简称BFS)就像水波一样逐渐向外扩展搜索,它先要尽可能“广”地访问每个节点所直接连接的其他节点。
例如从A出发,先访问直接和A相连的节点B和C,然后看看有哪些节点和已经访问过的节点相连,如D和E与B相连,F、G和H与C相连,然后访问D、E等节点,直到把所有节点都访问过一遍为止。
深度优先搜索算法
深度优先搜索(Depth-First Search,简称DFS)就像一条路走到黑的搜索,它先要尽可能“深”地访问每个节点。
例如从A出发,随便找一个相连的节点,比如B,然后从B出发到下一个节点,比如E,再从E出发到下一个节点I,直到找不到更远的节点,在往回找,看看中间是否有尚未访问的节点,如此也可以访问所有的节点。
深度优先搜索算法和广度优先搜索算法都可以保证访问到全部节点,但是不论采用哪种方法,都应该用一个小本本记录已经访问过的节点,避免同一个节点访问多次获这漏掉某个节点,这个小本本就是邻接链表。
猜你喜欢