C语言数据结构算法实现图的遍历

xiaoxiao2021-02-28  9

A 深度优先遍历:

1.深度优先遍历的递归定义

   假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通(从源点可达)的顶点均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。

2 基本思想:

(1)访问顶点v;

(2)从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历;

(3)重复上述两步,直至图中所有和v有路径相通的顶点都被访问到。

3.算法

3-1递归实现

(1)访问顶点v;visited[v]=1;//算法执行前visited[n]=0

(2)w=顶点v的第一个邻接点;

(3)while(w存在) 

           if(w未被访问)

              从顶点w出发递归执行该算法;             w=顶点v的下一个邻接点;

3-2非递归实现

 (1)栈S初始化;visited[n]=0;

 (2)访问顶点v;visited[v]=1;顶点v入栈S

 (3)while(栈S非空)

            x=栈S的顶元素(不出栈);

           if(存在并找到未被访问的x的邻接点w)

                   访问w;visited[w]=1;

                   w进栈;

           else

                    x出栈;

B广度优先遍历

1.广度优先遍历定义

 图的广度优先遍历BFS算法是一个分层搜索的过程,和树的层序遍历算法类同,它也需要一个队列以保持遍历过的顶点顺序,以便按出队的顺序再去访问这些顶点的邻接顶点。

2.基本思想

(1)顶点v入队列。

(2)当队列非空时则继续执行,否则算法结束。

(3)出队列取得队头顶点v;访问顶点v并标记顶点v已被访问。

(4)查找顶点v的第一个邻接顶点col。

(5)若v的邻接顶点col未被访问过的,则col入队列。

(6)继续查找顶点v的另一个新的邻接顶点col,转到步骤(5)。

        直到顶点v的所有未被访问过的邻接点处理完。转到步骤(2)。

3.算法

(1)初始化队列Q;visited[n]=0;

(2)访问顶点v;visited[v]=1;顶点v入队列Q;

(3) while(队列Q非空)  

           v=队列Q的对头元素出队;

           w=顶点v的第一个邻接点;

          while(w存在)

                 如果w未访问,则访问顶点w;

                 visited[w]=1;

                 顶点w入队列Q;

                  w=顶点v的下一个邻接点。

步骤:

1设计一个有向图和一个无向图,

2任选一种存储结构(邻接矩阵或者邻接链表),

3完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。

4进行广度优先遍历分别选择选择循环队列和链表队列。

画出图及其邻接矩阵和邻接表,显示结果截屏。

*选做:非递归深度优先遍历DFS程序DFS1

结果:

1 图遍历程序

// 图的邻接矩阵和邻接链表+队列的循环队列和链表队列

#include"stdio.h"

#include"stdlib.h"

#define MaxVertexNum 100     //定义最大顶点数

#define AL 0

//AL=1 存储结构=邻接矩阵 AL=0 存储结构=邻接表

 

//==========邻接矩阵===========

typedef struct{

   char vexs[MaxVertexNum];        //顶点表

   int edges[MaxVertexNum][MaxVertexNum];  //邻接矩阵,可看作边表

   int n,e;          //图中的顶点数n和边数e

}MGraph;              //用邻接矩阵表示的图的类型

typedef enum{FALSE,TRUE} Boolean;

Boolean visited[MaxVertexNum];

Boolean Visited[MaxVertexNum];

//==========邻接表===========

typedef struct node{       //边表结点

    int adjvex;           //邻接点域

    struct node *next;    //链域

}EdgeNode;

typedef struct vnode{      //顶点表结点

   char vertex;           //顶点域

   EdgeNode *firstedge;   //边表头指针

}VertexNode;

typedef VertexNodeAdjList[MaxVertexNum];         //AdjList是邻接表类型

typedef struct {

   AdjList adjlist;       //邻接表

   int n,e;               //图中当前顶点数和边数

} ALGraph;                 //图类型

//==================循环队列==================

typedef struct {

   int    data[MaxVertexNum];

   int    front, rear;

}Queue;

 

void InitQueue(Queue *Q)//初始化

{   Q->front = Q->rear = 0;   }

 

void EnQueue(Queue *Q, int e)//入队

