（浙大-19-夏-数据结构学习笔记+代码)图的遍历+深度优先+广度优先（Graph)

深度优先搜索（DFS)

void DFS(Vertex v)
{
	visited[ v ] = 1;//先做改变，确认已做
	for( v 的每一个邻接点 ）
		if( !visited [ w ] )//递归他的每一个邻接点，若未做
			DFS( w );//递归邻接点
}

若有 N 个顶点，E 条边，时间复杂度是

• 用邻接表存图，O ( N + E );
• 用邻接矩阵存图，O ( N^2 );

---

广度优先搜索(BFS)

void BFS( Vertex v)
{
	visited[ v ] = 1;//标记访问过
	Enqueue( v , Q );//入队
	while( !Isempty( Q ) )
	{
		v = Dequeue( Q );//出队一个节点
		for( v 的每一个邻接点 w ）
		   if( !visited[ w ] )
		   {
		   	visited[ w ] = 1;
		   	Enqueue( w , Q );
		   }
	}
}  

若有 N 个顶点， E 条边，时间复杂度是：

1. 用邻接表存图O ( N + E );
2. 用邻接矩阵存图 O ( N ^2 );

---

代码引自中国MOOC该课示例

/* 邻接表存储的图 - DFS */
 
void Visit( Vertex V )
{
    printf("正在访问顶点%d\n", V);
}
 
/* Visited[]为全局变量，已经初始化为false */
void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
{   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
    PtrToAdjVNode W;
     
    Visit( V ); /* 访问第V个顶点 */
    Visited[V] = true; /* 标记V已访问 */
 
    for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
        if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
            DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
}

/* 邻接矩阵存储的图 - BFS */
 
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
bool IsEdge( MGraph Graph, Vertex V, Vertex W )
{
    return Graph->G[V][W]<INFINITY ? true : false;
}
 
/* Visited[]为全局变量，已经初始化为false */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
{   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
    Queue Q;     
    Vertex V, W;
 
    Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
    /* 访问顶点S：此处可根据具体访问需要改写 */
    Visit( S );
    Visited[S] = true; /* 标记S已访问 */
    AddQ(Q, S); /* S入队列 */
     
    while ( !IsEmpty(Q) ) {
        V = DeleteQ(Q);  /* 弹出V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未访问过 */
            if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                /* 访问顶点W */
                Visit( W );
                Visited[W] = true; /* 标记W已访问 */
                AddQ(Q, W); /* W入队列 */
            }
    } /* while结束*/
}

---

两种算法优缺点(应用网上某评论，引自中国MOOC该课讨论区，暂不明原作者）
一、深度优先搜索法（DFS）的显著特点是
（1）深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。
（2）深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的结点（即深度最大的结点）先进行扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是，仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。
（3）不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。
（4）不一定会得到最优解，这个时候需要修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。
二、广度优先搜索法（BFS）的显著特点是：
（1）在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的结构。
（2）当结点到跟结点的费用（有的书称为耗散值）和结点的深度成正比时，特别是当每一结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，则得到的解不一定是最优解。这一类问题要求出最优解，一种方法是使用后面要介绍的其他方法求解，另外一种方法是改进前面深度（或广度）优先搜索算法：找到一个目标后，不是立即退出，而是记录下目标结点的路径和费用，如果有多个目标结点，就加以比较，留下较优的结点。把所有可能的路径都搜索完后，才输出记录的最优路径。
（3）广度优先搜索算法，一般需要存储产生的所有结点，占的存储空间要比深度优先大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。
（4）比较深度优先和广度优先两种搜索法，广度优先搜索法一般无回溯操作，即入队和出队的操作，所以运行速度比深度优先搜索算法法要快些。
总之，一般情况下，深度优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。因此在选择用哪种算法时，要综合考虑。决定取舍。

---

图不连通怎么办？
3. 连通：如果从 v 到 w 存在一条（无向）路径，则称 v 和 w 是连通的；
4. 路径：v 到 w 的路径是一系列顶点{v,v1,v2,v3,v4…w}的集合，其中任意一对相邻的顶点之间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。如果 v 到 w 之间的所有顶点都不同，则称简单路径；
5. 回路：起点等于终点的路径；
6. 连通图：图中任意两个顶点均连通；
无向图
连通分量：极大连通子图；

• 极大顶点数：再加一个顶点就不连通了；
• 极大边数：包含子图中所有顶点相连的所有边；

有向图

• 强连通：有向图中顶点 v 和 w 之间存在双向路径，则称 v 和 w 是强连通的；
• 强连通图：有向图中的任意两点顶点均连通；
• 强连通分量：有向图的极大连通子图；

---

• 具有 N 个顶点的无向图至多有 N 个连通分量;
• 如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是连通图;
• 具有个顶点的无向图至少有 1 个连通分量;