校园导航程序

题目需求完整代码代码演示过程难点——求无向图中任意两个点之间的所有路径
算法分析（有视频链接）(⊙﹏⊙)用到的结构及相关代码（有改编）
带权重的邻接矩阵邻接表栈核心内容（求所有路径）
（小白的代码，欢迎大神来优化）
题目需求
用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点。存放景点的编号﹑名称﹑简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求实现以下功能:
（1）查询各景点的相关信息
（2）查询图中任意两个景点间的最短路径。
（3）查询图中任意两个景点间的所有路径。
完整代码
#include 
#include 
#include 
using namespace std;

bool isFlag=false;
int choice;

//实验二：校园导航程序
void showMune2();
//定义结构体和变量
const int num=50;
int maxe=30;
int maxl=25662;
int minlist[num];
int minlength=5626;
typedef struct
{    int no;
    char name[100];
    char introduce[500];
}vtype;//顶点类型
typedef struct
{    int edges[num][num];
    int n,e;
    vtype v[num];//存放顶点信息
}matGraph;//邻接矩阵
typedef struct anode
{   int no;
    struct anode * next;
    int weight;
}Arcnode;//邻接表
typedef struct vnode
{    Arcnode *first; }vnode;
typedef struct
{    vnode adjlist[num];
    int n,e;
}adjGraph;
typedef struct linknode
{    int data;
    struct linknode *next;
}stNode;//栈
matGraph m;
adjGraph *G;
stNode *st;

//将所有的景点信息加入
vtype  spot[num]= {{0,"南阳门","南大门"},{1,"冶金广场","广场"},
    {2,"知行园","图书馆,寓意“知行合一、格物致知”..."},
    {3,"文山楼","教学楼"},{4,"阅道楼","教学楼"},
    {5,"三实楼","大学生活动中心：寓意学生的’三实’品质。"},
    {6,"体育馆","内设有练舞房"},{7,"风雨操场","内包括游泳池、排球场、篮球场"},
    {8,"东区运动中心","有足球场、羽毛球场、篮球场、排球场、网球场"},
    {9,"思源阁","寓意饮水思源，清·朱柏庐《治家格言》：一粥一饭，当思来之不易；半丝半缕，恒念物力维艰。"},
    {10,"悯农堂","取自唐朝诗人李绅的《悯农》：锄禾日当午，汗滴禾下土。谁知盘中餐，粒粒皆辛苦。"},
    {11,"碧玉湖","取自唐代诗人贺知章的《咏柳》，碧玉妆成一树高，万条垂下绿丝绦。不知细叶谁裁出，二月春风似剪刀。"},
    {12,"启航会议中心","启航会议中心"},{13,"执中楼","后勤楼，勤政爱民"},{14,"濂溪楼","行政楼，清正廉明"},
    {15,"思源广场","广场"},{16,"西区运动中心","有足球场、羽毛球场、篮球场、排球场、网球场"},
    {17,"金环大道","校区内环道路，金 寓意有色金属。"},{18,"北华门","北大门"}};

//测试数据集
vtype  spot1[7]= {{0,"南阳门","南大门"},{1,"冶金广场","广场"},
    {2,"知行园","图书馆,寓意“知行合一、格物致知”..."},
    {3,"文山楼","教学楼"},{4,"阅道楼","教学楼"},
    {5,"三实楼","大学生活动中心：寓意学生的’三实’品质。"},
    {6,"体育馆","内设有练舞房"}};
//定义方法体：
void showGraph();
void showInfo(int n);
void createMap(matGraph &G,vtype vinfo[],int n);
void showPath();
void createAdj(adjGraph *&G,matGraph m,int n,int e);
void createMap2(matGraph &G,vtype vinfo[],int n);//测试数据图的构建
void showAdj(adjGraph *g);
void getPath(adjGraph *g,stNode *&st,int a,int b);
void initStNode(stNode *&s)
{
    s=(stNode *)malloc(sizeof(stNode));
    s->next=NULL;
}
void push(stNode *&s,int e)
{
    stNode *p;
    p=(stNode *)malloc(sizeof(stNode));
    p->data=e;
    p->next=s->next;
    s->next=p;
}
bool pop(stNode *&s,int &e)
{
    stNode *p;
    if(s->next==NULL)
        return false;
    p=s->next;
    e=p->data;
    s->next=p->next;
    free(p);
    return true;
}


