邻接矩阵存储简单路径(1070)

描述

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

input

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

output

输出图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>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
 
#define maxsize 1000
 
vector<int>map[maxsize];
int p[maxsize];
int vis[maxsize];
int start,end;
int n;
 
void init()
{
    memset(p,0,sizeof(p));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)map[i].clear();
    cin>>n>>start>>end;
    int num;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        cin>>num;
        if(num!=0)
        map[i].push_back(j);
    }
     
}
 
void print(int u)
{
    for(int i=0;i<=u;i++)
    {
        cout<<p[i];
    }
    cout<<endl;
}
 
void dfs(int u,int t)
{
    p[t]=u;
    if(u==end)
    {
        print(t);
        return;
    }
     
    vis[u]=1;
    for(int i=0;i<map[u].size();i++)
    {
        int v=map[u][i];
        if(vis[v]==0)dfs(v,t+1);
    }
    vis[u]=0;
}
 
int main()
{
    init();
    dfs(start,0);
    return 0;
 }