现实场景

图模型在现实中有很多应用场景，例如交通网络、商业交易、通信网络等。一般有四种比较重要的图模型：无向图、有向图、加权图和加权有向图。所谓图是由一组顶点和能够将两个顶点相连接的边构成。

图的相关概念

如果两个顶点通过一条边相连，我们称这两个顶点相邻。子图是由一幅图所有边的子集构成。需要注意的是很多具体问题中是需要识别各种类型的子图。路径是由边顺序连接的一系列顶点。

• 连通图：如果从这幅图的任意一个顶点都可以找到一条路径达到另外一个顶点，那这幅图是连通图。一个非连通图是由多个连通图构成，每一个连通图都是它的极大连通子路。
• 针对无向图，我们讨论两个顶点之间的连通性；但针对有向图，我们讨论两个顶点的可达性。可达性比连通性有的时候要更加难以确定。
• 平行边：连接同一对顶点的两条边；一般含有平行边的图称为多重图。
• 自环：一条连接一个顶点和自身的边
• 简单图：不包含平行边和自环的图
• 简单路径：没有重复顶点的路径
• 环：一条至少含有一条边且起点和终点相同的路径 ，所以说自环不属于环。
• 简单环：不含有重复的顶点和边的环，除去起点和终点必须相同之外。
• 无环图：不包含环的图。树就是一个无环连通图
• 有向环：一条至少包含了一条边且起点和终点相同的有向路径。简单有相环：一条（除去起点和终点必须相同之外）不含有重复的顶点和边的环。

关键数据结构：树

树是一副无环的连通图。互不相连的树构成了一个森林。连通图的生成树是它的一个子图，包含了所有的顶点。图的生成森林是他所有连通子图的生成树的集合。一个图有多个生成树，在现实世界中，经常需要找到连接所有顶点，但代价最小的情况，例如班车线路，一定要能够覆盖所有的顶点，但要求这些顶点之间的行程最短，这个就是最小生成树算法。
树的性质：

• 有V-1条边且不包含环，且连通
• 是连通的，但删除任何一条边，都会产生一条环
• 是无环图，但添加任意一条边都会产生一条环

有向图

在有向图中，两个顶点的之间关系有四种：没有连接、两个方向的连接两种情况，以及同时存在两个方向的连接（i.e. 双向连接）。

B（广度优先）FS和D（深度优先）FS

都用于无向图的遍历和搜索。一般DFS用于确定图是否是连通图，或者定位到多个连通分量，也就是寻找拓扑结构。BFS也可以用于遍历图，但更多用于找到两点之间的最短路径。如果图是有向图的时候，也可以利用DFS和BFS搜索到和给定某个顶点的所有顶点。

如果图是加权图的时候，BFS就不适用于寻找最短路径了，因为边的个数不一定就是最小权重。在实现的数据结构上，DFS使用栈、BFS使用队列，前者先进后出，后者先进先出。复杂度上，都是O(V + E)。
这篇是写的比较通俗易懂的两种算法比较的文章

DFS的应用

程序内存的垃圾回收策略。如果和当前可直接访问的对象不可达，就可以被释放，从而供新对象使用。这个图每个顶点就是对象，对象之间的连接是是否可以被引用。

DFS可以用于检测有向图中是否有有向环，但BFS不可以。

最小生成树（MST）算法

最小生成树是给定一幅加权的无向图，找到一颗最小的生成树。MST：minimum spaning tree。
需要注意的是，在求解MST的时候，每条边的权重可以相同、可以是负数、也可以是0。如果不同边的权重可以相同，那一个连通图就会存在多个MST。

加权图

将每条边关联一个权值就是一个加权图。

Prim和Kruskal算法

TBF

Dijkstra算法

在非负有向图中寻找单源最短路径。算法复杂度：O(n**2)。邓俊辉老师讲解的这个很有意思，学堂在线-Dijstra算法-计算机和人生不一样。人生中应该有对人性的尊重，对情感的忠诚。计算机只是你工作时候使用的工具。
Dijkstra算法不能处理负数权重边的原因是因为它无法对已经找到最短路径D点进行二次更新，可以参见Dijkstra算法为什么无法处理负数的边。但Dijkstra是可以处理有环图的。算法的伪代码描述

最后

以上就是单薄火为你收集整理的算法：图模型现实场景图的相关概念的全部内容，希望文章能够帮你解决算法：图模型现实场景图的相关概念所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。