求图的简单路径和回路

《求图的简单路径和回路》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、求图的简单路径和回路下面是用邻接表存储无向图，然后输出图中指定顶点间的指定长度的简单路径，简单路径就是路径中的顶点不重复，还有一个就是求出图中经过某顶点的回路，都是对图的遍历算法的应用，主要是深度优先的遍历，加上简单的回溯。下面是代码1.//文件"graph.h"  2.  3.#include   4.#include   5.#include   6.using namespace std;  7.  8.bool visited[20];  9.int path[20];  10.  11.struct ArcNode  1

2、2.{  13.    int adjvex;  14.    ArcNode *nextarc;  15.};  16.  17.struct VexNode  18.{  19.    string data;  20.    ArcNode *firstarc;  21.};  22.  23.class NDGraph  24.{  25.private:  26.    VexNode vertices[20];  27.    int vexnum;  28.    int arcnum;  29.public:  30.    NDGraph()  31.    {

3、  32.        vexnum=0;  33.        arcnum=0;  34.    }  35.  36.    int GetVexNum()  1.    {  2.        return vexnum;  3.    }  4.  5.    int Locate_Vex(string v)  6.    {  7.        for(int i=0;i

4、eturn -1;  11.    }  12.  13.    void Create_NDGraph()  14.    {  15.        //构造无向图  16.        string v1,v2;  17.        int i,j,k;  18.        cout<<"输入顶点数和边数：";  19.        cin>>vexnum>>arcnum;  20.        while(vexnum>20)  21.        {  22.            cout<<"请输入少于20个顶点(重新输入顶点数和边数)：";  23

5、.            cin>>vexnum>>arcnum;  24.        }  25.  26.        cout<<"输入顶点名称：";  27.        for(i=0;i>vertices[i].data;  30.            vertices[i].firstarc=NULL;  31.        }  32.  33.        for(k=0;k

6、  cout<<"输入每条边对应的两个顶点：";  36.            cin>>v1>>v2;  37.              38.            i=Locate_Vex(v1);  39.            j=Locate_Vex(v2);  40.  41.            while(i == -1 

7、

8、 j == -1)  42.            {  43.                cout<<"顶点中有不符合要求的，请重新输入：";  44.                cin>>v1>>v2;  1.      

9、          i=Locate_Vex(v1);  2.                j=Locate_Vex(v2);  3.            }  4.  5.            ArcNode *p=new ArcNode;  6.            p->adjvex=j;  7.            p->nextarc=vertices[i].firstarc;  8.            vertices[i].firstarc=p;  9