首页 > 代码库 > 图的深度遍历和广度遍历
图的深度遍历和广度遍历
本文为原创，转载请注明出处：http://blog.csdn.net/j903829182/article/details/38174029
/*
图的遍历方法主要有两种：一种是深度优先遍历，一种是广度优先遍历。图的深度优先遍历类同于树的先根遍历，图的广度遍历类同树的层次遍历
一：连通图的深度优先遍历算法
图的深度优先遍历算法是遍历时深度优先的算法，即在图的所有邻接顶点中，每次都在访问当前顶点后，首先访问当前顶点的
第一个邻接顶点。
连通图的深度优先遍历递归算法如下：
1.访问顶点v并标记顶点v已访问。
2.查找顶点v的第一个邻接顶点w。
3.若顶点v的邻接顶点w存在，则继续执行，否则算法结束。
4.若顶点w尚未被访问，则深度优先遍历递归访问顶点w。
5.查找顶点v的w的邻接顶点的下一个邻接w，转到步骤3
二：连通图的广度优先遍历算法
图的广度优先遍历算法是一个分层搜索的过程，广度优先算法遍历是指，从指定顶点开始，按照到该顶点路径长度由短到长的顺序，访问图
中的其余顶点。
连通图的广度优先遍历算法如下：
1.访问初始顶点v并标记顶点v为已访问.
2.顶点v入队列。
3.若队列非空，则继续执行，否则算法结束
4.出队列取得队头顶点u。
5.查找顶点u的第一个邻接顶点w。
6.若顶点u的邻接顶点w不存在，则转到步骤3，否则循环执行：
a.若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问；
b.顶点w入队列；
c.查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤6
三：非连通图的遍历算法
对于非连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点。但对于非连通图，
从图的任意一个初始顶点开始深度或广度优先遍历，并不能访问图中的所有顶点，此时只能访问和初始顶点连通的那些顶点。
但是，对于非连通图，可以依次把每个顶点都作为一次初始顶点进行深度优先遍历或广度优先遍历，并根据每个顶点的访问标志
来判断该顶点是否已经访问过。若尚未访问过，则访问之，否则跳过该顶点。这样就一定可以访问非连通图中的多有顶点。
*/
//邻接矩阵存储结构下图操作的实现
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100 //定义元素的大小
typedef char DataType; //定义一个类型
#define MaxVertices 10 //定义顶点的最大值
#define MaxWeight 10000 //定义无穷大的具体值
#define MaxQueueSize 15
typedef int DataType1;
typedef struct{
DataType1 queue[MaxQueueSize];
int rear;//队列指针
int front;//对头指针
int count;//计数器
}SeqCQueue;
//初始化
void QueueInitiate(SeqCQueue *q){//初始化顺序循环队列q
q->count=0;//定义初始计数器
q->rear=0;//定义初始队尾指针下标
q->front=0;//定义初始对头指针标
}
//非空
int QueueNotEmpty(SeqCQueue q){
//判断顺序循环队列q非空否，非空则返回1，否则返回0
if(q.count!=0){
return 1;
}else{
return 0;
}
}
//入队列
int QueueAppend(SeqCQueue *q,DataType1 x){
//把数据元素值x插入顺序循环队列q的队尾，成功则返回1，失败返回0
if(q->count>0&&q->rear==q->front){//队满判断
printf("队列已满无法插入!!\n");
return 0;
}else{
q->queue[q->rear]=x;//数据元素x插入队尾
q->rear=(q->rear+1)%MaxQueueSize;//队尾指示器加1
q->count++;//计数器加1
return 1;//返回1
}
}
//出队列
int QueueDelete(SeqCQueue *q,DataType1 *d){
//删除顺序循环队列q的队头元素并赋给d，成功返回1，失败则返回0
if(q->count==0){//对空判断
printf("队列已空无数据元素出队列!!\n");
return 0;
}else{
*d=q->queue[q->front];//取对头元素存入d中
q->front=(q->front+1)%MaxQueueSize;//对头指示器加1
q->count--;//计算器减一
return 1;
}
}
//取对头数据元素
int QueueGet(SeqCQueue q,DataType1 *d){
//取顺序循环队列q的当前对头元素并赋给d，成功则返回1，失败则返回0
if(q.count==0){
printf("队列已空，无数据元素可以取!!\n");
return 0;
}else{
*d=q.queue[q.front];
return 1;
}
}
typedef struct{ //定义一个结构体
DataType list[MaxSize];
int size; //结构体元素的大小
}SeqList; //结构体的对象
typedef struct{
SeqList Vertices;//存放顶点的顺序表
int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵
int numOfEdges;//边的条数
}AdjMGraph;
typedef struct{
int row;//行下标
int col;//列下标
int weight;//权值
}RowColWeight;//边信息结构体
//初始化
void initiate(SeqList *L){
L->size=0;//定义初始化元素个数
}
//求当前元素的个数
int getLength(SeqList L){
return L.size;//返回长度
}
//插入数据元素
int insertData(SeqList *L,int i,DataType x){
//在顺序表L的第i(0<=i<=size)个位置前插入数据元素x
//插入成功返回1，出人失败返回0
int j;
if(L->size>=MaxSize){
printf("顺序表已满，无法插入!!\n");
return 0;
}else if(i<0||i>L->size){
printf("插入的位置不合法，不在指定的范围，参数i不合法!\n");
return 0;
}else{
//从后向前一致移动数据，为插入做准备
for(j=L->size;j>i;j--){
L->list[j]=L->list[j-1];
}
L->list[i]=x;
L->size++;
return 1;
}
}
//删除数据
int deleteData(SeqList *L,int i,DataType *x){
//删除顺序表中位置为i的数据i>=0&&i<=size-1，把数据保存到x中
//删除成功返回1，否则返回0
int j;
if(L->size<=0){
printf("顺序表已空无数据元素可删!\n");
return 0;
}else if(i<0||i>L->size-1){
printf("参数i不合法，不能删除!\n");
return 0;
}else{
*x=L->list[i];
for(j=i+1;j<=L->size-1;j++){//从前往后一次前移
L->list[j-1]=L->list[j];
}
L->size--;//数据元素减一
return 1;
}
}
//取出数据元素
int getData(SeqList L,int i,DataType *x){
if(i<0||i>L.size-1){
printf("参数i不合法，不能删除!\n");
return 0;
}else{
*x=L.list[i];
return 1;
}
}
//初始化有n个顶点的顺序表和邻接矩阵
void InitiateG(AdjMGraph *g,int n){
//初始化
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i==j){
g->edge[i][j]=0;
}else{
g->edge[i][j]=MaxWeight;//MaxWeight表示无穷大
}
}
}
g->numOfEdges=0;//边的条数置为0
initiate(&g->Vertices);//顺序表初始化
}
//插入顶点
void InsertVertex(AdjMGraph *g,DataType vertex){
//在图G中插入顶点vertex
insertData(&g->Vertices,g->Vertices.size,vertex);//顺序表尾插入
}
//插入边
void InsertEdge(AdjMGraph *g,int v1,int v2,int weight){
//在图中插入边<v1,v2>,边<v1,v2>的权为weight
if(v1<0||v1>=g->Vertices.size||v2<0||v2>=g->Vertices.size){
printf("参数v1或v2越界出错!!!\n");
return ;
}
g->edge[v1][v2]=weight;
g->numOfEdges++;
}
//删除边
void DeleteEdge(AdjMGraph *g,int v1,int v2){
//在G图中删除边<v1,v2>
if(v1<0||v1>=g->Vertices.size||v2<0||v2>=g->Vertices.size){
printf("参数v1或v2越界出错!!!\n");
return ;
}
if(g->edge[v1][v2]==MaxWeight||v1==v2){
printf("该边不存在!!!\n");
return;
}
g->edge[v1][v2]=MaxWeight;
g->numOfEdges--;
}
//取第一个邻接顶点
int GetFirstVex(AdjMGraph g,int v){
//在图G中寻找序号为v的顶点的第一个邻接顶点
//如果这样的顶点存在，则返回该邻接顶点的序号，否则返回-1
int col;
if(v<0||v>=g.Vertices.size){
printf("参数v1越界出错!!!\n");
return -1;
}
for(col=0;col<g.Vertices.size;col++){
if(g.edge[v][col]>0&&g.edge[v][col]<MaxWeight){
return col;
}
}
return -1;
}
//取下一个邻接顶点
int GetNextVex(AdjMGraph g,int v1,int v2){
//在图中寻找v1顶点的邻接顶点v2的下一个邻接顶点
//如果这样的邻接顶点存在，则返回该邻接顶点的序号；否则返回-1
//v1和v2都是相应的顶点的序号
int col;
if(v1<0||v1>g.Vertices.size||v2<0||v2>=g.Vertices.size){
printf("参数v1或v2越界出错!!!\n");
return -1;
}
for(col=v2+1;col<g.Vertices.size;col++){
if(g.edge[v1][col]>0&&g.edge[v1][col]<MaxWeight){
return col;
}
}
return -1;
}
void CreatGraph(AdjMGraph *g,DataType V[],int n,RowColWeight E[],int e){
//在图中插入n个顶点信息V和e条边信息E
int i,k;
InitiateG(g,n);//d顶点顺序表初始化
for(i=0;i<n;i++){
InsertVertex(g,V[i]);//插入顶点
}
for(k=0;k<e;k++){
InsertEdge(g,E[k].row,E[k].col,E[k].weight);//插入边
}
}
void Visit(DataType item){//定义访问操作函数
printf("%c ",item);
}
//连通图的深度优先函数
void DepthFSearch(AdjMGraph g,int v,int visited[],
void Visit(DataType item)){
//连通图G以v为初始顶点的访问操作作为Visit()的深度优先遍历
//数组visited标记了相应顶点是否已经访问过，0表示未访问，1表示已经访问
int w;
Visit(g.Vertices.list[v]);//访问顶点v
visited[v]=1;//置已访问标志
w=GetFirstVex(g,v);//取第一个邻接顶点
while(w!=-1){
if(!visited[w]){
DepthFSearch(g,w,visited,Visit);//递归
}
w=GetNextVex(g,v,w);
}
}
//非连通图的深度优先遍历函数
void DepthFirstSearch(AdjMGraph g,void Visit(DataType item)){
//非连通图G的访问操作作为Visit()的深度优先遍历
int i;
int *visited=(int *)malloc(sizeof(int)*g.Vertices.size);
for(i=0;i<g.Vertices.size;i++){
visited[i]=0;//访问标志初始均为0
}
for(i=0;i<g.Vertices.size;i++){
if(!visited[i]){
DepthFSearch(g,i,visited,Visit);//以每个顶点为初始顶点进行调用
}
}
free(visited);
}
//连通图的广度优先遍历函数
void BrodFSearch(AdjMGraph g,int v,int visited[],
void Visit(DataType item)){
//连通图G以v为初始顶点访问操作为Visit广度优先遍历
//数组visited标记了相应顶点是否已访问过，0表示未访问，1表示已访问
DataType1 u,w;
SeqCQueue queue;
Visit(g.Vertices.list[v]);//访问顶点v
visited[v]=1;//置已访问标志
QueueInitiate(&queue);//队列初始化
QueueAppend(&queue,v);//初始顶点v入队列
while(QueueNotEmpty(queue)){
QueueDelete(&queue,&u);//出队列
w=GetFirstVex(g,u);//取顶点u的第一个邻接顶点
while(w!=-1){//邻接顶点w存在时
if(!visited[w]){//若没有访问过
Visit(g.Vertices.list[w]);//访问顶点w
visited[w]=1;//置已访问标志
QueueAppend(&queue,w);//顶点w入队列
}
w=GetNextVex(g,u,w);//取下一个邻接顶点
}
}
}
//非连通图的广度优先遍历函数如下：
void BroadFirstSearch(AdjMGraph g,void Visit(DataType item)){
//非连通图G访问操作为Visit()的广度优先遍历
int i;
int *visited=(int *)malloc(sizeof(int)*g.Vertices.size);
for(i=0;i<g.Vertices.size;i++){
visited[i]=0;//访问标志初始均为0
}
for(i=0;i<g.Vertices.size;i++){
if(!visited[i]){
BrodFSearch(g,i,visited,Visit);//以每一个顶点为初始顶点进行调用
}
}
free(visited);
}
void main(){
AdjMGraph g;
DataType a[]={'A','B','C','D','E'};
RowColWeight rcw[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}};
int n=5,e=5;
int i,j;
CreatGraph(&g,a,n,rcw,e);//创建图
printf("深度优先遍历序列为:");
DepthFirstSearch(g,Visit);
printf("\n广度优先遍历序列为:");
BroadFirstSearch(g,Visit);
printf("\n");
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。