1. 图的遍历算法

图的遍历是指从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问次的过程。
图的遍历算法是求解图的连通性问题、拓扑排序及求关键路径等算法的基础。
图的遍历要比树的遍历复杂得多。因为图的任一个结点都可能与其余顶点相邻接，所以在访问了某个顶点之后，可能沿着某路径又回到该结点上，为了避免对顶点进行重复访问，在图的遍历过程中必须记下每个已访问过的顶点。深度优先搜索和广度优先搜索是两种遍历图的基本方法。

1.1 深度优先搜索

类似树的先根遍历，在第一次经过一个顶点时就进行访问操作。遍历步骤如下：

1. 设置搜索指针 p，使p指向顶点。
2. 访问p所指顶点，并使p指向与其相邻接的且尚未被访问过的顶点。
3. 若p所指顶点存在，则重复步骤(2)，否则执行步骤(4)。
4. 沿着刚才访问的次序和方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的顶点，然后重复步骤(2)，直到所有的顶点均被访问为止。

int visited[MaxN] = {0};  //调佣遍历算法前设置所有的顶点都被访问过
void Dfs(Graph G, int i)
{
	EdgeNode *t; int j;
	printf("%d",i);               //访问序号为i的顶点
	visited[i] = 1;               //序号为i的顶点已被访问过
	t = G.Vertices[i].firstarc;   //取顶点i的第一个邻接顶点
	while(t!=NULL){               //检查所有与顶点i相邻接的顶点
	j=t->adjvex;                 //顶点j为顶点i的一个邻接顶点
	if(visited[j]==0)           //若顶点j未被访问则从顶点j出发进行深度优先搜索
		Dfs(G,j);
	t=t->nextarc;              //取顶点i的下一个邻接顶点
	}
}

1.2 广度优先搜索

图：广度优先搜索

图的广度优先搜索方法为:从图中的某个顶点v出发，在访问了之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选图中的一个未被访问的顶点作为起点，重复上述过程，直到图中所有的顶点都被访问到为止。
广度优先遍历图的特点是尽可能先进行横向搜索，即最先访问的顶点的邻接点也先被访问。为此，引入队列来保存已访问过的顶点序列，即每当一个顶点被访问后，就将其放入队列中，当队头顶点出队时，就访问其未被访问的邻接点并令这些邻接顶点入队。

void Bfs(Graph G)
{
	EdgeNode *t; int i,j,k;
	int visited[MaxN]={0};          //调用遍历算法前设置所有的顶点都没有被访问过
	initQueue(Q);                  //创建一个空队列
	for(i=0;i<G.Vnum;i++)
	{
		if(!visited[i]){               //顶点i未被访问过
			enQueue(Q,i);
			printf("%d",i);visited[i]=1;    //访问顶点i并设置已访问标志
			while(!isEmpty(Q)){            //若队列不空，则继续取顶点进行广度优先搜索
				deQueue(Q,k);
				t=G.Vertices[k].firstarc;
				for(;t;t=t->nextarc){      //检查所有与顶点K相邻接的顶点
					j=t->adjvex;           //顶点j是顶点k的一个邻接顶点
					if(visited[j]==0){     //若顶点j未被访问过，将j加入队列
						enQUeue(Q,j);
						printf("%d",j);    //访问序号为j的顶点并设置已访问标志
						visited[j]=1;
					}
				}
			}
		}
	}
}

2. 最小生成树求解算法

生成树：设图G=（V，E）是个连通图，如果其子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。
对于有n个顶点的连通图，至少有 n-1 条边，而生成树中恰好有 n-1条边，所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边，则必然形成回路。
图的生成树不是唯一的。对于非连通图而言，每个联通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。

最小生成树：对于连通网来说，边是带权值的，生成树的各边也带权值，于是就把生成树各边的权值总和称为生成树的权,把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两种常用的求解最小生成树算法。

普里姆(Prim)算法

克鲁斯卡尔(Kruskal)算法

3. 拓扑排序

在工程领域，一个大的工程项目通常被划分为许多较小的子工程(称为活动)，当这些子工程都完成时，整个工程也就完成了。若以顶点表示活动，用有向边表示活动之间的优先关系,则称这样的有向图为以顶点表示活动的网(Activity On Vertex network,AOV 网)。在有向网中若从顶点$v_i$到顶点$v_j$有一条有向路径，则顶点$v_i$是$v_j$的前驱，顶点$v_j$是$v_i$的后继。若$<v_i,v_j>$是网中的一条弧，则顶点$v_i$是$v_j$的直接前驱，顶点$v_j$是$v_i$的直接后继。AOV 网中的弧表示了活动之间的优先关系，也可以说是一种活动进行时的制约关系。

在 AOV 网中不应出现有向环、回路若存在的话，则意味着某项活动必须以自身任务的完成为先决条件，显然这是荒谬的。因此，若要检测一个工程划分后是否可行，首先就应检查对应的AOV 网是否存在回路。检测的方法是对其 AOV 网进行拓扑排序。

对一个有向图进行拓扑排序的结果会有两种情况：

1. 一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路;
2. 另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。

4. 最短路径算法

狄克斯特拉算法