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

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

# C语言数据结构之图的遍历  # C语言树的遍历  # C语言数据结构与算法之图的遍历(二)  # C语言数据结构与算法之图的遍历(一)  # C语言实现图的遍历之深度优先搜索实例  # C语言算法积累图的遍历邻接表简单路径  # 遍历  # 递归  # 是有  # 数据结构  # 希望能  # 谢谢大家  # 为空  # struct  # typedef  # stdlib  # define  # MAX  # char  # data  # firstarc  # nextarc  # ArcNode  # int  # adjvex  # 无环图 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： 如何快速完成中国万网建站详细流程？  中山网站制作网页,中山新生登记系统登记流程？  Laravel怎么进行数据库事务处理_Laravel DB Facade事务操作确保数据一致性  手机怎么制作网站教程步骤,手机怎么做自己的网页链接？  ai格式如何转html_将AI设计稿转换为HTML页面流程【页面】  北京网站制作的公司有哪些,北京白云观官方网站？  Laravel如何配置Horizon来管理队列？（安装和使用）  如何用5美元大硬盘VPS安全高效搭建个人网站？  Laravel如何自定义分页视图？（Pagination示例）  详解Android图表 MPAndroidChart折线图  Windows11怎样设置电源计划_Windows11电源计划调整攻略【指南】  猪八戒网站制作视频,开发一个猪八戒网站，大约需要多少？或者自己请程序员，需要什么程序员，多少程序员能完成？  电视网站制作tvbox接口,云海电视怎样自定义添加电视源？  html5如何实现懒加载图片_ intersectionobserver api用法【教程】  想要更高端的建设网站，这些原则一定要坚持！  手机网站制作与建设方案,手机网站如何建设？  利用JavaScript实现拖拽改变元素大小  Python正则表达式进阶教程_复杂匹配与分组替换解析  如何用西部建站助手快速创建专业网站？  千库网官网入口推荐 千库网设计创意平台入口  Laravel如何创建自定义中间件？（Middleware代码示例）  如何在VPS电脑上快速搭建网站？  Laravel如何构建RESTful API_Laravel标准化API接口开发指南  Laravel如何实现多对多模型关联？（Eloquent教程）  Laravel DB事务怎么使用_Laravel数据库事务回滚操作  Laravel怎么实现模型属性转换Casting_Laravel自动将JSON字段转为数组【技巧】  如何在腾讯云服务器快速搭建个人网站？  Laravel如何与Docker（Sail）协同开发？（环境搭建教程）  Laravel的.env文件有什么用_Laravel环境变量配置与管理详解  如何在浏览器中启用Flash_2025年继续使用Flash Player的方法【过时】  阿里云网站搭建费用解析：服务器价格与建站成本优化指南  Win11怎样安装网易有道词典_Win11安装词典教程【步骤】  Laravel的Blade指令怎么自定义_创建你自己的Laravel Blade Directives  小视频制作网站有哪些,有什么看国内小视频的网站，求推荐？  laravel怎么用DB facade执行原生SQL查询_laravel DB facade原生SQL执行方法  Laravel如何实现文件上传和存储？（本地与S3配置）  Python高阶函数应用_函数作为参数说明【指导】  三星、SK海力士获美批准：可向中国出口芯片制造设备  在线制作视频网站免费,都有哪些好的动漫网站？  lovemo网页版地址 lovemo官网手机登录  如何在云虚拟主机上快速搭建个人网站？  潮流网站制作头像软件下载,适合母子的网名有哪些？  香港服务器网站推广：SEO优化与外贸独立站搭建策略  如何在阿里云域名上完成建站全流程？  如何注册花生壳免费域名并搭建个人网站？  关于BootStrap modal 在IOS9中不能弹出的解决方法(IOS 9 bootstrap modal ios 9 noticework)  jquery插件bootstrapValidator表单验证详解  Laravel怎么进行数据库回滚_Laravel Migration数据库版本控制与回滚操作  如何快速搭建高效简练网站？  Laravel如何创建和注册中间件_Laravel中间件编写与应用流程