这两天打代码主要去搞作业了，结果关于这个作业有点放松了，题没怎么做，课件也就是简单看了看，这个专题还有一阵子，接下来多花点时间好好补一补吧。
关于图的遍历 1.深度优先遍历 深度优先遍历与深搜DFS相似，从一个点A出发，将这个点标为已访问visited[i]:=true;，然后再访问所有与之相连，且未被访问过的点。当A的所有邻接点都被访问过后，再退回到A的上一个点（假设是B），再从B的另一个未被访问的邻接点出发，继续遍历。 参考程序
void dfs(int i) //图用数组模拟邻接表存储，访问点i { visited[i] = true; //标记为已经访问过 for (int j = 1; j <= num[i]; j++) //遍历与i相关联的所有未访问过的顶点 if (!visited[g[i][j]]) dfs(g[i][j]); } int main() { …… memset(visited,false,sizeof(visited)); for (int i = 1; i <= n; i++) //每一个点都作为起点尝试访问，因为不是从任何 //一点开始都能遍历整个图的，例如下面的两个图。 if (!visited[i]) dfs(i); …… return 0; }2.广度优先遍历（不常用，和广搜BFS相似）
最短路径算法 dis[u][v]表示从u到v最短路径长度，w[u][v]表示连接u，v的边的长度。 Floyed-Warshall算法 O(N3) 简称Floyed(弗洛伊德)算法，是最简单的最短路径算法，可以计算图中任意两点间的最短路径。Floyed的时间复杂度是O (N3)，适用于出现负边权的情况。 初始化：点u、v如果有边相连，则dis[u][v]=w[u][v]。 如果不相连则dis[u][v]=0x7fffffff For (k = 1; k <= n; k++) For (i = 1; i <= n; i++) For (j = 1; j <= n; j++) If (dis[i][j] >dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; 算法结束：dis[i][j]得出的就是从i到j的最短路径。
算法变形： 如果是一个没有边权的图，把相连的两点间的距离设为dis[i][j]=true，不相连的两点设为dis[i][j]=false，用Floyed算法的变形： For (k = 1; k <= n; k++) For (i = 1; i <= n; i++) For (j = 1; j <= n; j++) dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]); 用这个办法可以判断一张图中的两点是否相连。
