问题描述 :

在使用图的邻接表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<class TypeOfVer, class TypeOfEdge>

void adjlist_graph<TypeOfVer, TypeOfEdge>::FindPath(int start, int m);

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

template<class TypeOfVer, class TypeOfEdge>

void adjlist_graph<TypeOfVer, TypeOfEdge>::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 <iostream>
#include <vector>
#include <queue>
using namespace std;

/* 边表的结点定义 */
template<class TypeOfEdge>
struct edgeNode
{
    int data;
    TypeOfEdge weight;
    edgeNode<TypeOfEdge>* next = NULL;
    edgeNode(int d = 0, edgeNode<TypeOfEdge>* ptr = NULL) //构造函数，用于构造其他结点（无权图） 
    {
        next = ptr;
        data = d;
        weight = 0;
    }
    edgeNode(int& d, TypeOfEdge& w, edgeNode<TypeOfEdge>* ptr = NULL) //构造函数，用于构造其他结点（带权图） 
    {
        next = ptr;
        data = d;
        weight = w;
    }
    edgeNode(edgeNode<TypeOfEdge>& temp)
    {
        data = temp.data;
        weight = temp.weight;
        next = NULL;
    }
    int getData() { return data; }  //取得结点的序号（顶点集） 
    TypeOfEdge getWeight() { return weight; }  //取得边集中对应边的权值 
    void SetLink(edgeNode<TypeOfEdge>* link) { next = link; }  //修改结点的next域 
    void SetData(int value) { data = value; }   //修改结点的序号（顶点集） 
    void SetWeight(TypeOfEdge value) { weight = value; }   //修改边集中对应边的权值   
};
template<class TypeOfVer, class TypeOfEdge>
struct verNode
{
    TypeOfVer ver;
    edgeNode<TypeOfEdge>* head;
    verNode(TypeOfVer data)
    {
        ver = data;
        head = new edgeNode<TypeOfEdge>;
    }
    verNode(edgeNode<TypeOfEdge>* h = new edgeNode<TypeOfEdge>) { head = h; }
    TypeOfVer getVer() { return ver; }  //取得结点值（顶点集） 
    edgeNode<TypeOfEdge> getHead() { return head; }  //取得对应的边表的头指针 
    void setVer(TypeOfVer value) { ver = value; }  //设置结点值（顶点集） 
    void setHead(edgeNode<TypeOfEdge> value) { head = value; }  //设置对应的边表的头指针
};

