－DFS（Depth First Search）：深度优先搜索
访问完一个顶点的所有邻接点之后，会按原路返回，对应着堆栈、出栈
void DFS ( Vertex V )
{ visited [ V ] = true ;
for ( V的每个邻接点W )
if ( !visited [ W ] )
DFS ( W ) ;
}
深度优先搜索相当于树的先序遍历
若有N个顶点、E条边，时间复杂度为：
用邻接表存储图，有 O ( N + E )
用邻接矩阵存储图，有 O ( N的平方 )
－BFS（Breadth First Search）：广度优先搜索（相当于树的层序遍历）
树是一种特殊的图，类似于树的层序遍历（队列），图的遍历是先选取一个顶点，将它移出队列时把它所有邻接点入队，重复该操作
void BFS ( Vertex V )
{ visited [ V ] = true ; // 标记为已访问
Enqueue ( V , Q ) ; // 压入队列中
while ( ! IsEmpty ( Q ) ) {
V = Dequeue ( Q ) ;
for ( V的每个邻接点 W )
if ( ! visited [ W ] ){
visited [ W ] = true ;
Enqueue ( W , Q ) ;
}
}
}
若有N个顶点、E条边，时间复杂度是：
用邻接表存储图，有 O ( N + E )
用邻接矩阵存储图，有 O ( N的平方 )
为什么需要两种遍历？两种遍历有不同特点
BFS:对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高
图不连通，怎么遍历？深度遍历和广度遍历都会丢弃孤立结点
连通：如果从V到W存在一条（无向）路径，则称V和W是连通的
路径：V到W的路径是一系列顶点｛V，v1，v2，…，vn，W｝集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。如果V到W之间的所有顶点都不同，则称简单路径。
回路：起点等于终点的路径，带有回路的就不是简单路径
连通图：图中任意两顶点均连通
连通分量：无向图的极大连通子图
极大顶点数：再加1个顶点就不连通了
极大边数：包含子图中所有顶点相连的所有边
对于有向图，有强连通和弱连通之分
强连通：有向图中顶点V和W之间存在双向路径，则称V和W是强连通
弱连通：有向图不是强连通图，但是将该图的路径方向去掉后其变为连通图，则称之为若连通
强连通图：有向图中任意两顶点均强连通
每调用一次DFS（V），就把V所在的连通分量都遍历了一遍。BFS也是一样
void ListComponents ( Graph G ) // 所有分量列出来
{ for ( each V in G )
if ( ! visited [ V ] ) {
DFS ( V ) ; // or BFS ( V )
}
}
图的简单应用
－验证六度空间：
算法思路：
对每个节点，进行广度优先搜索
搜索过程中累计访问的节点数
需要记录“层数”，仅仅计算6层以内的节点数
void SDS ( )
{
for ( each V in G ) {
count = BFS ( V ) ;
Output ( count / N ) ;
}
}
void BFS ( Vertex V )
{
visited [ V ] = true ; count = 1 ; // count 记录访问的结点数量
level = 0 ; last = V ; // level指访问的层数，last为访问该层的最后那个节点
Enqueue ( V , Q ) ;
while ( ! IsEmpty ( Q ) ) {
V = Dequeue ( Q ) ;
for ( V的每个邻接点 W )
if ( !visited [ W ] ) { //每一个V的邻接点W进队列的时候，让tail指向W
visited [ W ] = true ;
Enqueue ( W , Q ) ; count++ ;
tail = W ;
}
if ( V == last ) {
level ++ ; last = tail ; // 当V是最后一个结点时，层数加一
}
if ( level == 6 ) break ; // 层数为6 跳出
} return count ; // 输出访问的总节点数
}
－最短路径问题
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径，这条路径就是两点之间的最短路径（Shortest Path）第一个顶点为源点（Source）最后一个顶点为终点（Destination）
问题分类：
单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
（有向）无权图
（有向）有权图
多源最短路径问题：求任意两顶点间的最短路径
无权图的单源最短路径算法
按照递增（非递减）的顺序找出到各个顶点的最短路。BFS
初始化以下数组：
dist [ W ] = S到W的最短距离
dist [ S ] = 0
path [ W ] = S到W的路上经过的某顶点
void Unweighted ( Vertex S )
{
Enqueue ( S , Q ) ; // 源点入队
while ( ! IsEmpty ( Q ) ) {
V = Dequeue ( Q ) ;
for ( V的每个邻接点 W )
if ( list [ W ] == -1 ) {
dist [ W ] = dist [ V ] + 1 ;
path [ W ] = V ;
Enqueue ( W , Q ) ;
}
}
}
V个顶点E条边，时间复杂度
T = O ( | V | + | E | )
有权图的单源最短路算法（不一定是经过顶点最少的路径）图中没有负值圈
按照递增（非递减）的顺序找出到各个顶点的最短路。Dijkstra算法
Dijkstra算法：令S＝{ 源点 s＋已经确定了最短路径的顶点Vi }，对任一未收录的顶点V，定义 dist [ V ]为S到V的最短路径长度，但该路径仅经过S中的顶点。即路径 { S -> ( Vi 属于 S ) -> V } 的最小长度
若路径是按照递增（非递减）的顺序生成的，则：真正的最短路必须只经过S中的顶点，每次从未收录的顶点中选一个dist最小的收录，增加一个V进入S，可能影响另一个W的dist值（此时V一定在路径上且V有一条直接到W的边）
void Dijkstra ( Vertex s )
{
while ( 1 ) {
V = 未收录顶点中dist的最小值
if ( 这样的V不存在 )
break ;
collected [ V ] = true ;
for ( V的每个邻接点W )
if ( collected [ W ] == false )
if ( dist [ V ] + E小于 dist [ W ] ) {
dist [ W ] = dist [ V ] + E ;
path [ W ] = V ;
}
}
}
//不能解决有负边的情况
如何得到未收录顶点中dist的最小值并完成 dist [ W ] = dist [ V ] + E 操作
方法1：直接扫描所有未收录顶点－O( | V | )，T = O ( | V | 的平方 + | E | )；
方法2：将dist存在最小堆中－O( | E | log| V | )，更新 dist [ W ] 的值－O ( log| V | )，
T = O ( | V | log| V | + | E | log| V | ) = O( | E | log| V | )
多源最短路算法：
方法1：直接将单源最短路算法调用｜V｜遍，T = O ( |V|的立方 + | E | * | V | )，对于稀疏图较优
方法2：Floyd算法，T = O ( | V |的立方 )，对于稠密图较优
void Floyd ( )
{
for ( i = 0 ; i < N ; i ++ )
for ( j = 0 ; j < N ; j ++ ){
D[ i ][ j ] = G[ i ][ j ] ;
path[ i ][ j ] = -1 ;
}
for ( k = 0 ; k < N ; k ++ )
for ( i = 0 ; i < N ; i ++ )
for ( j = 0 ; j < N ; j ++ )
if ( D[ i ][ k ] + D[ k ][ j ] < D[ i ][ j ] ) {
D[ i ][ j ] = D[ i ][ k ] + D[ k ][ j ] ;
path[ i ][ j ] = k ;
}
}
T = O ( | V |的立方 )
－最小生成树问题
连通图边最少
什么是最小生成树：
首先是树，树是一种特殊的图，树没有回路，[ V ]个顶点一定有[ V ]－1条边
生成树：包含全部顶点，[ V ]－1条边都在图里，生成树任意加一条边都会生成回路
边的权重和最小
贪心算法约束：只能用图里有的边，只能正好用掉 [ V ]－1条边，不能有回路
Prime算法：让一颗小树长大：从一顶点开始，寻找一条与该树相连的最小边，在以连结的两个顶点的树为基础，再找与之相关的最小边，加入的边不能形成回路，依此类推。有点像Dijkstra算法
void Prime ( )
{
MST = { s } ; // 初始化一棵最小生成树 选择根结点s
while ( 1 ) {
V = 未收录顶点中 dist 的最小者；// dist定义为一个顶点到这棵生成树的最小距离，dist [ V ] = E( v, w )或正无穷
if ( 这样的V不存在 )
break ;
将V收录进MST；dist [ V ] = 0 ;
for ( V 的每个邻接点 W )
if ( dist [ W ] != 0 ) // W未被收录
if ( E( v, w ) < dist [ W ] ) {
dist [ W ] = E( v, w ) ;
parent [ W ] = V ;
}
}
if ( MST中收录的顶点不到 [ V ] 个 ) // 有为连通的顶点
Error (“生成树不存在”) ;
}
该算法适用于稠密图
Kruskal算法－将森林合并成树，按照权重从小到大把边收录进来，注意不能构成回路
void Kruskal ( graph G )
{
MST = { } ; // MST中收集的是边，所以一开始时空集
while ( MST 中不到 [ V ]－1条边&& E中还有边 ) {
从 E 中取一条权重最小的边 E( v, w ) ; // 用最小堆存放边
将 E( v, w )从 E 中删除；
if ( E( v, w )不在 MST 中构成回路 )
// 用并查集检查是否构成回路，每一个顶点是一个集合，收录边时两棵树变成一棵树，判断新加入的边与原来的是否属于同一棵树
将 E( v, w ) 加入MST；
else
彻底无视 E( v, w )；
)
if ( MST 中不到 [ V ]－1条边 )
Error ( “生成树不存在” )；
}
连通图的最小生成树不是唯一的，思考：
当用Kruskal算法的思想加边的时候出现(两条权重相同并连接的两棵树相同的边)的时候最小生成树路径不唯一
反之当用Kruskal算法的思想加边的时候没出现(两条权重相同并连接的两棵树相同的边)的时候最小生成树路径唯一
或者说决定路径是否唯一的因素是使两棵树距离最小的边是否只有一条，若有多条则不唯一
网友评论