{

   if ((Q->rear+1)%MaxVertexNum == Q->front)

       return ;

   Q->data[Q->rear] = e;

   Q->rear = (Q->rear+1)%MaxVertexNum;

}

Boolean QueueEmpty(Queue *Q)//判空

{

if (Q->front== Q->rear)

     return TRUE;

else

     return FALSE;

}

 

void DeQueue(Queue *Q, int *e)//出队

{

   if (Q->front == Q->rear)  return ;

   *e = Q->data[Q->front];

   Q->front = (Q->front+1)%MaxVertexNum;

}

//==================链表队列==================

typedef struct QNode

{     intdata;

       structQNode *next;

}QNode,*QueuePtr;

 

typedef struct

{     QueuePtrfront;     //队头指针

       QueuePtrrear;      //队尾指针

}LinkQueue;

 

int InitQueueL(LinkQueue *Q) //构造空队列Q

{     QNode* p;

   p=(QNode *)malloc(sizeof(QNode));

       if(!p) 

return 0;

   Q->front=p;   Q->front->next=NULL;

       Q->rear=p;  Q->rear->next =NULL;

       return1;

}

int EnQueueL(LinkQueue *Q,int e)     //入队:插入e为Q的队尾元素

{     QNode* p;

   p=(QNode *)malloc(sizeof(QNode));

       if(p==NULL)

 return 0;

       p->data=e;p->next=NULL;

       Q->rear->next=p;Q->rear=p;

       return1;

}

 

int DeQueueL(LinkQueue *Q,int *e) //出队:销毁Q的队头元素并用e返回其值

{ if(Q->front==Q->rear)

              return0;

       QueuePtrP=Q->front->next;

       *e=P->data;

       Q->front->next=P->next;

       if(Q->rear==P)

              Q->rear=Q->front;

       free(P);

       return1;

}

 

int GetHeadL(LinkQueue Q,int &e) //用e返回Q的队头元素

{ if(Q.front!=Q.rear)

       {     e=Q.front->next->data;

              return1;

       }

else

              return0;

}

 

Boolean QueueEmptyL(LinkQueue *Q)//判空

{

   if (Q->front == Q->rear)

       return TRUE;

   else

       return FALSE;

}

//=========建立邻接矩阵=======

void CreatMGraph(MGraph *G)

{

  inti,j,k;

 char a[3];

 printf("请输入顶点数和边数n,e: ");

  scanf("%d,%d",&G->n,&G->e);         //输入顶点数和边数

 //G->n=5;G->e=5; //printf("%d:,%d:",G->n,G->e);

 printf("Input Vertex string:\n");

 for(i=0;i<G->n;i++)//scanf("%c",&G->vexs[i]);

 {    printf("%d: ",i);

      scanf("%s",&a);

          G->vexs[i]=a[0];             //读入顶点信息,建立顶点表

     //           G->vexs[i]=i+65;

  }

  printf("\n");

 for(i=0;i<G->n;i++) printf(" %c ",G->vexs[i]);

 printf("\n");

 for(i=0;i<G->n;i++)

      for(j=0;j<G->n;j++)

                     G->edges[i][j]=0;    //初始化邻接矩阵

 printf("Input edges,Creat Adjacency Matrix\n");

 for(k=0;k<G->e;k++)       //读入e条边,建立邻接矩阵

  {scanf("%d,%d",&i,&j);       //输入边(Vi,Vj)的顶点序号

   G->edges[i][j]=1;   

   G->edges[j][i]=1; //若为无向图,矩阵为对称矩阵;若建立有向图,去掉该条语句

  }

 }

 

void CreatMGraph1(MGraph *G)

{     inta[MaxVertexNum]={0,1,1,1,4},b[MaxVertexNum]={1,3,2,3,3};

       G->n=5;  G->e=5;

      for(int i=0;i<G->n;i++)  G->vexs[i]=65+i;

       for(i=0;i<G->n;i++)

           for(int j=0;j<G->n;j++)

                  G->edges[i][j]=0;

       for(i=0;i<G->e;i++)    

       {G->edges[a[i]][b[i]]=1;

         G->edges[b[i]][a[i]]=1;

       }

}void CreatMGraph2(MGraph *G)

