|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include <iostream>
using namespace std;
#define MAXSIZE 100
typedef int ElemType;
typedef char VertexType;
typedef struct MGraph{
VertexType vertex[MAXSIZE];///顶点表
ElemType arc[MAXSIZE][MAXSIZE];///邻接矩阵,可看作边表
ElemType vertexNum, arcNum;///vertexNum是顶点数,arcNum是边数
};
int visited[MAXSIZE];//标记数组
int visited1[MAXSIZE];
void CreateMGraph(MGraph *G){
int i ,j ,k;
cout<<"输入边数和顶点数:";
cin>>G->arcNum>>G->vertexNum;
//输入顶点
cout<<"输入顶点"<<endl;
for(i = 0;i < G->vertexNum;i++)
{
cin>>G->vertex[i];
}
//初始化矩阵
for(i = 0;i < G->vertexNum; i++)
{
for(j = 0; j <G->vertexNum; j++)
{
G->arc[i][j]=0;
}
}
///输入由顶点构成的边
cout<<"请输入与边关联的两个顶点的序号:"<<endl;
for(k = 0;k <G->arcNum;k++)
{
cin>>i>>j;
G->arc[i][j]=1;//有边则赋值为1
G->arc[j][i]=1;
}
cout<<"输出邻接矩阵:"<<endl;
//输出矩阵
for(i = 0;i < G->vertexNum; i++)
{
for(j = 0; j <G->vertexNum; j++)
{
cout<<G->arc[i][j]<<"\t";
}
cout<<endl;
}
}
/// 邻接矩阵的深度递归算法
void DFSTravese(MGraph *G,int v){
int w;
cout<<G->vertex[v]<<"\t";
visited[v]=1;
for(w = 0;w < G->vertexNum; w++)
{
if(G->arc[v][w] == 1 && !visited[w] )
{
DFSTravese(G,w);
}
}
}
///邻接矩阵的深度遍历操作
void DFSTravese(MGraph *G){
int v;
for(v= 0;v < G->vertexNum; v++)
{
visited[v] = 0;
}
for(v =0;v <G->vertexNum; v++)
{
if(!visited[v])
{
DFSTravese(G,v);
}
}
}
///队列的操作
typedef struct Qnode{
ElemType *base;
int front;
int rear;
};
///初始化队列
int InitQueue(Qnode *q){
q->base=new ElemType;
if(!q->base)
{
cout<<"开辟空间失败"<<endl;
}
q->front=q->rear=0;
}
///插入队列
int InsertQueue(Qnode *q,ElemType *e){
if((q->rear+1)%MAXSIZE == q->front)
{
cout<<"队列已满,不能插入"<<endl;
return 0;
}
q->base[q->rear]=*e;
q->rear=(q->rear+1)%MAXSIZE;
}
///删除队列
void DeleteQueue(Qnode *q,ElemType *e){
if((q->front)%MAXSIZE == q->rear)
{
cout<<"队列已空"<<endl;
}
*e=q->base[q->front];
q->front=(q->front+1)%MAXSIZE;
}
///邻接矩阵的广度优先遍历
void BFSTravese(MGraph G,int v){
Qnode q;
int w;
cout<<G.vertex[v]<<"\t";///先将第一个结点输出
visited1[v]=1;
InitQueue(&q);///初始化队列
InsertQueue(&q,&v);///插入队列
while(q.rear != q.front)///只要队列不为空就一直开始出队列
{
DeleteQueue(&q,&v);///删除刚才输出的队列
for(w =0; w <G.vertexNum; w++)
{
if(G.arc[v][w] == 1 && visited1[w] == 0)
{
cout<<G.vertex[w]<<"\t";
visited1[w]=1;
InsertQueue(&q,&w);
//BFSTravese(G,e);
}
}
}
}
int main() {
MGraph G;
CreateMGraph(&G);
cout<<"输出遍历的顶点:"<<endl;
DFSTravese(&G,0);
cout<<endl;
cout<<"输出遍历的顶点:"<<endl;
BFSTravese(G,0);
return 0;
} |
|