wantingtr 2017-12-07 13:39 采纳率: 50%
浏览 3188

数据结构 图 根据邻接矩阵求两点间的所有路径 用栈的方法程序运行时无反应

 #define maxvex 10
#include <iostream>
#include <stack>
using namespace std;
int visit[maxvex];

typedef char vertextype;//结点数据
typedef struct
{
    vertextype vexs[maxvex];//顶点表
    int arc[maxvex][maxvex];//邻接矩阵
    int numnodes,numedges,direction;//顶点数,边数,方向
}graph;

void creatematrix(graph *g)//邻接矩阵
{
    int i,j;
    vertextype e1,e2;
    cout<<"输入顶点和边数"<<endl;
    cin>>g->numnodes>>g->numedges;
    cout<<"是否为有向图?有向图输入1,无向图输入0"<<endl;
    cin>>g->direction;
    cout<<"输入各个顶点数据"<<endl;
    for(i=0;i<g->numnodes;i++)
        cin>>g->vexs[i];//输入每个节点的字符数据到顶点表 vexs[0]=A
    for(i=0;i<g->numnodes;i++)
    {
        for(int j=0;j<g->numnodes;j++)
            g->arc[i][j]=0;
    }//邻接矩阵初始化
    cout<<"请输入每条边的两个顶点结点"<<endl;
    for(int k=0;k<g->numedges;k++)//输入边数
    {
        cin>>e1>>e2;
        for(i=0;i<g->numnodes;i++)//根据顶点表查找第一个结点
        {
            if(g->vexs[i]==e1)
                break;
        }
        for(j=0;j<g->numnodes;j++)//根据顶点表查找第二个结点
        {
            if(g->vexs[j]==e2)
                break;
        }
        g->arc[i][j]=1;
        if(g->direction==0)
            g->arc[j][i]=g->arc[i][j];//无向图的邻接矩阵对称
    }
    cout<<"邻接矩阵建立完成"<<endl;
    cout<<"邻接矩阵如下"<<endl;
    for(i=0;i<g->numnodes;i++)
    {
        for(j=0;j<g->numnodes;j++)
            cout<<g->arc[i][j];
        cout<<endl;
    }

}

void matrixoutput(graph g)
{
    cout<<"邻接矩阵如下"<<endl;
    for(int i=0;i<g.numnodes;i++)
    {
        for(int j=0;j<g.numnodes;j++)
            cout<<g.arc[i][j];
        cout<<endl;
    }
}

void DFS1(graph g,int i)
{
    visit[i]=true;
    cout<<g.vexs[i]<<" ";//打印顶点
    for(int j=0;j<g.numnodes;j++)//一个连通分量的遍历
        if(g.arc[i][j]==1 && !visit[j])
            DFS1(g,j);
}
//邻接矩阵的深度遍历
void DFS(graph g)
{
    for(int i=0;i<g.numnodes;i++)
        visit[i]=0;//初始所有顶点状态都是未访问过状态
    for(int i=0;i<g.numnodes;i++)//若是连通图,只会执行一次
        if(!visit[i])//对未访问过的顶点调用DFS
            DFS1(g,i);
}
void output(stack<int> s)//打印栈内元素
{
    stack<int> out;
    int e;
    while(!s.empty())
    {
        e=s.top();
        s.pop();
        out.push(e);
    }
    while(!out.empty())
    {
        char b=char(out.top())+65;
        cout<<b<<" ";
        out.pop();
    }
    cout<<endl;
}

void way(graph g,vertextype e1,vertextype e2)
{
    int visit[g.numnodes];
    for(int i=0;i<g.numnodes;i++)
        visit[i]=0;
    stack<int> s;//栈内为顶点数据的整型
    int a=int(e1)-65;//起点
    int b=int(e2)-65;//终点
    s.push(a);
    while(s.top()!=b){
        for(int i=0;i<g.numnodes;i++){
            if(visit[i]=0 && g.arc[s.top()][i]==1){
                s.push(i);
            }
        }

    }
    output(s);
    while(!s.empty()){
        int temp1=s.top();
        s.pop();
        for(int i=0;i<g.numnodes;i++){
            if(visit[i]=0 && g.arc[s.top()][i]==1){
                s.push(i);
            }
        }
        if(s.top()==b)
            output(s);
        visit[temp1]=0;
    }
}


main()
{
    graph g;
    vertextype e1,e2;
    creatematrix(&g);
    cout<<"对邻接矩阵进行深度优先遍历"<<endl;
    DFS(g);
    cout<<endl;
    cout<<"请输入起点和终点"<<endl;
    cin>>e1>>e2;
    way(g,e1,e2);
    system("pause");
}





图片说明

  • 写回答

2条回答 默认 最新

  • wantingtr 2017-12-07 13:41
    关注

    输入起点和终点之后程序就没反应了...头大

    评论

报告相同问题?

悬赏问题

  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