图的DFS与树不一样，树是一对多/一对一，图可以多对一。
第二种方法比较常用
1.求有向图两个点之间的所有可能路径:（BFS版）
V[points][0].num+1作为指向下一个遍历的对象位置。在choose时对下一个已经max的节点.num置为0。choose后非-1非end则push_back，为-1则pop_back回退。
#include <bits/stdc++.h>
using namespace std;
typedef struct{
int num;
// 在BFS中第一列v[i][0].num中作为记录上次遍历的位置
int value;
// 长度等权值
}Node;
#define N 1000
bool isOccupy[N]={false};
// 防回环的临时标记，用于当前BFS前进试错中选中的节点标记，在pop栈后恢复为false。
int choose(vector<vector<Node>>&v,int points){
int i=0;
int choosed=-1;
// 之前遍历结束时v[points][0].num置为满，回退的过程中抑制延伸返回-1，把突出部位回退。
// 但是当从别的路径遍历过来的时候v[points][0].num需要恢复为0。
// 这样的标记设计避免了bool的使用而且记住了上一次操作的位置
for(i=v[points][0].num+1;i<v[points].size();i++){
// 跳过之前遍历过的节点（从0->length遍历，所以i+1就可以跳过之前的所有节点）
if(isOccupy[v[points][i].num]==false){
choosed=v[points][i].num;
// 修改临时占领标记
isOccupy[choosed]=true;
// 标记当前遍历到的节点位置，下一次就从下一个节点开始遍历
v[points][0].num=i;
// 对于需要再遍历的下一个节点，需要把它的内部指针调回0
if(v[choosed][0].num==v[choosed].size()-1)
{
v[choosed][0].num=0;
}
break; //找到第一个就应该跳出循环了
}
}
return choosed;
}
void print(vector<int>s){
int i;
for(i=0;i<s.size();i++){
cout<<">>"<<s[i];
}
cout<<endl;
}
// BFS的栈回退操作
void pop_back(vector<int>&s){
int t=s[s.size()-1];
// cout<<"\n#####pop:"<<t<<endl;
isOccupy[t]=false;
s.pop_back();
}
void BFS_path(vector<vector<Node>>&v,int start,int end){
vector<int>s; // 用stack模拟栈
s.push_back(start);
int path_length=0;
int points,choosed;
// 栈不为空时
while(!s.empty()){
int points=s[s.size()-1];
// 取栈顶元素
choosed=choose(v,points);
//cout<<"\n!!!! choosed:"<<choosed<<endl;
// 在触底的时候
if(choosed==end){
s.push_back(choosed);
print(s);
pop_back(s);
isOccupy[choosed]=false;
}
// 在陷入死胡同的时候就需要回退到正确的路上
else if(choosed==-1){
pop_back(s);
}
// 在未到达终点的时候
else{
s.push_back(choosed);
}
}
}
int main(){
vector<vector<Node>>v;
// 用来存储已占领的节点，用于后面遍历邻接未占领节点
// 第一行废弃，第二行开始第一列用于标记是否后续已占满，只有后面用于记录value边权值还有num后继节点
int edges,i,j,points;
scanf("%d %d",&points,&edges);
// 初始化第一列的链
for(i=0;i<points+1;i++){
vector<Node>vv;
v.push_back(vv);
Node node;
node.num=0;
node.value=0;
v[i].push_back(node);
}
int a,b,value;
for(j=0;j<edges;j++){
scanf("%d %d %d",&a,&b,&value);
Node node;
node.num=b;
node.value=value;
v[a].push_back(node);
}
int start=1;
int end=9;
isOccupy[start]=true;
BFS_path(v,start,end);
}
/*
测试数据1：
7 8
1 2 7
1 4 5
2 3 12
4 5 3
4 6 4
5 7 4
6 7 3
7 3 5
测试数据2：
9 12
1 2 3
1 3 4
1 4 6
2 5 7
3 5 6
4 5 4
5 6 3
5 7 2
5 8 1
6 9 4
7 9 5
8 9 6
*/
测试数据1：
image.png
测试数据2：
image.png
2. 存在相同路径长度下的最短路径( DFS(Dijskla) + BFS ):
这一版加入了vector<vector<int>>parent记录爸爸，然后可以自底向上用DFS遍历所有路径。对相同路径的情况，在遍历的时候对dis[]+v[i][j].value==min的时候将point(爸爸)加入father，在切换最好爸爸的时候vector.clear()，然后在确定真正的爸爸后将所有二爸爸fathers[]加入vector<vector<int>>parent
，其中parent的行数代表儿子的编号，列存储的数字代表儿子对应的爸爸的编号。
#include <bits/stdc++.h>
using namespace std;
typedef struct{
int num; // 在BFS中第一列[0]中作为记录上次遍历的位置
int value; // 长度
int people;
//bool isOccupy;
// 在邻接表中用于避免BFS重复遍历，永久标记。第一列作为完全遍历的标记
}Node;
#define N 1000
vector<vector<Node>>v;
vector<vector<int>>parent;
int points=0; // 记录点数
int dis[N]={0};
bool occupy[N]={0};
// 记录每个点对应的父节点
void record(vector<vector<int>>&v,int father,int son){
v[son].push_back(father);
}
void insert(vector<vector<Node>>&v,int point1,int point2,int length){
Node node;
node.num=point1;
node.value=length;
v[point2].push_back(node);
node.num=point2;
v[point1].push_back(node);
}
int choose(vector<vector<Node>>&v,vector<int>q){
int i,j;
// 选一个非常大的数作为最短路径的初始值
int min_length=100000;
// 天选之子
int choosed=-1;
// 到起始点的最优距离
int distance=0;
// 记录父子关系
int record_father=0;
int record_son=0;
vector<int>fathers;// 这一轮遍历下来你可能会有很多爸爸
for(j=0;j<q.size();j++){
int point=q[j];
for(i=0;i<v[point].size();i++){
if(occupy[v[point][i].num]==false){
// 如果有更短路径，
if(v[point][i].value+dis[point]<min_length){
// 更新最短长度
min_length=v[point][i].value+dis[point];
// 更新当前最优节点
choosed=v[point][i].num;
// 更新到起始点的最短距离
distance=v[point][i].value+dis[point];
// 建立父子关系
record_son=choosed;
record_father=point;
// 改了就不认以前的爸爸们了
fathers.clear();
}
// 对路径长度相同的父节点进行记录，添加到parent中
else if(v[point][i].value+dis[point]==min_length){
// 对于最小距离节点进行切换的情况需要clear,不换的话就把二爸爸三爸爸放fathers[]里存起来
if(v[point][i].num==choosed){
fathers.push_back(point);
}
}
}
}
}
if(choosed!=-1){
// 固定最优距离
dis[choosed]=distance;
// 标记占领
occupy[choosed]=true;
// 把二爸爸们记录在parent[]里面
for(i=0;i<fathers.size();i++){
record(parent,fathers[i],record_son);
}
// 把爸爸记录在parent[]里面
record(parent,record_father,record_son);
}
return choosed;
}
//
void Dijkstra_improve(vector<vector<Node>>&v,int begining,int ending,int numbers){
int i,j;
int choosed;
// 存储已占领节点
vector<int>q;
// 初始化栈
q.push_back(begining);
// 标记占领起点
occupy[begining]=true;
// 当栈没有装满所有节点
while(q.size()!=points){
// 选择一个天选之子
choosed=choose(v,q);
// 选不出来就算了,宣布寻路结束
if(choosed==-1){
break;
}
// 选出来的话就入栈
else{
cout<<">>choosed:"<<choosed<<" \n";
q.push_back(choosed);
}
}
}
// 打印路径
void show(vector<int>&s){
int i;
for(i=s.size()-1;i>=0;i--){
cout<<">>"<<s[i];
}
cout<<endl;
}
int begining=0;
int ending=0;
// 根据parent列表，从end到begin自底向上DFS遍历
void DFS_Path(vector<vector<int>>&parent,vector<int>&s,int start,int& max_group){
// 堆栈用来存储DFS的路径
int i,j;
// 触底
if(start==begining){
max_group++;
return;
}
// 未触底
for(i=0;i<parent[start].size();i++){
s.push_back(parent[start][i]);
DFS_Path(parent,s,parent[start][i],max_group,max_calc);
s.pop_back();
}
}
int main(){
int edges,point;
scanf("%d %d %d %d",&points,&edges,&begining,&ending);
int i,j;
for(i=0;i<points;i++){
dis[i]=0;
scanf("%d",&point);
vector<Node>vv;
v.push_back(vv);
vector<int>p;
parent.push_back(p);
}
int point1,point2,length;
for(i=0;i<edges;i++){
scanf("%d %d %d",&point1,&point2,&length);
Node node;
insert(v,point1,point2,length);
}
// 用于统计急救队的人数
int numbers;
// 使用优化了的Dijkstra获取 fathers[]还有最近路径dis[]
Dijkstra_improve(v,begining,ending,numbers);
cout<<"\nThis is the DFS time to show the path ways......"<<endl;
// 栈递归前的初始化准备,该栈用于存储路径
vector<int>s;
s.push_back(ending);
int max_group=0;
// 统计相同长度的路径数量还有所经过的节点数，在DFS递归的时候统计同长度路径的个数个数
DFS_Path(parent,s,ending,max_group);
cout<<"ending..................\n"<<endl;
cout<<max_group<<" means of same-length path\n"<<endl;
}
/*
9 12 0 8
1 2 1 5 3 1 2 1 5
0 1 3
0 2 4
0 3 6
1 4 7
2 4 6
3 4 4
4 5 3
4 6 2
4 7 1
5 8 4
6 8 5
7 8 6
*/
网友评论