{

       intc[5][5]={

    0, 1, 1, 0, 0,

    1, 0, 0, 1, 0,

    1, 0, 0, 0, 0,

    0, 1, 0, 0, 1,

    0, 0, 0, 1, 0};

       G->n=5;  G->e=5;

     for(int i=0;i<G->n;i++)  G->vexs[i]=65+i;

       for(i=0;i<G->n;i++)

           for(int j=0;j<G->n;j++)

                  G->edges[i][j]=c[i][j];

}

//===========显示图的邻接矩阵===============

void showGraph(MGraph *G)

{int i;

//显示图顶点

       for(i=0;i<G->n;i++)

            printf("%c ",G->vexs[i]);

   printf("\n");

//显示图邻接矩阵

   for(i=0;i<G->n;i++)

       {    for(int j=0;j<G->n;j++)

                 printf("%d",G->edges[i][j]);

             printf("\n");

       }

}

//========DFS:深度优先遍历的递归算法邻接矩阵======

void DFS(MGraph *G,int i)  //从第i个顶点开始搜素 对连通子图G邻接矩阵进行DFS搜索

{     visited[i]=TRUE;

   printf(" %c ",G->vexs[i]);

       for(int j = 0; j < G->n; j++)

           if (G->edges[i][j] &&!visited[j])

                     DFS(G,j);

}

 

void DFSM(MGraph *G)  //对G邻接矩阵进行DFS搜索,可以是多个不连通子图

{     for(inti=0;i<G->n;i++) visited[i] = FALSE;

       for(i = 0; i < G->n; i++)

              if(!visited[i])

                     DFS(G,i);

}

//===========访问顶点i入队列Q=======

void visitEnQueue(MGraph *G,Queue *Q,inti)//访问顶点i入队列Q

{

       visited[i]= TRUE; //设置当前顶点访问过

       printf("%c",G->vexs[i]);//打印顶点

       EnQueue(Q,i);       //将此顶点入队列

}

void visitEnQueueL(MGraph *G,LinkQueue*Q,int i)//访问顶点i入队列Q

{

       visited[i]= TRUE; //设置当前顶点访问过

       printf("%c",G->vexs[i]);//打印顶点

       EnQueueL(Q,i);            //将此顶点入队列

}

//===========BFS:广度优先遍历  邻接矩阵=======

void BFS(MGraph *G)// 循环队列

{   inti,j;    QueueQ;

       for(i=0;i<G->n;i++)visited[i] = FALSE;

       InitQueue(&Q);                          //初始化一辅助用的队列

       for(i=0;i<G->n;i++)//对每一个顶点做循环

       {

              if(!visited[i])                //若是未被访问过就处理

              {

                     visitEnQueue(G,&Q,i);//访问顶点i

                     while(!QueueEmpty(&Q))//若当前顶点不为空

                     {

                            DeQueue(&Q,&i); //将队头元素出队并赋给i

                 for(j=0;j<G->n;j++)

                            {                          //判断其他顶点若与当前顶点存在边且未被访问过

                                   if(G->edges[i][j]==1 && !visited[j])

                                      visitEnQueue(G,&Q,j);//访问顶点j

                                   }//for(j=0

                     }//while

              }//if

       }//for(i=0

}

 

void BFS1(MGraph *G) // 链表队列

{   int i,j;     LinkQueueQ;

       for(i=0;i<G->n;i++)visited[i] = FALSE;

       InitQueueL(&Q);                        //初始化一辅助用的队列

       for(i=0;i<G->n;i++)//对每一个顶点做循环

       {

              if(!visited[i])                //若是未被访问过就处理

              {     visitEnQueueL(G,&Q,i);//访问顶点i

                     while(!QueueEmptyL(&Q))//若当前顶点不为空

                     {

                            DeQueueL(&Q,&i);      //将队头元素出队并赋给i

                            for(j=0;j<G->n;j++)

                            {                          //判断其他顶点若与当前顶点存在边且未被访问过

                                   if(G->edges[i][j]==1 && !visited[j])

                                     visitEnQueueL(G,&Q,j);//访问顶点j

                                   }//for(j=0

                     }//while

              }//if

       }//for(i=0

}