//图的邻接表类
template <class TypeOfVer, class TypeOfEdge>
class adjlist_graph {
private:
    int Vers = 0;           //顶点数 
    int Edges = 0;          //边数 
    vector<verNode<TypeOfVer, TypeOfEdge>> verList;//有头节点
    string GraphKind;     //图的种类标志 
    bool Delete_Edge(int u, int v)
    {
        if (u >= Vers || v >= Vers)return false;
        edgeNode<TypeOfEdge>* p, * q;
        for (p = verList[u].head, q = p->next;q != NULL;p = q, q = q->next)
        {
            if (q->data == v)
            {
                p->next = q->next;
                delete q;
                q = p;
                break;
            }
        }
        if (q == NULL)return false;
        return true;
    }
    void DFS(int u, int& num, vector<bool>& visited) //DFS遍历（递归部分）
    {
        if (num != Vers)cout << "->";
        cout << verList[u].ver;
        if (num == 0)return;
        visited[u] = 1;
        num--;
        if (num == 0)return;
        int v, w;
        GetFirstAdjVex(u, v);
        while (v != -1)
        {
            if (visited[v])
            {
                GetNextAdjVex(u, v, w);
                v = w;
            }
            else DFS(v, num, visited);
        }
    }
    bool CheckRoute(int u, int targe, vector<bool>& visited)//检查两个结点之间是否有路径存在（递归部分，私有成员函数） 
    {
        visited[u] = 1;
        if (visited[targe])return true;
        int v, w;
        GetFirstAdjVex(u, v);
        while (v != -1)
        {
            if (visited[v])
            {
                GetNextAdjVex(u, v, w);
                v = w;
            }
            else CheckRoute(v, targe, visited);
        }
        if (visited[targe])return true;
        else return false;
    }
public:
    //构造函数构造一个只有结点没有边的图。 
    adjlist_graph(string& kd, int vSize, vector<TypeOfVer>& d)
    {
        GraphKind = kd;
        Vers = vSize;
        verList.resize(Vers);
        for (int i = 0;i < Vers;i++)
        {
            verList[i].ver = d[i];
        }
    }
    ////构造函数构造一个无权图。5个参数的含义：图的类型、结点数、边数、结点集和边集 
    adjlist_graph(string& kd, int vSize, int eSize, vector<TypeOfVer>& d, vector<vector<int>>& e)
    {
        GraphKind = kd;
        Vers = vSize;
        Edges = eSize;
        verList.resize(Vers);
        for (int i = 0;i < Vers;i++)
        {
            verList[i].ver = d[i];
        }
        int count = 0;
        for (int i = 0;i < Vers;i++)
        {
            edgeNode<TypeOfEdge>* p, * q;
            for (int j = 0;j < Vers;j++)
            {
                if (e[i][j] == 0)continue;
                p = new edgeNode<TypeOfEdge>;
                p->data = j;
                p->weight = 1;
                p->next = verList[i].head->next;
                verList[i].head->next = p;
                if (GraphKind == "UDG")
                {
                    q = new edgeNode<TypeOfEdge>;
                    q->data = i;
                    q->weight = 1;
                    q->next = verList[j].head->next;
                    verList[j].head->next = q;
                }
            }
        }
    }
    //构造函数构造一个有权图。
    adjlist_graph(string& kd, int vSize, int eSize, vector<TypeOfVer>& d, vector<vector<int>>& e, vector<TypeOfEdge> w)
    {
        GraphKind = kd;
        Vers = vSize;
        Edges = eSize;
        verList.resize(Vers);
        for (int i = 0;i < Vers;i++)
        {
            verList[i].ver = d[i];
        }
        int count = 0;
        for (int i = 0;i < Vers;i++)
        {
            edgeNode<TypeOfEdge>* p, * q;
            for (int j = 0;j < Vers;j++)
            {
                if (e[i][j] != 0)
                {
                    p = new edgeNode<TypeOfEdge>;
                    p->data = j;
                    p->weight = w[count++];
                    p->next = verList[i].head->next;
                    verList[i].head->next = p;
                    if (GraphKind == "UDN")
                    {
                        q = new edgeNode<TypeOfEdge>;
                        q->data = i;
                        q->weight = p->weight;
                        q->next = verList[j].head->next;
                        verList[j].head->next = q;
                    }
                }
            }
        }
    }
    ~adjlist_graph() //析构函数
    {
        edgeNode<TypeOfEdge>* p, * q;
        for (int i = 0;i < Vers;i++)
        {
            for (p = q = verList[i].head;q != NULL;)
            {
                q = q->next;
                delete p;
                p = q;
            }
            delete p;
        }
    }

    bool PrintGraphKind()
    {
        if (Vers == 0)return false;
        cout << GraphKind << endl;
        return true;
    }
    bool PrintVer()  //输出顶点集 
    {
        if (Vers == 0)return false;
        for (int i = 0;i < Vers - 1;i++)
            cout << verList[i].ver << " ";
        cout << verList[Vers - 1].ver << endl;
        return true;
    }
    bool PrintVers()
    {
        if (Vers == 0)return false;
        cout << Vers << endl;
        return true;
    }
    bool PrintEdges()
    {
        if (Vers == 0)return false;
        cout << Edges << endl;
        return true;
    }
    bool PrintAdjList()  //输出邻接矩阵 
    {
        if (Vers == 0)return false;
        if (GraphKind == "DG" || GraphKind == "UDG")
            for (int i = 0;i < Vers;i++)
            {
                cout << verList[i].ver;
                edgeNode<TypeOfEdge>* p;
                for (p = verList[i].head->next;p != NULL;p = p->next)
                {
                    cout << "->" << p->data;
                }
                cout << endl;
            }
        else for (int i = 0;i < Vers;i++)
        {
            cout << verList[i].ver;
            edgeNode<TypeOfEdge>* p;
            for (p = verList[i].head->next;p != NULL;p = p->next)
            {
                cout << "->" << p->data << "(" << p->weight << ")";
            }
            cout << endl;
        }
        return true;
    }

