本人在博客园的第一篇题解,日期2022年3月8日晚上7点。
前言:本文适合有一定dfs基础和图论基础的人借鉴。
1.深度优先搜索算法(Deep First Search):
不过度赘述,利用递归调用。下面给出模板。
1 void dfs(参数列表){ 2 //剪枝 3 4 //递归结束 5 6 //递归 7 8 }
2.题目:(P3371 【模板】单源最短路径(弱化版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
本题中,dfs核心代码如下:
1 void dfs(int cur,int des,int sum){ 2 //剪枝 3 if(sum>=minSum[des])return; 4 //找到目标点,结束递归 5 if(cur==des){ 6 minSum[des]=sum;//更新新小值 7 return; 8 } 9 //递归 10 for(int i=1;i<=n;i++){ 11 if( edge[cur][i]==-1)continue; 12 dfs(i,des,sum+edge[cur][i]); 13 } 14 }
其中,cur表示当前到达的元素,des表示终点元素,sum表示当前已经累计的合。
minSum[des]表示从s到当前终点的最短路径权值合。
剪枝部分:已经累积的合已然超过了之前搜索到的最小值,直接结束递归。
当cur==des,也就是找到终点元素,当前路径打通,结束递归,并且一定此时有sum<minSum[des]。
这里的edge[A][B]的值,表示从A->B路径的权值。
3.下面给出完整代码:
1 /*** 2 3 ***/ 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 //点,边,出发点 8 // m 行 u v w 9 // u->v权值w 10 const int Max=20; 11 const int Inf=2147483647; 12 int n,m,s; 13 int edge[Max][Max]; 14 int minSum[Max]; 15 void dfs(int cur,int des,int sum){ 16 //剪枝 17 if(sum>=minSum[des])return; 18 //找到目标点,结束递归 19 if(cur==des){ 20 minSum[des]=sum;//更新新小值 21 return; 22 } 23 //递归 24 for(int i=1;i<=n;i++){ 25 if( edge[cur][i]==-1)continue; 26 dfs(i,des,sum+edge[cur][i]); 27 } 28 } 29 int main() { 30 cin>>n>>m>>s; 31 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)edge[i][j]=-1; //初始化邻接矩阵 32 while(m--){ 33 int u,v,w; 34 cin>>u>>v>>w; 35 edge[u][v]=w; 36 } 37 fill(minSum+1,minSum+n+1,Inf); 38 for(int i=1;i<=n;i++){ 39 dfs(s,i,0); 40 cout<<minSum[i]<<" "; 41 } 42 return 0; 43 } 44 45 46
其中,edge邻接矩阵需要初始化,-1表示不连通。
fill()语句语法:fill(填充起始地址,结束地址,填充值);
用来把数组整体赋值为一个非0值。
值得注意的是,当数据过大时,会出现stack overflow错误!栈溢出。
解决办法:换其他算法,待更新。