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; 
} 

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