无向连通图邻接矩阵的创建输出广度深度遍历

源代码：
#include<stdio.h>
#define MaxInt 32767 //表示极大值
#define MVNum 100 //最大顶点数
typedef char VerTexType; //定义数据类型
typedef int ArcType;
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum,arcnum; //图的点数和边数
}AMGraph;
typedef struct
{
char data[MVNum];
int front; //头指针
int rear; //尾指针
}SqQueue;
bool visited[MVNum]; //访问标志数组
int LocateVex(AMGraph G,char v)//确定V在G中的位置
{
int i;
for(i = 0;i < G.vexnum;i++)
{
if(G.vexs[i]==v) //如果找到，返回其序号
break;
}
return i;
}
int CreateUDN(AMGraph &G)
{
int v1,v2,w=1,i,j;
printf(“请输入总顶点数和总边数：”);
scanf("%d %d",&G.vexnum,&G.arcnum);
printf(“请输入点的信息：\n”);
for(i = 0;i < G.vexnum;i++)
scanf(" %c",&G.vexs[i]);
for(i = 0;i < G.vexnum;i++) //初始化邻接矩阵
for(j = 0;j < G.vexnum;j++)
G.arcs[i][j]=0;
for(int k = 0;k < G.arcnum;k++)//构造邻接矩阵
{
printf(“请输入一条边(第%d条边)连接的两个顶点：”,k+1);
scanf(" %c %c",&v1,&v2);//输入一条边依附的顶点
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=w; //设置权值
G.arcs[j][i]=G.arcs[i][j];//根据对称构造另一半
}
return 0;
}
void DisMGraph(AMGraph G)//输出构造的邻接矩阵
{
int i, j;
for(i = 0;i < G.vexnum;i++)
{
for(j = 0;j < G.vexnum;j++)
printf("%5d “,G.arcs[i][j]);
printf(”\n");
}
}
void DFS_AM(AMGraph G,int s)//深度优先搜索遍历
{
int w;
printf("%c ",G.vexs[s]);//输出第s个顶点
visited[s]=true; //设置标志数组值为true
for(w = 0;w < G.vexnum;w++)//依次检查行
{
if((G.arcs[s][w]!=0)&&(!visited[w]))
DFS_AM(G,w); //如果没有被访问，递归调用
}
}

void InitQueue(SqQueue &Q)//队列初始化
{
Q.front=0;
Q.rear=0;
}
bool EnQueue(SqQueue &Q, int e)//入队
{
if( ( Q.rear+1 ) % MVNum == Q.front )//判断队列是否满
return false;
Q.data[Q.rear]=e;
Q.rear = (Q.rear+1)%MVNum;
return true;
}
bool DeQueue(SqQueue &Q,int &e) //出队
{
if( Q.frontQ.rear )
return NULL;
e=Q.data[Q.front];
Q.front=(Q.front+1)%MVNum;
return true;
}
bool QueueEmpty(SqQueue Q) //队列判空
{
return Q.frontQ.rear?true:false;
}
void BFS_AM(AMGraph G,int s) //广度优先搜索遍历
{
int i,j;
int data;
for(i = 0; i < G.vexnum; i++)
visited[i] = false;
printf("%c “,G.vexs[s]);//输出第s个顶点
visited[s]=true; //设置标志数组值为true
SqQueue Q;
InitQueue(Q);
EnQueue(Q,s); //s进队
while(!QueueEmpty(Q))//队列非空
{
DeQueue(Q,data); //队头元素出队并置为data
for(i = 0;i < G.vexnum;i++)
{
if(!visited[i])//对未访问的顶点做BFS
{
visited[i] = true;
printf(”%c “,G.vexs[i]);
EnQueue(Q,i);//将此顶点入队
}
}
}
}
int main()
{
char v;
int i;
AMGraph G;
CreateUDN(G);
DisMGraph(G);
printf(“深度优先搜索遍历:\n”);
printf(“请输入开始遍历的顶点：”);
scanf(” %c",&v);
for(i = 0;i < G.vexnum;i++)
{
if(v==G.vexs[i])
break;
}
DFS_AM(G,i);
printf("\n广度优先搜索遍历:\n");
BFS_AM(G,i);
return 0;
}