C语言数据结构之图的遍历实例详解

C语言数据结构之图的遍历实例详解

输入一组顶点，建立无向图的邻接矩阵。输入一组顶点，建立有向图的邻接表。分别对无向图和有向图进行DFS（深度优先遍历）和BFS（广度优先遍历）。写出深度优先遍历的递归和非递归算法。根据建立的有向图，判断该图是否是有向无环图，若是，则输出其一种拓扑有序序列。

实现代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX 20 

typedef struct ArcNode{
  int adjvex;
  struct ArcNode *nextarc;
}ArcNode; 

typedef struct{
  char data;
  ArcNode *firstarc;
}AdjList[MAX]; 

typedef struct{
  AdjList vertices;
  int vexnum;
  int arcnum;
}ALGraph; 

typedef struct{
  int *base;
  int front,rear;
}CqQueue; 

void InitQueue(CqQueue &Q)
{//初始化一个队列
  Q.base=(int*)malloc(MAX*sizeof(int));
  Q.front=Q.rear=0;
} 

int QueueEmpty(CqQueue Q)
{//判断队列是否为空
  if(Q.rear==Q.front)
    return 1;
  return 0;
} 

void EnQueue(CqQueue &Q,int e)
{//入队操作
  if((Q.rear+1)%MAX==Q.front)
    return;
  Q.base[Q.rear]=e;
  Q.rear=(Q.rear+1)%MAX;
} 

void DeQueue(CqQueue &Q,int &e)
{//出队操作
  if(Q.rear==Q.front)
    return;
  e=Q.base[Q.front];
  Q.front=(Q.front+1)%MAX;
} 

int LocateVex(ALGraph G,char v)
{//查找顶点v在图G中的位置
  for(int i=0;i<G.vexnum;i++)
    if(G.vertices[i].data==v)
      return i;
  return -1; 

  for(int i=0;i<G.vexnum;i++)
    if(G.vexs[i]==v)
      return i;
  return -1;
} 

void CreateAdjList(ALGraph &G)
{//建立无向图的邻接表
  int v,i,j,k;
  char v1,v2;
  ArcNode *p,*s;
  printf("输入无向图的顶点数和边数：\n");
  scanf("%d%d",&G.vexnum,&G.arcnum);
  getchar();
  printf("输入图的顶点信息：\n");
  for(v=0;v<G.vexnum;v++){
    scanf("%c",&G.vertices[v].data);getchar();
    G.vertices[v].firstarc=NULL;
  } 

  printf("输入无向图的边：\n");
  for(k=0;k<G.vexnum;k++){
    scanf("%c%c",&v1,&v2);
    getchar();
    i=LocateVex(G,v1);
    j=LocateVex(G,v2);
    s=(ArcNode*)malloc(sizeof(ArcNode));
    s->adjvex=j;
    s->nextarc=NULL;
    if(!G.vertices[i].firstarc)
      G.vertices[i].firstarc=s;
    else{
      p=G.vertices[i].firstarc;
      while(p->nextarc)
        p=p->nextarc;
      p->nextarc=s;
    }
    s=(ArcNode*)malloc(sizeof(ArcNode));
    s->adjvex=i;
    s->nextarc=NULL;
    if(!G.vertices[j].firstarc)
      G.vertices[j].firstarc=s;
    else{
      p=G.vertices[j].firstarc;
      while(p->nextarc)
        p=p->nextarc;
      p->nextarc=s;
    }
  }
} 

int visited[MAX]; 

void DFS(ALGraph G,int v)
{//从顶点v开始对图G进行深度优先搜索
  ArcNode *p;
  printf("%3c",G.vertices[v].data);
  visited[v]=1;
  for(p=G.vertices[v].firstarc;p;p=p->nextarc)
    if(!visited[p->adjvex])
      DFS(G,p->adjvex);
} 

void DFSTraverse(ALGraph G)
{//对用邻接表存储的无向图G进行深度优先遍历
  int v;
  for(v=0;v<G.vexnum;v++)
    visited[v]=0;
  for(v=0;v<G.vexnum;v++)
    if(!visited[v])
      DFS(G,v);
} 

void BFSTraverse(ALGraph G)
{//对用邻接表存储的无向图G进行深度优先遍历
  int u,v;
  CqQueue Q;
  ArcNode *p;
  for(v=0;v<G.vexnum;v++)
    visited[v]=0;
  InitQueue(Q);
  for(v=0;v<G.vexnum;v++)
    if(!visited[v]){
      printf("%3c",G.vertices[v].data);
      visited[v]=1;
      EnQueue(Q,v);
      while(!QueueEmpty(Q)){
        DeQueue(Q,u);
        for(p=G.vertices[u].firstarc;p;p=p->nextarc)
          if(!visited[p->adjvex]){
            printf("%3c",G.vertices[p->adjvex].data);
            visited[p->adjvex]=1;
            EnQueue(Q,p->adjvex);
          }
      }
    }
} 

int main(){
  ALGraph G;
  printf("建立无向图的邻接表：\n");
  CreateAdjList(G);
  printf("无向图的深度优先遍历序列如下：\n");
  DFSTraverse(G);
  printf("\n\n无向图的广度优先遍历序列如下：\n");
  BFSTraverse(G);
  printf("\n");
  return 0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！