SWUST1070: 邻接矩阵存储简单路径

简介: SWUST1070: 邻接矩阵存储简单路径

题目描述


假设无向图G采用邻接矩阵存储,设计一个算法,输出图G中从顶点u到v的所有简单路径。


输入

简单路径是指路径上的顶点不重复。第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),第二行表示顶点u和v的编号,接下来是为一个n*n大小的矩阵,表示图的邻接关系。数字为0表示不邻接,1表示不邻接。

输出

输出图G中从顶点u到v的所有简单路径。


样例输入

5

0 3

0 1 0 1 1

1 0 1 1 0

0 1 0 1 1

1 1 1 0 1

1 0 1 1 0


样例输出

0123

01243

013

03

04213

0423

043


#include <iostream>
using namespace std;
int n;
int start,last;
const int N = 1010;
int st[N], path[N];
int g[N][N];
void dfs(int u, int t)
{
  path[t] = u;
  if(u == last){
    for(int i = 0; i < t; i++){
      cout<<path[i];
    }
    cout<<last<<endl;
    return;
  }
  st[u] = 1;
  for(int i = 0; i < n; i++){
    if(st[i] == 0&&g[u][i]==1) dfs(i, t + 1);
  } 
  st[u] = 0;
}
int main()
{
  cin>>n;
  cin>>start>>last;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin>>g[i][j];
    }
  }
  dfs(start, 0);
  return 0;
}


注释版

#include <iostream>
using namespace std;
int n;//点的个数 
int start,last;//表示起点和终点 
const int N = 1010;
int st[N], path[N];//st[N]表示是否遍历过该点,path[N]存储路径 
int g[N][N];//存地图 
void dfs(int u, int t)
{
  //将点存入路径中 
  path[t] = u;
  //如果这个点是终点,输出路径 
  if(u == last){
    for(int i = 0; i < t; i++){
      cout<<path[i];
    }
    cout<<last<<endl;
    return;
  }
  //遍历过的点修改st为1 
  st[u] = 1;
  //如果下个点没有遍历过且与该点连通,继续遍历 
  for(int i = 0; i < n; i++){
    if(st[i] == 0&&g[u][i]==1) dfs(i, t + 1);
  } 
  //回溯过程再次修改为0 
  st[u] = 0;
}
int main()
{
  cin>>n;
  cin>>start>>last;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin>>g[i][j];
    }
  }
  //从起点开始遍历, 0表示第一次 
  dfs(start, 0);
  return 0;
}


目录
相关文章
17_二叉树的所有路径
17_二叉树的所有路径
|
6月前
|
存储
技术心得记录:图的概念和存储(邻接矩阵,邻接表)
技术心得记录:图的概念和存储(邻接矩阵,邻接表)
28 0
|
7月前
|
机器人
动态规划|【路径问题】63.不同路径II
动态规划|【路径问题】63.不同路径II
|
7月前
|
算法 机器人 BI
动态规划|【路径问题】|62.不同路径I
动态规划|【路径问题】|62.不同路径I
|
7月前
|
测试技术
【树】【图论】【树路径】【深度优先搜索】2867. 统计树中的合法路径数目
【树】【图论】【树路径】【深度优先搜索】2867. 统计树中的合法路径数目
|
7月前
|
C++
二叉树的所有路径(C++)
二叉树的所有路径(C++)
59 1
|
7月前
|
存储 机器学习/深度学习 人工智能
无向图的邻接矩阵可用一维数组存储
无向图的邻接矩阵可用一维数组存储
302 0
|
7月前
|
存储 算法 程序员
【算法训练-二叉树 六】【路径和计算】路径总和I、路径总和II、路径总和III、二叉树的最大路径和
【算法训练-二叉树 六】【路径和计算】路径总和I、路径总和II、路径总和III、二叉树的最大路径和
93 0
|
存储 C++
C++二叉树的所有路径
C++二叉树的所有路径
|
存储 算法 Java
计算图中两个顶点的所有路径,你会吗
计算图中两个顶点的所有路径,你会吗
330 0
计算图中两个顶点的所有路径,你会吗