C++ 深度优先搜索求图的最长路径

#include<bits/stdc++.h> using namespace std; const int N=1010; int g[N][N],dist,max_d=-10*N,n,m; boolean vis[N]; void dfs(int st){//深度优先搜索 for(int i=1;i<=n;i++){ if(g[st][i]&&!vis[i]){ vis[i]=1; dist+=g[st][i]; dfs(i); dist-=g[st][i];//回溯 } } max_d=max(max_d,dist);//统计最大深度 vis[st]=0; return; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z;//读入边和对应的权值 g[x][y]=z; g[y][x]=z; } for(int i=1;i<=n;i++){ vis[i]=1; dfs(i); memset(vis,0,sizeof(vis));//记得清空标记数组 } cout<<max_d; return 0; }

题目要求找到任意两个节点之间的最长路径，可以使用深度优先搜索来实现。

首先，建立一个邻接矩阵 'g'，表示两个节点之间是否有边以及对应的权值。然后从每个节点开始，对其进行深度优先搜索，并记录搜索的深度 'dist'。当搜索到叶子节点时，将 'dist' 与当前最大深度 'max_d' 进行比较，保存较大值。最终得到的 'max_d' 即为所求的最长路径。

需要注意的是，为了避免重复搜索，需要使用一个标记数组 'vis' 来记录每个节点是否已经被访问过。在每次搜索前将当前节点标记为已访问，搜索结束后将其标记为未访问，然后继续搜索其他未访问的节点。同时，在每次搜索结束后需要对 'dist' 进行回溯，将其减去当前节点的权值，以便搜索其他路径时不会受到影响。

时间复杂度

对于每个节点，最多会遍历一遍整个图，因此总时间复杂度为 O(n^2)。

参考代码