图的存储与遍历算法-数据结构 第2页
样，也是从初始点Vi出发开始访问，访问初始点，标志其已被访问，并将已访问过的初始点序号i入队。当队列非空时进行循环处理，删除队首元素，第一次执行时k的值为i，即front=(front+1)%MaxLength。然后取Vk邻接表的表头指针int k=q[front]; edgenode* p=GL[k]。当边结点指针p不为空时，通过while（）循环，并以p是否为空为控制条件，依次搜索Vk的每一个结点。若Vj没有被访问过则进行处理。访问完后，将p指向p->next。其中的while循环部分的代码如下：
while(p!=NULL){
//依次搜索Vk的每一个结点
int j=p->adjvex; //Vj为Vk的一个邻接点
if(!visited[j]){ //若Vj没有被访问过则进行处理
cout<<j<<' ';
visited[j]=true;
rear=(rear+1)%MaxLength;
q[rear]=j;
}
p=p->next;
}
这样就可以访问所有结点，完成图的广度优先遍历。
第五章 源代码
程序 图的存储与遍历
头文件 图.h
#ifndef GRAPH_H
#define GRAPH_H
#define MAX_VRTEX_NUM 20
struct edgenode{
int adjvex;
edgenode * next;
}; //定义邻接表的边结点类型
typedef edgenode **adjlist;
//定义邻接表类型
void InitGAdjoin(adjlist &GL,int n);
//初始化图的邻接表
void CreateAdjoin(adjlist &GL,int n,int m);
//建立图的邻接表
void dfsAdjoin(adjlist GL,bool*&visited,int i,int n);
//从初始点出发深度优先搜索由邻接表GL表示的图
void bfsAdjoin(adjlist GL,bool*&visited,int i,int n);
//从初始点出发广度优先搜索由邻接表GL表示的图
#endif
实现文件 图.cpp
#include<iostream.h>
#include<stdio.h>
#include"图.h"
void Check(int n,int& i,int& j);
void InitGAdjoin(adjlist&GL,int n)
//初始化图的邻接表
{
GL=new edgenode*[n];
for(int i=1;i<=n;i++)GL[i]=NULL;
}
void CreateAdjoin(adjlist &GL,int n,int m)
//建立图的邻接表
{
int i,j,k,e;
cout<<"输入图的总边数：";
cin>>e;
if(m==0){
//建立无向图
for(k=0;k<e;k++){
cout<<"输入第"<<k<<"条边的起点和终点序号！"<<endl;
cin>>i>>j;
Check(n,i,j);
edgenode*p=new edgenode;
p->adjvex=j;
p->next=GL[i];
GL[i]=p;
//向序号为i的单链表的表头插入一个边结点
p=new edgenode;
p->adjvex=i;
p->next=GL[j];
GL[j]=p;
//向序号为j的单链表的表头插入一个边结点
}
cout<<endl<<"=============="<<endl;
cout<<"图的邻接表为:"<<endl;
for(i=1;i<=n;i++){
edgenode*p=GL[i];
cout<<i-1<<" |"<<"V"<<i;
for(p=GL[i];p!=NULL;p=p->next)
cout<<"|-|->|"<<p->adjvex;
cout<<"|^|";
cout<<endl;
}
//输出邻接表
}
else if(m==1){//建立有向图
for(k=1;k<=e;k++){
cout<<"输入第"<<k<<"条边的起点和终点序号！"<<endl;
cin>>i>>j;
Check(n,i,j);
//向序号为i的表头插入一个边结点
edgenode*p=new edgenode;
p->adjvex=j;
p->next=GL[i];
GL[i]=p;
www.751com.cn for(p=GL[i];p!=NULL;p=p->next)
cout<<"|-|->|"<<p->adjvex;
cout<<"|^|";
cout<<endl;
}
//输出邻接表
}
}
void dfsAdjoin(adjlist GL,bool*& visited,int i,int n)
//从初始点出发深度优先搜索邻接表 GL表示的图
{
cout<<i<<' ';
visited[i]=true;
edgenode* p=GL[i];
while(p!=NULL){
int j=p->adjvex;
//j为Vi的一个邻接点的序号
if(!visited[j])
dfsAdjoin(GL,visited,j,n);
p=p->next;
//使p指向Vi单链表的下一个边结点
}
}
void bfsAdjoin(adjlist GL,bool*& visited,int i,int n)
//从初始点出发广度优先搜索邻接表 GL表示的图
{
const int MaxLength=30;
int q[MaxLength]={0};上一页 [1] [2] [3] [4] 下一页
图的存储与遍历算法-数据结构 第2页下载如图片无法显示或论文不完整，请联系qq752018766
