No.5.1 图的深度优先遍历

一、要求：找出从节点1到节点5的全部路径和最短路径！

/*有向图的深度优先遍历：打印所有路径，并找出最短路径
#include
struct node{ 　　//记录路径的stack，深度重试的时候，走过的距离也要回收，所以应该把路径也包含在深度搜索的参数里面
　　int x; 　　//点下标
　　int y; 　　//走过的距离
};
struct node s[100],t[100]; 　　// t用来临时存储最短路径，tp是它的头指针
int top=1,tp;

int a[100][100],book[100];
int n,m; 　　//n=city num; m=path num;
int p=5; 　　//distination
int min=10000;
void dfs(int cur,int dis){ 
　　int j,i;
　　//if(dis>min) return;  　　如果寻找的是最短路径，这一步可以节省时间，阻止继续搜索当前路径；但是，我要的是打印所有路径和最短路径
　　if(cur==p){
　　　　if(dis 　　　　{
　　　　　　min=dis;
　　　　　　tp=top;
　　　　　　for(i=1;i 　　　　　　　　t[i]=s[i];
　　　　　　}
　　　　}

　　　　//打印所有路径
　　　　printf("\nFind Path:");
　　　　for(i=1;i 　　　　　　printf("(%d,%d)\t",s[i].x,s[i].y);

　　　　return;
　　}
　　

　　for(j=1;j<=n;j++){
　　　　if(a[cur][j]!=-1 && book[j]==0){ 　　// DFS
　　　　　　book[j]=1;
　　　　　　s[top].x=j;
　　　　　　s[top].y=dis+a[cur][j];
　　　　　　top++;
　　　　　　dfs(j,dis+a[cur][j]);
　　　　　　book[j]=0;
　　　　　　top--;
　　　　}
　　}
　　return;
}

int main(){
　　int i,j,x,y,z;
　　scanf("%d %d",&n,&m);
　　for(i=1;i<=n;i++) //矩阵初始化，不能用这种方式 a[100][100]={-1};
　　　　for(j=1;j<=n;j++)
　　　　{
　　　　　　if(i==j) a[i][j]=0;
　　　　else
　　　　　　a[i][j]=-1;　　//这里用 -1 表示不可达
　　　　}

　　for(i=1;i<=m;i++)
　　{
　　　　scanf("%d %d %d",&x,&y,&z);　　 //这里不能使用i,j，除非在使用前，重新初始化
　　　　a[x][y]=z; 　　　　　　　　　　　 //为何不能直接 &x,&y,&a[x][y]
　　}

　　//// output matrix for debug
　　//for(i=1;i<=n;i++){
　　　　// for(j=1;j<=n;j++){
　　　　　　// printf("%d\t",a[i][j]);
　　　　// }
　　　　// printf("\n");
　　//}

　　book[1]=1;
　　s[top].x=1;s[top].y=0;
　　top++;
　　dfs(1,0);
　　printf("\nMin Path:");
　　for(i=1;i 　　　　printf("(%d,%d)\t",t[i].x,t[i].y);

　　getchar();getchar();return 0;
}
*/

二、记录下小白的DEBUG经历：

1.矩阵初始化的时候，不能用这种方式 a[100][100]={-1}；有向图和无向图有一点区别：矩阵的对称性；

2.输入矩阵元素的时候，&x,&y,&a[x][y]失败；

3.关于图的遍历，如果直接看图1，进行深度遍历，相对来说还简单点；但是图不能直接存储，于是需要转换为图2二维表的形式，这时如果被二维图的下标影响到了，那么恭喜你中了它的陷阱了

4.if(dis>min) return;

三、发散一下思维呗：

1.如果有多条最短路径，如何处理？

　　我觉得，stack t 可以继续入栈，并增加一个倍数变量，实现分段打印多条最短路径。

2.想象一下，假设上面是一台路由器，不知道目标路径，还要考虑网络负载，如何实现？

　　我觉得广度优先搜索更合适。

3.上面的场景也可以尝试一下广度优先搜索算法！