图的邻接表的深度优先搜索
发布网友
发布时间：2022-04-21 21:57
共1个回答
热心网友
时间：2023-09-11 08:54
int *visited; //存放当前结点是否遍历
typedef int **MGraph;//定义一个二维数组存放邻接矩阵，暂不定义矩阵大小，数据元素类型为整型
//把矩阵看作数组元素是一维数组的一个一维数组
struct ArcNode{ //定义邻接表中的边结点类型
int adjvex; //邻接点位置
int weight; //权值
ArcNode *nextarc; //指向下一个边结点的链域
};
struct VNode{
int data;
ArcNode *nextarc;
};//邻接表表头结点
typedef VNode *adjlist;
//邻接矩阵存储方式
void InitGraph(MGraph &G,int n) //建立n行n列的二维数组
{
G=new int *[n];//分配第一维空间
int i,j;
for(i=0;i<n;i++)
G[i]=new int[n];//分配第二维空间
for(i=0;i<n;i++)
for(j=0;j<n;j++)
G[i][j]=0;//初始情况下没有连接
}
void CreateGraph(MGraph &G,int n){//建立无向图，其它形式的图可以自己建立
int i,j,e;
cout<<"输入无向图中边的总数量";
cin>>e;
cout<<"\n输入每条边的起点和终点序号(注：结点编号范围为0~n-1):\n";
for(int k=1;k<=e;k++){
cout<<"\n第"<<k<<"对边：";
cin>>i>>j;
if(i>n||j>n||i<0||j<0) return;
G[i][j]=G[j][i]=1;}
}
void dfsMGraph(MGraph G,int n,int i)//从第i个顶点开始遍历
{
cout<<i<<"==>";
visited[i]=1;
for(int j=0;j<n;j++)
if(G[i][j]!=0&&!visited[j])
dfsMGraph(G,n,j);
}
void bfsMGraph(MGraph G,int n,int i)//从第i个顶点开始遍历
{
int *q=new int[n];
int front=0,rear=0; //定义一个队列存放当前已被访问，但其邻接点未被访问的结点
cout<<i<<"==>";
visited[i]=1;
q[rear]=i;
rear=(rear+1)%n;//用的是循环队列
while(front!=rear)
{
int k=q[front];
front=(front+1)%n;
for(int j=0;j<n;j++)
{
if(G[k][j]!=0&&!visited[j])
{
cout<<j<<"==>";
visited[j]=true;
q[rear]=j;
rear=(rear+1)%n;
}//end if
}//end for
}// end while
}
//邻接表存储方式
//初始化
void InitAdj(adjlist &G,int n)
{
G=new VNode[n];
for(int i=0;i<n;i++) {G[i].data=i;G[i].nextarc=NULL;}
}
//建立邻接表存储方式的图
void CreateAdj(adjlist &G,int n)
{
int i,j,k,e;
cout<<"输入图的总边数：";
cin>>e;
cout<<"\n输入每条边的起点和终点序号(注：结点编号范围为0~n-1):\n";
for(k=1;k<=e;k++){
cout<<"\n第"<<k<<"对边：";
cin>>i>>j;
if(i>n||j>n||i<0||j<0) return;
//向序号为i的链表中插入一个边结点
ArcNode*p=new ArcNode;
p->adjvex=j;p->weight=1;
p->nextarc=G[i].nextarc;
G[i].nextarc=p;
//向序号为j的链表中插入一个边结点
p=new ArcNode;
p->adjvex=i;p->weight=1;
p->nextarc=G[j].nextarc;
G[j].nextarc=p;
}
}
//深度遍历邻接表
void dfsAdj(adjlist G,int n,int i)
{
cout<<i<<"==>";
visited[i]=true;
ArcNode *p=G[i].nextarc;
while(p!=NULL)
{
int j=p->adjvex;
if(!visited[j])
dfsAdj(G,n,j);
p=p->nextarc;
}
}
//广度遍历邻接表
void bfsAdj(adjlist G,int n,int i)
{
int *q=new int[n];
int front=0,rear=0; //定义一个队列存放当前已被访问，但其邻接点未被访问的结点
cout<<i<<"==>";
visited[i]=1;
q[rear]=i;
rear=(rear+1)%n;//用的是循环队列
while(front!=rear)
{
int k=q[front];
front=(front+1)%n;
ArcNode *p=G[k].nextarc;
//cout<<"p->adjvex"<<p->adjvex<<endl;
while(p)
{
int j=p->adjvex;
// cout<<"j="<<j<<endl;
if(!visited[j])
{
cout<<j<<"==>";
visited[j]=true;
q[rear]=j;
rear=(rear+1)%n;
}
p=p->nextarc;
}
}// end while
}
//根据邻接矩阵得到图的邻接表
void graphChange(MGraph gm,adjlist ga,int n)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(gm[i][j]!=0)
{
ArcNode *p=new ArcNode;
p->adjvex=j;
p->weight=gm[i][j];
p->nextarc=ga[i].nextarc;
ga[i].nextarc=p;
}
}
//主函数
void main()
{
int i,n,v;MGraph gm;
cout<<"输入图中顶点数量：";
cin>>n;
visited=new int[n];
cout<<"按图的邻接矩阵方式建立图\n";
InitGraph(gm,n);
CreateGraph(gm,n);
//按图的邻接矩阵得到的深度优先遍历
cout<<"输入按图的邻接矩阵遍历的起始顶点：";
cin>>v;
cout<<"按图的邻接矩阵得到的深度优先遍历:"<<endl;
for(i=0;i<n;i++)
visited[i]=0;
cout<<"开始==>";
dfsMGraph(gm,n,v);
cout<<"结束\n";
//按图的邻接矩阵得到的度优先遍历
cout<<"按图的邻接矩阵得到的广度优先遍历:"<<endl;
for(i=0;i<n;i++)
visited[i]=0;
cout<<"开始==>";
bfsMGraph(gm,n,v);
cout<<"结束\n";
adjlist ga;
InitAdj(ga,n);
// cout<<"\n按图的邻接表方式建立图\n";
// CreateAdj(ga,n);
graphChange(gm,ga,n);
//按图的邻接表得到的深度优先遍历
cout<<"输入按图的邻接表遍历的起始顶点：";
cin>>v;
cout<<"按图的邻接表得到的深度优先遍历:"<<endl;
for(i=0;i<n;i++)
visited[i]=0;
cout<<"开始==>";
dfsAdj(ga,n,v);
cout<<"结束\n";
//按图的邻接表得到的度优先遍历
cout<<"按图的邻接表得到的广度优先遍历:"<<endl;
for(i=0;i<n;i++)
visited[i]=0;
cout<<"开始==>";
bfsAdj(ga,n,v);
cout<<"结束\n";
}
