| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1344 人关注过本帖
标题:遍历无向网,执行时出错
只看楼主 加入收藏
不二伊人
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2015-10-7
结帖率:66.67%
收藏
已结贴  问题点数:20 回复次数:1 
遍历无向网,执行时出错
编程实现采用邻接矩阵表示法创建一个无向网,在控制台打印出该无向网的邻接矩阵。并用深度优先算法和广度优先算法遍历该无向网。
#include<iostream>
using namespace std;
#define MVNum 100 //最大顶点数
#define MaxInt 32767 //极大值,即∞
#define OK 1
#define OVERFLOW -1
#define ERROR 0
#define MAXQSIZE 100 //队列可能达到的最大长度
typedef int Status;
typedef char VerTexType;//假设顶点的数据类型为char
typedef int ArcType;//假设边的权值类型为int
typedef struct
{
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum,arcnum;//图的当前顶点数和边数
}AMGraph;
int LocateVex(AMGraph G,VerTexType v)
{//确定顶点v在G中的位置
    int i;
    for(i=0;i<G.vexnum;i++)
        if(G.vexs[i]==v)
            return i;
        return -1;
}
Status CreateUDN(AMGraph G)
{//采用邻接矩阵表示法创建无向图
    int i,j,k;
    VerTexType v1,v2;
    ArcType w;
    cout<<"输入总顶点数和总边数"<<endl;
    cin>>G.vexnum>>G.arcnum;//输入总顶点数和总边数
    cout<<"依次输入顶点的信息"<<endl;
    for(i=0;i<G.vexnum;i++)
        cin>>G.vexs[i];//依次输入顶点的信息
    for(i=0;i<G.vexnum;i++)
        for(j=0;j<G.vexnum;j++)
            G.arcs[i][j]=MaxInt;//初始化邻接矩阵,边的权值均置为极大值MaxInt
        for(k=0;k<G.arcnum;k++)//构造邻接矩阵
        {
            cout<<"输入一条边依附的两个顶点及权值"<<endl;
            cin>>v1>>v2>>w;//输入一条边依附的两个顶点及权值
            i=LocateVex(G,v1);//确定v1,v2在G中的位置,即顶点数组下标
            j=LocateVex(G,v2);
            G.arcs[i][j]=w;//边<v1,v2>的权值置为w
            G.arcs[i][j]=G.arcs[j][i];//置<v1,v2>的对称边<v2,v1>的权值为w
        }
        return OK;
}
bool visited[MVNum];//访问标志数,其初始值为false
int FirstAdjVex(AMGraph G,int i)
{//返回第i个顶点的第一个邻接点
    int j;
    for(j=0;j<G.vexnum;j++)
        if((G.arcs[i][j]!=0)&&visited[j]==false)
            return j;
        return -1;
}
int NextAdjVex(AMGraph G,int i,int j)
{//返回第i个顶点相对第j个顶点的下一个邻接点
    int k;
    for(k=j;k<G.vexnum;k++)
        if(G.arcs[i][k]!=0&&visited[j]==false)
            return j;
        return -1;
}
int DFS(AMGraph G,int i)
{//从第i个顶点出发递归地深度遍历图G
    int j;
    cout<<i;
    visited[i]=true;//访问第i个顶点,并置访问数组相应分量值为true
    for(j=FirstAdjVex(G,i);j>=0;j=NextAdjVex(G,i,j))//依次检查i的所有邻接点j
        if(!visited[j])
            DFS(G,j);//对i的尚未访问的邻接顶点j递归调用DFS
        return 0;
}
int DFS_AM(AMGraph G,int i)
{//图G为邻接矩阵类型,从第i个顶点出发深度优先搜索遍历图G
    int j;
    cout<<i;
    visited[i]=true;//访问第i个顶点,并置访问标志数组相应分量为true
    for(j=0;j<G.vexnum;j++)//依次检查邻接矩阵i所在行
        if((G.arcs[i][j]!=0)&&(!visited[j]))
            DFS(G,j);//j是i的邻接点并为访问,则递归调用DFS
        return 0;
}
typedef int QElemType;//队列元素类型
typedef struct
{//队列的顺序存储结构
    QElemType *base;//存储空间的基地址
    int front;//头指针
    int rear;//尾指针
}SqQueue;
Status InitQueue(SqQueue &Q)
{//初始化,构造一个空队列
    Q.base=new QElemType[MAXQSIZE];//为队列分配一个最大容量为MAXQSIZE的数组空间
    if(!Q.base)
        exit(OVERFLOW);//存储分配失败
    Q.front=Q.rear=0;//头指针和尾指针为0,队列为空
    return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)
{//入队,插入元素e为Q的新的队尾元素
    if((Q.rear+1)%MAXQSIZE==Q.front)//尾指针在循环意义上加1后等于头指针,表明队满
        return ERROR;
    Q.base[Q.rear]=e;//新元素插入队尾
    Q.rear=(Q.rear+1)%MAXQSIZE;//队尾指针加1
    return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
{//出队,删除Q的对头元素,用e返回其值
    if(Q.front==Q.rear)
        return ERROR;//队空
    e=Q.base[Q.front+1]%MAXQSIZE;//对头指针加1
    return OK;
}
bool QueueEmpty(SqQueue Q)
{//判断队列是否为空
    if(Q.rear==Q.front)
        return true;
    return false;
}
int BFS(AMGraph G,int i)
{//按广度优先非递归遍历连通图G
    SqQueue Q;
    int j,k;
    cout<<i;
    visited[i]=true;//访问第i个顶点,并置访问标志数组相应分量值为true
    InitQueue(Q);//辅助队列Q初始化,置空
    EnQueue(Q,i);//v入队
    while(!QueueEmpty(Q))
    {
        DeQueue(Q,j);//队头元素出队并置为j
        for(k=FirstAdjVex(G,j);k>=0;k=NextAdjVex(G,j,k))
            if(!visited[k])
            {
                cout<<k;
                visited[k]=true;//访问k,并置访问数组相应分量值为true
                EnQueue(Q,k);//K入队
            }
    }
    return 0;
}
int main()
{
    cout<<"*****采用邻接矩阵表示法创建无向网*****"<<endl;
    AMGraph G;
    CreateUDN(G);//采用邻接矩阵表示法创建无向图
    cout<<endl;
    cout<<"无向图G创建完成!"<<endl<<"**无向网G邻接矩阵如下**"<<endl;
    int m,n;
    for(m=0;m<G.vexnum;m++)//打印无向网邻接矩阵算法
    {
        for(n=0;n<G.vexnum;n++)
        {
            if(n!=G.vexnum-1)
            {
                if(G.arcs[m][n]!=MaxInt)
                    cout<<G.arcs[m][n]<<"\t";
                else
                    cout<<"∞"<<"\t";
            }
            else
            {
                if(G.arcs[m][n]!=MaxInt)
                    cout<<G.arcs[m][n]<<endl;
                else
                    cout<<"∞"<<endl;
            }
        }

    }
    cout<<"*****邻接矩阵法图的深度优先和广度优先遍历搜索*****"<<endl<<"请输入遍历无向图G的起始点:"<<endl;
    VerTexType c;
    cin>>c;
    int i;
    for(i=0;i<G.vexnum;i++)
        if(c==G.vexs[i])
            break;
        cout<<endl;
        while(i>=G.vexnum)
        {
            cout<<"该点不存在,请重新输入!"<<endl<<"请输入遍历连通图的起始点:"<<endl;
            cin>>c;
            for(i=0;i<G.vexnum;i++)
                if(c==G.vexs[i])
                    break;
        }
        cout<<"深度优先搜索遍历无向图G结果:"<<endl;
        DFS_AM(G,i);//以i为顶点开始遍历调用深度遍历函数
        cout<<endl<<"广度优先搜索遍历连通图结果:"<<endl;
        BFS(G,i);//以i为顶点开始遍历调用广度遍历函数
        cout<<endl;
        return 0;
}
搜索更多相关主题的帖子: 控制台 include 
2015-12-20 07:43
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:20 
编译没问题。
不懂无向图,反复输入数据显示该点不存在。楼主应该给几个示范点,然后给出应该达到的结果,或许有大神帮你检查出算法上的错误。

能编个毛线衣吗?
2015-12-20 17:30
快速回复:遍历无向网,执行时出错
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017192 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved