深度优先遍历图的方法是，从图中某顶点v出发：
??a.访问顶点v；
??b.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
??c.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
bool visited(MAX_VERTEX_NUM); //访问标记数组
void DFSTraverse(Graph G) { //对图G进行深度优先遍历
for (v = 0; v < G.vexnum; ++v)
visited[v] = FALSE; //初始化已访问标记数据
for (v = 0; v < G.vexnum; ++v) //本代码中是从v=0开始遍历
if (!visited[v])
DFS(G, v);
}
void DFS(Graph G, int v) { //从顶点v出发，深度优先遍历图G；
visit(v); //访问顶点v
visitd[v] = TRUE; //设已访问标记
for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
if (!visited[w]) { //w为u的尚未访问的邻接顶点
DFS(G, w);
} //if
}
}
广度优先搜索（BFS）
?广度优先搜索是按层来处理顶点，距离开始点最近的那些顶点首先被访问，而最远的那些顶点则最后被访问，这个和树的层序变量很像，BFS的代码使用了一个队列。搜索步骤：
??a .首先选择一个顶点作为起始顶点，并将其染成灰色，其余顶点为白色。
??b. 将起始顶点放入队列中。
??c. 从队列首部选出一个顶点，并找出所有与之邻接的顶点，将找到的邻接顶点放入队列尾部，将已访问过顶点涂成黑色，没访问过的顶点是白色。如果顶点的颜色是灰色，表示已经发现并且放入了队列，>如果顶点的颜色是白色，表示还没有发现
??d. 按照同样的方法处理队列中的下一个顶点。
??基本就是出队的顶点变成黑色，在队列里的是灰色，还没入队的是白色。
bool visited(MAX_VERTEX_NUM); //访问标记数组
void BFS(Graph G, int v) { //从顶点v出发，广度优先遍历G
visit(v); //访问初始顶点v
visited[v] = TRUE; //对v做已访问标记
EnQueue(Q, v); //顶点v入队列Q
while (!isEmpty(Q)) {
DeQueue(Q, v); //顶点v出队列
for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
//检测v所有邻接点
if (!visited[w]) { //w为v的尚未访问的邻接顶点
visit(w); //访问顶点w
visited[w] = TRUE; //对w做已访问标记
EnQueue(Q, w); //顶点w入队列
}//if
}
}//while
}
算法特点：
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
算法的思路:
Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。
若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
void Dijkstra(MatGraph g，int v)
{ int dist[MAXV]，path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for (i=0;i<g.n;i++)
{
dist[i]=g.edges[v][i]; //距离初始化
s[i]=0; //s[]置空
if (g.edges[v][i]<INF) //路径初始化
path[i]=v; //顶点v到i有边时
else
path[i]=-1; //顶点v到i没边时
}
s[v]=1; //源点v放入S中
for (i=0;i<g.n;i++) //循环n-1次
{
mindis=INF;
for (j=0;j<g.n;j++)
if (s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=1; //顶点u加入S中
for (j=0;j<g.n;j++) //修改不在s中的顶点的距离
if (s[j]==0)
if (g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
Dispath(dist,path,s,g.n,v); //输出最短路径
}
概述：
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。
该算法是一种在具有正或负边缘权重（但没有负环）的加权图中找到最短路径的>算法，即支持负权值但不支持负权环。
弗洛伊德算法采用的是动态规划思想，其状态转移方程如下：
其中matrix[i,j]表示i到j的最短距离，k是穷举i到j之间可能经过的中间点，当中间点为k时，对整个矩阵即从i到j的路径长度进行更新，对所有可能经过的中间点进行遍历以得到全局最优的最短路径。
算法的单个执行将找到所有顶点对之间的最短路径长度，与迪杰斯特阿拉算法的计算目标有一些差异，迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径，其时间复杂度为O(n3)。
虽然它不返回路径本身的细节，但是可以通过对算法的简单修改来重建路径，我们利用这个思想，通过递归的方式访问每条路径经过的中间节点，对最终的路径进行输出。
void Floyd(MatGraph g) //求每对顶点之间的最短路径
{ int A[MAXVEX][MAXVEX]; //建立A数组
int path[MAXVEX][MAXVEX]; //建立path数组
int i, j, k;
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
{
A[i][j]=g.edges[i][j];
if (i!=j && g.edges[i][j]<INF)
path[i][j]=i; //i和j顶点之间有一条边时
else //i和j顶点之间没有一条边时
path[i][j]=-1;
}
for (k=0;k<g.n;k++) //求Ak[i][j]
{
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
if (A[i][j]>A[i][k]+A[k][j]) //找到更短路径
{
A[i][j]=A[i][k]+A[k][j]; //修改路径长度
path[i][j]=path[k][j]; //修改最短路径为经过顶点k
}
}
（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它。
（2）从图中删去该顶点，并且删去从该顶点发出的全部有向边。
（3）重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。
用一个带权有向图（DAG）描述工程的预计进度。
顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的时间（比如天数）。
图中入度为0的顶点表示工程的开始事件（如开工仪式），出度为0的顶点表示工程结束事件。
从AOE网中源点到汇点的最长路径，具有最大长度的路径叫关键路径。
关键路径是由关键活动构成的，关键路径可能不唯一。
PTA旅游规划问题
原文：https://www.cnblogs.com/Jiegeboke/p/14826638.html