    bool GraphisEmpty() { return Vers == 0; }  //判断图空否
    string GetGraphKind() { return GraphKind; }
    int GetVerNum() { return Vers; }    //取得当前顶点数 
    int GetEdgeNum() { return Edges; }  //取得当前边数 
    bool GetWeight(int u, int v, TypeOfEdge& w)//对于有权图，取两端点为v1和v2的边上的权值。获取成功，返回true；否则，返回false 
    {
        if (u >= Vers || v >= Vers)return false;
        edgeNode<TypeOfEdge>* p = verList[u].head->next;
        while (p)
        {
            if (p->data == v)
            {
                w = p->weight;
                return true;
            }
            p = p->next;
        }
        return false;
    }
    int Get_Degree(int u)//求指定顶点的（出）度（无向图/网：度； 有向图/网：出度 ） 
    {
        if (u >= Vers)return -1;
        edgeNode<TypeOfEdge>* p;
        int count = 0;
        for (p = verList[u].head->next;p != NULL;p = p->next)
            count++;
        return count;
    }
    int Get_InDegree(int u)//求有向图指定顶点的入度 
    {
        if (GraphKind == "UDG" || GraphKind == "UDN")return -1;
        if (u >= Vers)return -1;
        int count = 0;
        for (int i = 0;i < Vers;i++)
        {
            if (i == u)continue;
            edgeNode<TypeOfEdge>* p;
            for (p = verList[i].head->next;p != NULL;p = p->next)
                if (p->data == u)count++;
        }
        return count;
    }

