图
发表于 2017-12-19 17:05:22 | 分类于 算法 |
图的相关概念
- 图，是网络结构的抽象模型。
- 图，是一组由边连接的节点（或顶点）。
- 任何二元关系都可以用图来表示
图，在数学及技术上的概念
- 一个图 G = ( V, E ) 由以下元素组成
- V：一组顶点
- E：一组边，连接 V 中的顶点
术语
- 相邻顶点
- 由一条边连接在一起的顶点称为相邻顶点
- 顶点的度
- 一个顶点的度，是其相邻顶点的数量
- 路径
- 是顶点 v <sub>1</sub> ，v<sub>2</sub> ， ...v<sub>k</sub> 的一个连续序列。
- 其中 v<sub>i</sub> ， v<sub>i + 1</sub> 是相邻的。
- 简单路径
- 要求不包含重复的顶点
- 环
- 环也是一个简单路径
- 无环
- 如果图中不存在环，则称该图是无环的。
- 连通
- 如果图中每两个顶点间都存在路径，则该图是连通的。
- 有向图
- 有向图的边有一个方向
- 无向图
- 图的边没有方向
- 强连通
- 如果图中每两个顶点间在双向上都存在路径，则该图是强连通的。
- 加权、未加权
- 图还可以是未加权的、或是加权的。
图的表示
邻接矩阵
- 图最常见的实现是邻接矩阵
- 每个节点都和一个整数相关联，该整数最为数组的索引。
- 用一个二维数组来表示顶点之间的链接。
- 如果索引为 i 的节点和索引为 j 的节点相邻，则
array [ i ][ j ] === 1，否则，array [ i ][ j ] === 0 - 缺点
- 不是强连通的图（稀疏图），如果用邻接矩阵来表示，则矩阵中将会有很多 0，意味着浪费了存储空间来表示不存在的边。
- 例如，找给定顶点的相邻顶点，即使该顶点只有一个相邻顶点，也不得不迭代一整行。
- 图中顶点的数量可能会改变，而 二维数组不太灵活。
邻接表
- 由图中每个顶点的相邻顶点列表组成。
- 可用列表（数组）、链表、散列表、字典，来表示相邻顶点列表。
- 邻接表可能对大多数问题来说都是更好的选择，但以上两种表示法都很有用，且它们有着不同的性质
- 例如，要找出顶点 v 和 w 是否相等，使用邻接矩阵会比较快。
关联矩阵
- 矩阵的行表示顶点，列表时便。
- 如果顶点 v 是边 e 的入射点，则
array [ v ] [ e ] === 1，否则array [ v ][ e ] === 0 - 关联矩阵通常用于边的数量比顶点多的情况，以节省空间和内存。
图的遍历
图遍历
- 可用来寻找特定的顶点或寻找两个顶点之间的路径
- 检检查图是否连通
- 检查图是否含有环等。
广度优先搜索（Breadth-First Search，BFS）
- 从指定的一个顶点开始遍历图
- 先访问其所有的相邻点，就像一次访问图的一层。就是宽后深地访问顶点。
深度优先搜索（Depth-First Search，DFS）
- 从第一个指定的顶点开始遍历图
- 沿着路径直到这条路径最后一个顶点被访问了
- 接着原路退回 。并探索下一跳路径。
- 先深度后广度地访问顶点。
图遍历算法的思想
- 必须追踪每个第一次访问的节点
- 并且追踪哪些节点还没有被完全探索。
- 对于两种图遍历算法，都需要明确指出第一个被访问的顶点。
- 完全探索一个顶点
- 要求查看该顶点的每一条边
- 对于每一条边所连接的没有被访问过的顶点，将其标注为被发现的，并将其加进待访问顶点列表中。
- 为保证算法的效率，访问每个顶点至多两次。
- 当要标注已经访问过的顶点时，用三种颜色反应它们的状态
- 白色：表示该顶点还未被访问
- 灰色：表示该顶点被访问过，但还未被探索过
- 黑色：表示该顶点被访问过且被完全探索过。
广度优先搜索、深度优先搜索对比
| 算法 | 描述 | 数据结构 |
|---|---|---|
| 深度优先搜索 | 栈 | 通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问 |
| 广度优先搜索 | 队列 | 通过将顶点存入队列中，最先入队列的顶点先被探索。 |
图的创建
function Grap ( ) {
//用一个数组来存储图中所有顶点
//用一个字典存储邻接表
var vertices = [ ] ;
var adjList = new Dictionary ( ) ;
// 向图中添加一个新顶点
this.addVertex = function ( v ) {
vertices.push( v ) ;
adjList.set ( v, [ ] ) ;s
} ;
// 添加顶点之间的边
this.addEdge = function ( v, w ) {
adjList.get ( v ).push ( w ) ;
adjList.get ( w ).push( v ) ;
} ;
this.toString = function ( ) {
var s = " " ;
for ( var i = 0; i < vertices.length; i++ ) {
s += vertices [ i ] + " -> " ;
var neighbors = adjList.get ( vertices [ i ] ) ;
for ( var j = 0; j < neighbors.length; j++ ) {
s += neighbors [ j ] ;
}
s += " \n " ;
}
} ;
// 广度优先搜索
// 创建一个队列 Q
// 将 v 标注为被发现的（灰色），并将 v 入队列 Q
// 如果 Q 非空，则运行一下步骤
// 1）将 u 从 Q 中出队列
// 2）将标注 u 为被发现的（灰色）
// 3）将 u 所有未被访问过的临点（白色）入队列；
// 4）将 u 标注为已被探索的（黑色）。
var initializeColor = function ( ) {
var color = [ ] ;
for ( var i = 0; i < vertices.length; i++ ) {
color [ vertices [ i ] ] = "white" ;
}
return color ;
} ;
this.bfs = function ( v, callback ) {
var color = initializeColor ( ) ,
queue = new Queue ( ) ;
queue.enqueue ( v ) ;
while ( ! queue.isEmpty ( ) ) {
var u = queue.dequeue ( ) ,
neighbors = adjList.get ( u ) ;
color [ u ] = "grey" ;
for ( var i = 0; i < negihbors.length; i++ ) {
var w = neighbors [ i ] ;
if ( color [ w ] === "white") {
color [ w ] = "grey" ;
queue.enqueue ( w ) ;
}
}
color [ u ] = "black" ;
if ( callback ) {
callback ( u ) ;
}
}
} ;
// 深度优先搜索
// 并不需要一个源顶点
// 若图中顶点 v 未访问，则访问该顶点 v
// 要访问顶点 v ，步骤如下：
// 1）标注 v 为被发现的（灰色）
// 2）对于 v 的所有未访问的邻点 w：
// 访问顶点 w
// 3）标注 v 为已探索的（黑色）
this.dfs = function ( callback ) {
var color = initializeColor ( ) ;
for ( var i = 0; i < vertices.length; i++ ) {
if ( colo [ vertices [ i ] ] === "white" ) {
dfsVisit ( vertices [ i ], color, callback ) ;
}
}
} ;
// 辅助函数 dfsVisit
var dfsVisit = function ( u, color, callback ) {
color [ u ] = "grey" ;
if ( callback ) {
callback ( u ) ;
}
var neighbors = adjList.get ( u ) ;
for ( var i = 0; i < neighbors.length; i++ ) {
var w = neighbors [ i ] ;
if ( color [ w ] === "white") {
dfsVisit ( w, color, callback ) ;
}
}
color [ u ] = "black" ;
} ;
}
使用 BFS 寻找最短路径
-
给定一个图 G 和源顶点 v ，找出对每个顶点 u ，u 和 v 之间最短路径的距离（以边的数量计）。
-
对于给定顶点 v ，广度优先算法会访问所有与其距离为 1 的顶点，接着是距离为 2 的顶点，以此类推。
-
所以，可以用广度优先算法来接这个问题。
-
修改 bfs 方法以返回一些信息。
- 从 v 到 u 的距离 d [ u ] ；
- 前溯点 pred [ u ] ，用来推导出从 v 到其他每个顶点s u 的最短路径。
this.BFS = function ( v ) {
var color = initializeColor ( ) ,
queue = new Queue ( ) ,
d = [ ] ,
pred = [ ] ;
queue.enqueue ( v ) ;
for ( var i = 0; i < vertices.length; i++ ) {
d [ vertices [ i ] ] = 0 ;
pred [ vertices [ i ] ] = null ;
}
while ( ! queue.isEmpty ( ) ) {
var u = queue.dequeue ( ) ,
neighbors = adjList.get ( u ) ;
color [ u ] = "grey" ;
for ( i = 0; i < neighbors.length; i ++ ) {
var w = neighbors [ i ] ;
if ( color [ w ] === "white" ) {
color [ w ] = "grey" ;
d [ w ] = d [ u ] + 1 ;
pred [ w ] = u ;
queue.enqueue ( w ) ;
}
}
color [ u ] = "black" ;
}
return {
distances : d,
predecessors :pred
} ;
} ;
深入学习最短路径算法
- 本章中的图不是加权图
- 如果计算加权图中的最短路径（例如，城市 A 和城市 B 之间的最短路径——GPS 和 Google Maps 中用到的算法），广度优先搜索未必合适
- Dijkstra's 算法解决了单源最短路径问题
- Bellman-Ford 算法解决了边权值为负的单源最短路径问题
- A* 搜索算法解决了求仅一对顶点间的最短路径问题，它用经验法则来加速搜索过程。
- Floyd-Warshall 算法解决了求所有顶点对间的最短路径问题
探索深度优先算法
- 对于给定的图 G ，
- 希望深度优先搜索算法遍历图 G 的所有节点，构建 ”森林“ （有根树的一个集合）以及一组源顶点（根），
- 并输出两个数组：
- 发现时间
- 完成探索时间
- 可以修改 dfs 方法来返回一些信息：
- 顶点 u 的发现事件 d [ u ]
- 当顶点 u 被标注为黑色时， u 的完成探索实践 f [ u ]
- 顶点 u 的前溯点 p [ u ]
var time = 0 ;
this.DFS = function ( ) {
var color = initializeColor ( ) ,
d = [ ] ,
f = [ ] ,
p = [ ] ;
time = 0 ;
for ( var i = 0; i < vertices.length; i++ ) {
f [ vertices [ i ] ] = 0 ;
d [ vertices [ i ] ] = 0;
p [ vertices [ i ] ] = null ;
}
for ( i = 0; i < vertices.length; i++ ) {
if ( color [ vertices [ i ] ] === "white" ) {
DFSVisit ( vertices [ i ], color, d, f, p)
}
}
return {
discocery : d;
finished : f,
predecessors : p
} ;
} ;
// 辅助函数
var DFSVisit = function ( u, color, d, f, p ) {
console.log ( "discoveryed " + u ) ;
color [ u ] = "grey" ;
d [ u ] = ++time ;
var neighbors = adjList.get ( u ) ;
for ( var i = 0; i < neighbors.length; i++ ) {
var w = neighbors [ i ] ;
if ( color [ w ] === "white" ) {
p [ w ] = u ;
DFSVisit ( w, color, d, f, p ) ;
}
}
color [ u ] = "black" ;
f [ u ] = ++time ;
console.log ( "explored " + u ) ;
} ;
拓扑排序
当需要编排一些任务或步骤的执行顺序时，这称为拓扑排序（topological sorting）。
拓扑排序只能用于有向无环图（DAG）