六十七.深度优先遍历C语言实现（有向图）

#include<stdio.h> int min = 9999999,book[101],n,e[101][101]; //假设9999999为正无穷 void dfs(int cur,int dis) //cur是当前所在的顶点编号，dis是当前已经走过的路程 { int j; if(dis>min) //如果当前走过的路程已经大于之前的最短路，则没必要继续尝试了，立即返回 return ; if(cur == n) //判断是否到达了目标顶点 { if(dis<min) min = dis; //更新最小值 return ; } for(j=1;j<=n;j++) //从顶点1到顶点n依次尝试 { if(e[cur][j] != 99999999 && book[j] == 0) //判断当前顶点cur到顶点j是否有路，并判断顶点j是否在已走过的路径中 { book[j] = 1; //标记城市j已经在路径中 dfs(j,dis+e[cur][j]); //从顶点j在出发，继续寻找目标顶点 book[j] = 0; // 之前一步探索完毕之后，取消对顶点j的标记 } } return ; } int main() { int i,j,m,a,b,c; scanf("%d %d",&n,&m); for(i=1;i<=n;i++) //初始化二维矩阵 for(j=1;j<=n;j++) if(i==j) e[i][j] = 0; else e[i][j] = 9999999; for(i=1;i<=m;i++) //读入顶点之间的路径 { scanf("%d %d %d",&a,&b,&c); //顶点a到b之间有长度c的路径 e[a][b] = c; } book[1] = 1; //标记1号顶点已经在路径中 dfs(1,0); //1表示当前所在的城市编号，0表示当前已经走的路径 printf("%d",min); //打印1号城市到5号城市的最短路径 getchar();getchar(); return 0; }