int main()
{

    initStNode(st);
    showMune2();
    return 0;
}
//实验二：校园导航程序
void showMune2()
{
    cout<> n;
        if(n!=5){
            createMap(m,spot,19);
            createAdj(G,m,19,26);
        }
        switch (n)
        {
        case 1:
            showGraph();
            break;
        case 2://2.查询景点相关信息
            int input;
            showGraph();
            cout<<"请输入你要查询的景点编号:";
            cin >> input;
            showInfo(input);
            break;
        case 3://3.查询景点间的距离
            showPath();
            break;
        case 4://4.查询A到B的路径信息
            int A,B;
            cout << "输入A：";cin >> A;cout <> B;cout << endl;
            getPath(G,st,A,B);
            break;
        case 5:
            //测试所有路径
            createMap2(m,spot1,6);
            createAdj(G,m,6,7);
            showAdj(G);
            getPath(G,st,1,5);
            break;
        case 0:
            while(!isFlag){
                    cout << "是否要退出xxxx大学导航系统？（Y/N）"<> a;
                    if(a=='Y'||a=='y'){
                        isFlag = true;
                        break;
                    }else if(a=='N'||a=='n')
                        break;
                    else cout << "输入错误，请重新输入："<adjlist[a].first;
    for(int u=0;uadjlist[st->next->data].first;
        while(p!=NULL)
        {
            if(p->no!=e && s[p->no]==0){
                push(st,p->no);count++;s[p->no]=1;t[count]=p->no;
                e=num;//很重要
                if(p->no==b){
                    int l=0,k;
                    cout <<"通路"<";
                        l=l+m.edges[t[k]][t[k+1]];
                    }
                    if(ladjlist[st->next->data].first;
            }else
                p=p->next;
        }
        pop(st,e);s[e]=0;
        count--;
        if(count==0){
            cout << endl;
            cout <<"最短路径为："<";
            cout << m.v[minlist[i]].name<adjlist[st->next->data].first;
        while(p!=NULL && p->no!=e && enext;
        //return;
    }
}

//画出邻接表
void showAdj(adjGraph *g)
{
    int i;Arcnode * p;
    for(i=0;in;i++)
    {
        p=g->adjlist[i].first;
        cout << i;
        while(p!=NULL)
        {
            cout <<"-->"<< p->no;
            p=p->next;
        }
        cout << endl;
    }
}


//测试图G-------------------------------------------
//设置景点之间的路径长度
void createMap2(matGraph &G,vtype vinfo[],int n)
{
    G.n=n;G.e=maxe;
    for(int i=0;iadjlist[i].first=NULL;
    for(i=0;i=0;j--)
            if(m.edges[i][j]!=0 && m.edges[i][j]!=maxl)
            {
                p=(Arcnode *)malloc(sizeof(Arcnode));
                p->weight=m.edges[i][j];
                p->no=j;
                p->next=G->adjlist[i].first;
                G->adjlist[i].first=p;
            }
    G->n=n;G->e=e;
}

//展示景点的相关信息
void showInfo(int n)
{
    int i=1;
    cout <adjlist[n].first;
    while(p!=NULL)
    {
        cout<< i <<" 距离"<no].name<weight<<"m"<next;
    }
}
void showPath()
{
    int i,j;
    int k=1;
    for(i=0;i"<< j<<" "< 
代码演示过程 

 
 
 
 
  
难点——求无向图中任意两个点之间的所有路径 
 
算法分析（有视频链接） 
以上图为例，对求1到5的所有路径进行算法分析
 视频讲解
  
 
(⊙﹏⊙)用到的结构及相关代码（有改编） 
 
 因为临时改了，便于观看，所以直接运行可能会有一丢丢小错误这里面的对应的不是上图的结构，需要自行输入数据也可以用上面的全部代码里面的数据，呃，在哪里要自己看，应该有注释的 
 
带权重的邻接矩阵 
 
 如图：（25662代表∞，表示两点之间没有边，0代表是自己到自己，先这样说，其他的表示有边，值表示是边的权重）
  
 
int maxl=25662;
typedef struct
{
    int no;//顶点编号
    //下面是顶点的其他信息，根据需求设定
    //char name[100];
    //char introduce[500];
}vtype;//顶点类型
typedef struct
{
    int edges[num][num];//邻接矩阵
    int n,e;
    vtype v[num];//存放顶点信息
}matGraph;

//临时写的
int main()
{
	int n,int e;
	cout << "请输入顶点数" << endl;//（定点编号默认以0~n-1）
	cin >> n;
	cout << "请输入边数"<> e;
	int i,j;
	//设置相关信息
	matGraph m;
	m.n=n;m.e=e;
    for(i=0;i> a;cin >> b;cin >> input;
		G.edges[a-1][b-1]=G.edges[b-1][a-1]=maxl;
	}
}

void showMat(matGraph a)//有点丑的邻接矩阵的输出（可以不需要）
{
    int i,j;
    for(i=0;i 
邻接表 
 
//邻接表
typedef struct anode
{
    int no;
    struct anode * next;
    int weight;
}Arcnode;
typedef struct vnode
{
    Arcnode *first;
}vnode;
typedef struct
{
    vnode adjlist[num];
    int n,e;
}adjGraph;

//创建邻接表
void createAdj(adjGraph *&G,matGraph m,int n,int e)
{
    int i,j;Arcnode *p;
    G=(adjGraph *)malloc(sizeof(adjGraph));
    for(i=0;iadjlist[i].first=NULL;
    for(i=0;i=0;j--)
            if(m.edges[i][j]!=0 && m.edges[i][j]!=maxl)
            {
                p=(Arcnode *)malloc(sizeof(Arcnode));
                p->weight=m.edges[i][j];
                p->no=j;
                p->next=G->adjlist[i].first;
                G->adjlist[i].first=p;
            }
    G->n=n;G->e=e;
}

//显示邻接表（可以省略呐）
void showAdj(adjGraph *g)
{
    int i;Arcnode * p;
    for(i=0;in;i++)
    {
        p=g->adjlist[i].first;
        cout << i;
        while(p!=NULL)
        {
            cout <<"-->"<< p->no;
            p=p->next;
        }
        cout << endl;
    }
}

 
栈 
//栈
typedef struct linknode
{
    int data;
    struct linknode *next;
}stNode;

void initStNode(stNode *&s)
{
    s=(stNode *)malloc(sizeof(stNode));
    s->next=NULL;
}
void push(stNode *&s,int e)
{
    stNode *p;
    p=(stNode *)malloc(sizeof(stNode));
    p->data=e;
    p->next=s->next;
    s->next=p;
}
bool pop(stNode *&s,int &e)
{
    stNode *p;
    if(s->next==NULL)
        return false;
    p=s->next;
    e=p->data;
    s->next=p->next;
    free(p);
    return true;
}
 
核心内容（求所有路径） 
void getPath(adjGraph *g,stNode *&st,int a,int b)
{
    int s[num],t[num],e=num;//e记录出栈的元素,s[]记录访问情况，t[]是要输出的数组
    //因为输出的是路径，是从栈底开始，所以定义一个变量记录栈中的元素情况
    Arcnode * p=g->adjlist[a].first;
    for(int u=0;uadjlist[st->next->data].first;
        while(p!=NULL)
        {
            if(p->no!=e && s[p->no]==0){
                push(st,p->no);count++;s[p->no]=1;t[count]=p->no;
                e=num;//很重要
                if(p->no==b){
                    int l=0,k;
                    cout <<"通路"<";
                        l=l+m.edges[t[k]][t[k+1]];
                    }
                    if(ladjlist[st->next->data].first;
            }else
                p=p->next;
        }
        //p=g->adjlist[st->next->data].first;
        pop(st,e);s[e]=0;
        count--;
        if(count==0){
            cout << endl;
            cout <<"最短路径为："<";
            cout << minlist[i]<adjlist[st->next->data].first;
        while(p!=NULL && p->no!=e && enext;
    }
    //return;
}
校园导航程序

C/C++/C#相关栏目本月热门文章