//=========显示图的邻接表=======

void showALGraph(ALGraph *G)

{   int i;     EdgeNode *s;

       for(i=0;i<G->n;i++)

       {     printf(" %d:%c",i,G->adjlist[i].vertex+65); 

          for(s=G->adjlist[i].firstedge;s!=NULL;s=s->next)printf(" %d",s->adjvex );

                    printf("\n");

       }

}

//=========建立图的邻接表=======

void CreatALGraph(ALGraph *G)

{

    int i,j,k;

    char a[3];

    EdgeNode *s;           //定义边表结点

    printf("Input VertexNum(n) and EdgesNum(e): ");

    scanf("%d,%d",&G->n,&G->e);       //读入顶点数和边数

    printf("Input Vertex string:\n");

     for(i=0;i<G->n;i++)        

    {   scanf("%s",a);

           G->adjlist[i].vertex=a[0]-65;     //读入顶点信息

              G->adjlist[i].firstedge=NULL;  //边表置为空表

    }

   printf("请输入边,创立邻接表:\n");//printf("\nInput edges,Creat Adjacency List\n");

       for(k=0;k<G->e;k++)         //建立边表

       {scanf("%d,%d",&i,&j);         //读入边(Vi,Vj)的顶点对序号

          s=(EdgeNode *)malloc(sizeof(EdgeNode));    //生成边表结点

          s->adjvex=j;                  //邻接点序号为j

          s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s; //头插入新结点*S Vi的边表

      s=(EdgeNode *)malloc(sizeof(EdgeNode));

      s->adjvex=i;                  //邻接点序号为i

      s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s;//将新结点s插入顶点Vj的边表头部

       }

       showALGraph(G);

}

 

void CreatALGraph1(ALGraph *G)

{

    int i,j,k;

    EdgeNode *s;           //定义边表结点

    G->n=5;G->e=5;  //定义顶点数n和边数e

        for(i=0;i<G->n;i++)        

    {  G->adjlist[i].vertex=i;     //读入顶点信息

              G->adjlist[i].firstedge=NULL;  //边表置为空表

    }

    int c[22]={0,1,2,3,4},b[22]={1,3,3,4,0};

        for(k=0;k<G->e;k++) {        //建立边表

          i=c[k];j=b[k];

          s=(EdgeNode *)malloc(sizeof(EdgeNode));    //生成边表结点

          s->adjvex=j;                  //邻接点序号为j

         s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s; //新结点s头插入Vi的边表

      s=(EdgeNode *)malloc(sizeof(EdgeNode));

      s->adjvex=i;                  //邻接点序号为i

      s->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;//将新结点s头部插入Vj的边表

        }

        showALGraph(G);

}

//========显示访问顶点 邻接表======

void Visit(int w)

{

 printf("%c",w+65);

}

//========DFS:深度优先遍历的递归算法  邻接表======

void DFSMa(ALGraph *G,int i)

{ EdgeNode *p ;

 Visited[i]=TRUE ;

 Visit(G->adjlist[i].vertex);

 p=G->adjlist[i].firstedge;  

 while (p!=NULL)

  {if(!Visited[p->adjvex]) DFSMa(G, p->adjvex);

   p=p->next ;

  }

}

void DFSa(ALGraph *G)//不连通的全部子图

{ int i;

  for(i=0 ;i<G->n ; i++) Visited[i]=FALSE ;  

  for(i=0 ;i<G->n ; i++)

         if (!Visited[i])

                DFSMa(G , i);

}

//==========BFS:广度优先遍历 邻接表=========

void BFSa(ALGraph *G) // 循环队列

