2 找出从指定结点出发且长度为m的所有简单路径---来源舒姐

下面是舒姐的csdn

abyssfall的博客_CSDN博客-计科学子的头发账本,代码存档领域博主

在使用图的邻接表ADT的基础上，设计一个算法，按照深度优先搜索的思想找出从指定结点出发且长度为m的所有简单路径。并将此算法加入到邻接表ADT中，在邻接表ADT中提供一个公有的成员函数FindPath(start, m)。

提示：

（1）这个问题相当于从指定结点开始深度优先遍历，而且遍历的深度正好为m。为此，在遍历时需要记住遍历的深度，当深度达到m时，就不需要递归了。此时需要输出这条路径，因此在遍历的过程中还需要记住整条路径。

（2）由于深度优先遍历是用递归实现的，所以FindPath函数最好也设计两个。一个是共有的FindPath函数，供用户使用（外壳）；另一个是私有的FindPath函数，实现递归的遍历。公有的FingPath函数调用私有的FindPath函数找出这些路径。

（3）在调用递归的FindPath函数前，外壳函数还需要做一些辅助工作：

1）要找的是长度为m的简单路径，因此路径上不能有相同的结点，于是定义了一个数组visited记录结点是否在路径上。

2）当路径长度等于m时要输出这条路径，于是定义了一个数组stack保存这条路径。每访问一个结点，都要把结点记录在stack中。

3）递归的FindPath函数有6个参数。第1个参数是遍历的起点的序号；第2个参数是要求的路径长度；第3个参数是符合要求的路径数目；第4个参数是当前路径中的结点数，当前路径的长度是结点数减1；第5个参数是visited数组，记录结点是否在路径上；第6个参数是一个用于记录路径上结点序号的数组，作用和栈类似。

4）调用FindPath函数时要指出从哪一个结点出发，而递归的FingPath函数的参数是起点的序号。递归的FindPath函数首先将起点放入这条路径，并标记这个结点已被访问，然后判断路径长度是否是m。如果长度已达到m，则输出这条路径，并将最后一个结点从路径上删除，返回上一层调用，检查是否还有其它的途径；否则逐个检查起点的后继结点。如果该后继结点没有被访问过，则对该结点调用递归的FindPath函数继续寻找。在所有的后继都检查后，表示这条路径处理完毕。将起始结点从这条路径上删除，返回上一层调用。

参考函数原型：

（1）//找出从指定结点出发且长度为m的所有简单路径（外壳部分） 

template

void adjlist_graph::FindPath(int start, int m);

（2）//找出从指定结点出发且长度为m的所有简单路径（递归部分） 

template

void adjlist_graph::FindPath(int start, int m, int &count, int top, int visited[], int stack[]);

输入说明 :

第一行：图的类型

第二行：结点数

第三行：结点集

第四行：边数

第五行：边集

第六行：起点start

第七行：路径长度m

输出说明 :

第一行：顶点集

第二行：邻接表

空行

如无符合要求的路径：输出 0

否则： 路径输出（一条路径占一行）

           路径数目

输入范例 :

DG
8
1 2 3 4 5 6 7 8
8
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
0
2

输出范例 :

1 2 3 4 5 6 7 8
1->2->1
2->4->3
3->6->5
4->7
5->7
6
7
8

1->3->7
1->3->6
1->2->5
1->2->4
4

#include 
using namespace std;
 
const int MAX = 100;
 
int m = 0;
int arr[MAX][2] = {0};
 
struct E
{
    int num;
    E *next = NULL;
};
 
struct V
{
    string data;
    E *next = NULL;
};
 
struct graph
{
    V m[MAX];
    int number_of_V;
    int number_of_E;
};
 
void creat_no_directioin(graph &g)
{
    int v;
    int f;
    cin >> v;
    g.number_of_V = v;
    for (int i = 0; i < v; i++)
    {
        cin >> g.m[i].data;
    }
    //输入顶点字母
 
    cin >> f;
    g.number_of_E = f;
    for (int i = 0; i < f; i++)
    {
        int v1, v2;
        cin >> v1 >> v2;
        arr[i][0] = v1;
        arr[i][1] = v2;
 
        E *p1 = new E;
        p1->num = v2;
        p1->next = g.m[v1].next;
        g.m[v1].next = p1;
 
        E *p2 = new E;
        p2->num = v1;
        p2->next = g.m[v2].next;
        g.m[v2].next = p2;
    }
}
 
void creat_direction(graph &g)
{
    int e;
    int f;
    cin >> e;
    g.number_of_V = e;
    for (int i = 0; i < e; i++)
    {
        cin >> g.m[i].data;
    }
 
    cin >> f;
    g.number_of_E = f;
    for (int i = 0; i < f; i++)
    {
        int v1, v2;
        cin >> v1 >> v2;
        arr[i][0] = v1;
        arr[i][1] = v2;
        E *p1 = new E;
        p1->num = v2;
        p1->next = g.m[v1].next;
        g.m[v1].next = p1;
    }
}
 
bool index0[MAX] = {false};
 
vector path;   //栈，记录当前路径上的结点
int now_path = 0; //记录总路径数目
 
void DFS(graph &g, int am, int len, int now_len)
{
    index0[am] = true; //标记该点已入选
 
    path.push_back(g.m[am]);
 
    if (now_len == len)
    {
        bool f = false;
        for (int i = 0; i <= len; i++)
        {
            if (f == true)
            {
                cout << "->";
            }
            else
            {
                f = true;
            }
            cout << path[i].data;
        }
        now_path++;
        cout << endl;
    }
 
    else
    {
        E *p = g.m[am].next;
        while (p && now_len < len) //未达目标长度、且还有下个结点
        {
            if (index0[p->num] == 0)
            {
                DFS(g, p->num, len, now_len + 1);
            }
            p = p->next;
        }
    }
 
    path.pop_back();
    index0[am] = false;
}
 
int main()
{
    string kind;
    cin >> kind;
    if (kind == "DG")
    {
        // cout << "DG" << endl;
        graph g;
        creat_direction(g);
 
        int m = 0;
        for (int h = 0; h < g.number_of_V; h++)
        {
            if (m == 1)
            {
                cout << " ";
            }
            m = 1;
            cout << g.m[h].data;
        }
        cout << endl;
 
        for (int u = 0; u < g.number_of_V; u++)
        {
            cout << g.m[u].data;
 
            E *p = g.m[u].next;
            while (p)
            {
                cout << "->";
                cout << p->num;
                p = p->next;
            }
            if (p == NULL)
            {
                cout << endl;
            }
        }
        cout << endl;
 
        int num, len;
        cin >> num >> len;
 
        DFS(g, num, len, 0);
        cout << now_path;
    }
 
    else if (kind == "UDG")
    {
        // cout << "UDG" << endl;
        graph g;
        creat_no_directioin(g);
 
        for (int h = 0; h < g.number_of_V; h++)
        {
            if (m == 1)
            {
                cout << " ";
            }
            m = 1;
            cout << g.m[h].data;
        }
        cout << endl;
        for (int u = 0; u < g.number_of_V; u++)
        {
            cout << g.m[u].data;
 
            E *p = g.m[u].next;
            while (p)
            {
                cout << "->" << p->num;
                p = p->next;
            }
            if (p == NULL)
            {
                cout << endl;
            }
        }
 
        cout << endl;
 
        int num, len;
        cin >> num >> len;
 
        DFS(g, num, len, 0);
        cout << now_path;
    }
 
    getchar();
    getchar();
 
    return 0;
}