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

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

一笔画问题

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

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

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)中，顶点偶对的v和w之间是有序的，称图G是有向图。

无向图(Undigraph)： 若图G的关系集合E(G)中，顶点偶对的v和w之间是无序的，称图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，直到找不到更远的节点，在往回找，看看中间是否有尚未访问的节点，如此也可以访问所有的节点。

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

猜你喜欢

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

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