{ int k ,v , w ;

 EdgeNode  *p ;

 Queue  *Q;

 Q=(Queue *)malloc(sizeof(Queue)) ;

 Q->front=Q->rear=0 ;  //  建立空队列并初始化

  for(k=0 ; k<G->n ; k++) Visited[k]=FALSE ;  //  访问标志初始化

  for(k=0 ; k<G->n  ; k++)

 {  v=G->adjlist[k].vertex  ; //  单链表的头顶点

    if (!Visited[v])     //   v尚未访问

        { EnQueue(Q,v) ;    //  v入队

      while (!QueueEmpty(Q))//循环直到队空停止

          { DeQueue(Q,&w) ;//出队w

        if(Visited[w]==FALSE)

               { Visited[w]=TRUE ;     //  置访问标志

                 Visit(w);    //  访问队首元素

          p=G->adjlist[w].firstedge;//w第一个弧

          while (p!=NULL) // w所有弧入队

                 { if (!Visited[p->adjvex])

                EnQueue(Q, p->adjvex) ; // 弧入队

            p=p->next; // 下一条弧

                 }

               }  //  end while (p!=NULL

          }  //  end  while 

        }    //end  if 

 }  //  end for 

}

 

void BFSb(ALGraph *G) // 链表队列

{ int k ,v , w ;

EdgeNode *p ;

LinkQueue *Q;

Q=(LinkQueue *)malloc(sizeof(LinkQueue)) ;

QNode * q;

q=(QNode *)malloc(sizeof(QNode));

if(!q) exit(-1) ;

Q->front=q;   Q->front->next=NULL;

Q->rear=Q->front;

//======

 for(k=0 ; k<G->n ; k++) Visited[k]=FALSE ;      //  访问标志初始化

 for(k=0 ; k<G->n  ; k++)

 { v=G->adjlist[k].vertex  ;    //  单链表的头顶点

   if(!Visited[v])     //   v尚未访问

   {  EnQueueL(Q,v) ;    //  v入队

          while (!QueueEmptyL(Q))//循环直到队空停止

          { DeQueueL(Q,&w) ;//出队w

        if(Visited[w]==FALSE)

               { Visited[w]=TRUE ;   //  置访问标志

                 Visit(w);   //  访问队首元素

          p=G->adjlist[w].firstedge;//w第一个弧

          while (p!=NULL) // w所有弧入队

                 { if (!Visited[p->adjvex])

                       EnQueueL(Q, p->adjvex) ; // 弧入队

                   p=p->next; // 下一条弧

                 }// end  while

               }// end  if

          } //  end  while

  }    //  end  if

 } //  end for

}

//==========主程序main=====

void main()

{  

#if AL>0

       charqq[MaxVertexNum];

   MGraph *G;

   G=(MGraph *)malloc(sizeof(MGraph));  //为图G申请内存空间

   printf("\n邻接矩阵: \n");    //存储结构为邻接矩阵

 //CreatMGraph(G);           //建立邻接矩阵1

 //CreatMGraph1(G);          //建立邻接矩阵2

       CreatMGraph2(G);          //建立邻接矩阵3

       showGraph(G);

//=======深度优先遍历图===邻接矩阵========

   printf("\n Print Graph DFS 深度优先遍历: \n  ");    //DFS(G,0);

   DFSM(G);//深度优先遍历

//=======广度优先遍历图===邻接矩阵========

   printf("\n Print Graph BFS广度优先遍历-循环队列: \n  "); BFS(G);//广度优先遍历-循环队列

  //printf("\n Print Graph BFS 广度优先遍历-链队列:\n"); BFS1(G);//广度优先遍历-链队列

       printf("\n");

#else

       charqq[MaxVertexNum];

   ALGraph *G;

   G=(ALGraph *)malloc(sizeof(ALGraph));  //为图G申请内存空间

       printf("\n邻接表: \n");    //存储结构为邻接表

 //  CreatALGraph(G);          //建立邻接表1

    CreatALGraph1(G);   //建立邻接表2

 //   showALGraph(G);

//=======深度优先遍历图===邻接表========

   printf("\n Print Graph DFS 深度优先遍历: \n   ");    //DFS(G,0);

       DFSa(G);//深度优先遍历

//=======广度优先遍历图===邻接表========

   printf("\n Print Graph BFS 广度优先遍历-循环队列: \n   "); BFSa(G); //广度优先遍历-循环队列

  //printf("\n Print Graph BFS 广度优先遍历-链队列:\n"); BFSb(G); //广度优先遍历-链队列

   printf("\n");

#endif

}
转载请注明原文地址: https://www.6miu.com/read-2000044.html

最新回复(0)