遍历无向网，执行时出错
编程实现采用邻接矩阵表示法创建一个无向网，在控制台打印出该无向网的邻接矩阵。并用深度优先算法和广度优先算法遍历该无向网。#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;
}