    bool GetVer(int u, TypeOfVer& data) //取得G中指定顶点的值 
    {
        if (u >= Vers)return false;
        data = verList[u].ver;
        return true;
    }
    int GetFirstAdjVex(int u, int& v) //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
    {
        v = -1;
        if (u >= Vers)return v;
        if (verList[u].head->next != NULL)
        {
            v = verList[u].head->next->data;
        }
        return v;
    }
    int GetNextAdjVex(int u, int v, int& w) //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回false
    {
        w = -1;
        if (u >= Vers)return w;
        edgeNode<TypeOfEdge>* p;
        for (p = verList[u].head->next;p != NULL;p = p->next)
        {
            if (p->data == v)
            {
                if (p->next != NULL)
                    w = p->next->data;
                return w;
            }
        }
        return w;
    }
    bool PutVer(int u, TypeOfVer data) //对G中指定顶点赋值 
    {
        if (u >= Vers)return false;
        verList[u].ver = data;
        return true;
    }
    bool InsertVer(TypeOfVer& data) //往G中添加一个顶点 
    {
        verList.push_back(verNode<TypeOfVer, TypeOfEdge>(data));
        Vers++;
        return true;
    }
    int LocateVer(TypeOfVer data) //返回G中指定顶点的位置 
    {
        for (int i = 0;i < Vers;i++)
        {
            if (verList[i].ver == data)return i;
        }
        return -1;
    }
    bool ExistEdge(int u, int v)
    {
        if (u >= Vers || v >= Vers)return false;
        edgeNode<TypeOfEdge>* p = verList[u].head->next;
        while (p)
        {
            if (p->data == v)return true;
            p = p->next;
        }
        return false;
    }
    bool Insert_Edge(int u, int v) //无权图插入一条边
    {
        if (u == v)return false;
        if (u >= Vers || v >= Vers || u < 0 || v < 0)return false;
        edgeNode<TypeOfEdge>* p, * q, * r;
        for (q = verList[u].head, r = q->next;r != NULL;q = r, r = r->next)
        {
            if (r->data == v)return false;
        }
        p = new edgeNode<TypeOfEdge>;
        p->data = v;
        p->weight = 1;
        p->next = verList[u].head->next;
        verList[u].head->next = p;
        if (GraphKind == "UDG" || GraphKind == "UDN")
        {
            p = new edgeNode<TypeOfEdge>;
            p->data = u;
            p->weight = 1;
            p->next = verList[v].head->next;
            verList[v].head->next = p;
        }
        Edges++;
        return true;
    }
    bool Insert_Edge(int u, int v, TypeOfEdge w) //有权图插入一条边
    {
        if (u == v)return false;
        if (u >= Vers || v >= Vers || u < 0 || v < 0)return false;
        edgeNode<TypeOfEdge>* p, * q, * r;
        for (q = verList[u].head, r = q->next;r != NULL;q = r, r = r->next)
        {
            if (r->data == v)return false;
        }
        p = new edgeNode<TypeOfEdge>;
        p->data = v;
        p->weight = w;
        p->next = verList[u].head->next;
        verList[u].head->next = p;
        if (GraphKind == "UDG" || GraphKind == "UDN")
        {
            p = new edgeNode<TypeOfEdge>;
            p->data = u;
            p->weight = w;
            p->next = verList[v].head->next;
            verList[v].head->next = p;
        }
        Edges++;
        return true;
    }
    bool DeleteVer(TypeOfVer& data) //往G中删除一个顶点 
    {
        int n = LocateVer(data);
        if (n != -1)
        {
            Edges++;
            edgeNode<TypeOfEdge>* p, * q;
            for (p = q = verList[n].head;q != NULL;)
            {
                Edges--;
                q = q->next;
                delete p;
                p = q;
            }
            delete p;
            verList.erase(verList.begin() + n);
        }
        else return false;
        Vers--;
        for (int i = 0;i < Vers;i++)
        {
            edgeNode<TypeOfEdge>* p, * q;
            for (p = verList[i].head, q = p->next;q != NULL;p = q, q = q->next)
            {
                if (q->data == n)
                {
                    if (GraphKind != "UDG" && GraphKind != "UDN")
                        Edges--;
                    p->next = q->next;
                    delete q;
                    q = p;
                    continue;
                }
                if (q->data > n)
                    q->data--;
            }
        }
        return true;
    }
    bool DeleteVer(int n) //往G中删除一个顶点 
    {
        if (n < 0 || n >= Vers)return false;
        edgeNode<TypeOfEdge>* p, * q;
        Edges++;
        for (p = q = verList[n].head;q != NULL;)
        {
            Edges--;
            q = q->next;
            delete p;
            p = q;
        }
        delete p;
        verList.erase(verList.begin() + n);
        Vers--;
        for (int i = 0;i < Vers;i++)
        {
            edgeNode<TypeOfEdge>* p, * q;
            for (p = verList[i].head, q = p->next;q != NULL;p = q, q = q->next)
            {
                if (q->data == n)
                {
                    if (GraphKind != "UDG" && GraphKind != "UDN")
                        Edges--;
                    p->next = q->next;
                    delete q;
                    q = p;
                    continue;
                }
                if (q->data > n)
                    q->data--;
            }
        }
        return true;
    }
    bool DeleteEdge(int u, int v) //删除边 (外壳：有向（删除1条边）， 无向（删除2条边））
    {
        if (!Delete_Edge(u, v))return false;
        if (GraphKind == "UDG" || GraphKind == "UDN")
            Delete_Edge(v, u);
        Edges--;
        return true;
    }
    void DFS_Traverse(int u) //DFS遍历（外壳部分）
    {
        if (u >= Vers || u < 0)return;
        vector<bool> visited(Vers, false);
        int num = Vers;
        DFS(u, num, visited);
    }
    void BFS_Traverse(int u) //BFS遍历
    {
        queue<int>q;
        vector<int>visit(Vers, false);
        q.push(u);
        int v, w;
        bool first = true;
        visit[u] = 1;
        while (!q.empty())
        {
            if (!first)cout << "->";
            first = false;
            u = q.front();
            cout << verList[u].ver;
            q.pop();
            GetFirstAdjVex(u, v);
            while (v != -1)
            {
                if (!visit[v])
                {
                    q.push(v);
                    visit[v] = 1;
                }
                GetNextAdjVex(u, v, w);
                v = w;
            }
        }
    }
    bool CheckRoute(int u, int v)//检查两个结点之间是否有路径存在（外壳部分，公有成员函数）  
    {
        if (u >= Vers || v >= Vers)return false;
        vector<bool>visit(Vers);
        return CheckRoute(u, v, visit);
    }

    void FindPath(int start, int m)    //找出从指定结点出发且长度为m的所有简单路径（外壳部分）
    {
        vector<int> visited(Vers, 0);
        vector<int> stack(m + 1);
        stack[0] = start;
        int count = 0;
        visited[start] = 1;
        FindPath(start, m, count, 0, visited, stack);
        cout << count << endl;
    }
    void FindPath(int start, int m, int& count, int top, vector<int>& visited, vector<int>& stack)    //找出从指定结点出发且长度为m的所有简单路径（递归部分）
    {
        if (top == m)
        {
            for (int i = 0;i < m;i++)
                cout << verList[stack[i]].ver << "->";
            cout << verList[stack[m]].ver << endl;
            count++;
            return;
        }
        int u, v, w;
        u = start;
        GetFirstAdjVex(u, v);
        while (v != -1)
        {
            if (!visited[v])
            {
                visited[v] = 1;
                stack[top + 1] = v;
                FindPath(v, m, count, top + 1, visited, stack);
                stack[top + 1] = -1;
                visited[v] = 0;
            }
            GetNextAdjVex(u, v, w);
            v = w;
        }
    }
};

template <class TypeOfVer>
void input(int& vSize, int& eSize, vector<TypeOfVer>& d, vector<vector<int>>& e)
{
    cin >> vSize;
    d.resize(vSize);
    for (int i = 0;i < vSize;i++)
    {
        cin >> d[i];
    }
    cin >> eSize;
    e.resize(vSize);
    for (int i = 0;i < vSize;i++)
        e[i].resize(vSize);
    int a, b;
    for (int i = 0;i < eSize;i++)
    {
        cin >> a >> b;
        e[a][b] = 1;
    }
}

template <class TypeOfVer, class TypeOfEdge>
void input(int& vSize, int& eSize, vector<TypeOfVer>& d, vector<vector<int>>& e, vector<TypeOfEdge>& w)
{
    cin >> vSize;
    d.resize(vSize);
    for (int i = 0;i < vSize;i++)
    {
        cin >> d[i];
    }
    cin >> eSize;
    e.resize(vSize);
    for (int i = 0;i < vSize;i++)
        e[i].resize(vSize);
    int a, b;
    for (int i = 0;i < eSize;i++)
    {
        cin >> a >> b;
        e[a][b] = 1;
    }
    w.resize(eSize);
    for (int i = 0;i < eSize;i++)
        cin >> w[i];
}

template <class TypeOfVer, class TypeOfEdge>
void run(adjlist_graph<TypeOfVer, TypeOfEdge>& list)
{
    int start, m;
    cin >> start >> m;
    list.PrintVer();
    list.PrintAdjList();
    cout << endl;
    list.FindPath(start, m);
}

int main()
{
    typedef string TypeOfVer;
    typedef int TypeOfEdge;
    int vSize = 0, eSize = 0;
    vector<vector<int>>e;
    string str;
    vector<TypeOfVer> d;
    vector<TypeOfEdge>w;
    cin >> str;
    if (str == "DG" || str == "UDG")
    {
        input(vSize, eSize, d, e);//无权图的构造
        adjlist_graph<TypeOfVer, TypeOfEdge> list(str, vSize, eSize, d, e);
        run(list);
    }
    else
    {
        input(vSize, eSize, d, e, w);//有权图的构造
        adjlist_graph<TypeOfVer, TypeOfEdge> list(str, vSize, eSize, d, e, w);
        run(list);
    }
    return 0;
}

OJ测试用例
``
Ex1:

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

Ans1:

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

Ex2:

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

Ans2:

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

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

Ex3:

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
10
2

Ans3:

49 32 50 32 51 32 52 32 53 32 54 32 55 32 56 10
49 45 62 50 45 62 49 10
50 45 62 52 45 62 51 10
51 45 62 54 45 62 53 10
52 45 62 55 10
53 45 62 55 10
54 10
55 10
56 10
10
48

Ex4:

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
20

Ans4:

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

0

微信号公众号搜索：澜莲小哥

个人博客：[澜莲的博客](http://124.223.175.42/)

力扣：https://leetcode-cn.com/u/g-l-/

微博：澜澜沧海水