图及其应用
第1关：创建采用邻接表存储的无向图
任务描述
本关任务：创建邻接表存储的无向图，并输出图的邻接表。
相关知识
为了完成本关任务，你需要掌握：1.邻接表，2.图的邻接表存储表示。
邻接表
对于图中每个顶点 vi，把所有邻接于 vi的顶点（对有向图是将从vi出发的弧的弧头顶点链接在一起）链接成一个带头结点的单链表，将所有头结点顺序存储在一个一维数组中。 例：下面左图G2对应的邻接表如右边所示。
图的邻接表存储表示
#define MAXVEX 20 /*最大顶点数*/
typedef enum{DG,DN,UDG,UDN} GraphKind; /*有向图，有向网，无向图，无向网*/
typedef struct ENode /*表结点类型*/
{
int adjvex;
struct ENode *nextarc;
int weight;
}ENode;
typedef int VexType;
typedef struct VNode /*头结点类型*/
{
VexType vex;
ENode *firstarc;
}VNode, AdjList[MAXVEX]; /*邻接表类型定义*/
typedef struct
{
AdjList vertices; /*用邻接表存储顶点集合及边集合*/
int vexnum,edgenum;
GraphKind kind;
}ALGraph; /*邻接表存储的图的类型定义*/编程要求
在右侧编辑器中补充代码，完成CreateUDG_ALG函数，以实现图的创建。
测试说明
可在右侧文件夹中查看step1/Main.cpp文件，以便于你的操作。
平台会对你编写的代码进行测试。
输入输出说明： 第一行输入图的类型、图的顶点数和边数。图的类型包括：DG（有向图）,DN（有向网）,UDG（无向图）,UDN（无向网），分别用0-3表示。 第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。 输出邻接表。 如创建图G2，则 测试输入: 2 5 6 //图的类型为2表示UDG，图的顶点数为5，图的边数为6 0 1 0 3 1 2 1 4 2 3 2 4 //输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入
预期输出： 0->3->1 1->4->2->0 2->4->3->1 3->2->0 4->2->1
开始你的任务吧，祝你成功！
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraph.h"
int visited[MAXVEX]; /*设访问标志数组为全局变量*/
void CreateUDG_ALG(ALGraph &g) /*构造无向图的邻接表*/
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
int i,j,k;ENode *p;
//printf("请输入图的类型(0-3表示DG,DN,UDG,UDN)、顶点数、边数：\n");
scanf("%d%d%d",&g.kind,&g.vexnum,&g.edgenum);
for(i=0;i<g.vexnum;i++) /*构造头结点数组*/
{
g.vertices[i].vex=i;
g.vertices[i].firstarc=NULL; /*初始化头结点指针域为空*/
}
//printf("请按顶点编号从小到大的顺序输入各条边的两顶点：\n");
for(k=0;k<g.edgenum;k++) /*构造邻接表*/
{
scanf("%d%d",&i,&j); /*输入一条边所依附的两个顶点的编号*/
/*将顶点Vj插入到第i个单链表的表头，也就是用“头插法”建立一个单链表*/
p=(ENode *)malloc(sizeof(ENode)); /*生成表结点*/
p->adjvex=j; p->weight=0;
p->nextarc=g.vertices[i].firstarc; /*插入表结点*/
g.vertices[i].firstarc=p;
/*将顶点Vi插入到第j个单链表的表头，也就是用“头插法”建立一个单链表*/
p=(ENode *)malloc(sizeof(ENode));
p->adjvex=i; p->weight=0;
p->nextarc=g.vertices[j].firstarc;
g.vertices[j].firstarc=p;
}
/********** End **********/
}
void PrintAdjList(ALGraph g) /*输出邻接表*/
{
int i,w;ENode *p;
for(i=0;i<g.vexnum;i++)
{
printf("%d",g.vertices[i].vex);
p=g.vertices[i].firstarc;
while(p)
{
w=p->adjvex;printf("->%d",w);p=p->nextarc;
}
printf("\n");
}
}第2关：图的深度优先遍历
任务描述
本关任务：图的深度优先遍历。
相关知识
为了完成本关任务，你需要掌握：图的深度优先遍历。
图的深度优先遍历
设初始时，图中所有顶点未曾被访问过： ● 从图中某个顶点 v 出发，访问此顶点； ● 依次从 v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和顶点 v 有路径相通的顶点都被访问到； ● 如果此时图中还有尚未访问的顶点，则另选一个尚未访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 如：下图从V0出发，可以得到一个深度优先遍历序列为{ V0 ,V1 ,V3 ,V7 ,V4 ,V2 ,V5 ,V6 }。
编程要求
在右侧编辑器中补充代码，完成DFS函数，实现图的深度优先遍历。具体要求如下：
* DFS：从未被访问的顶点Vi出发深度优先遍历图。
测试说明
可在右侧文件夹中查看step2/Main.cpp文件，以便于你的操作。
平台会对你编写的代码进行测试。
输入输出说明： 第一行输入图的类型、图的顶点数和边数。 第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。 输出深度优先遍历的结果。 如图G2，
测试输入: 2 5 6 0 1 0 3 1 2 1 4 2 3 2 4
预期输出： 0 3 2 4 1 //深度优先遍历的结果
开始你的任务吧，祝你成功！
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraph.h"
int visited[MAXVEX]; /*设访问标志数组为全局变量*/
void DFSTraverse(ALGraph g)/*深度优先遍历以邻接表存储的图g*/
{
int i;
for(i=0;i<g.vexnum;i++) /*访问标志数组初始化*/
visited[i]=0;
for(i=0;i<g.vexnum;i++)
if(!visited[i]) DFS(g,i); /*对尚未访问的顶点调用DFS函数*/
}
void DFS(ALGraph g, int i)/*从未被访问的顶点Vi出发深度优先遍历图g*/
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
ENode *p;
printf("%d ",g.vertices[i].vex);
visited[i]=1;
p=g.vertices[i].firstarc;
while(p)
{
if(!visited[p->adjvex])
DFS(g,p->adjvex);
p=p->nextarc;
}
/********** End **********/
}
void CreateUDG_ALG(ALGraph &g) /*构造无向图的邻接表*/
{
int i,j,k;ENode *p;
//printf("请输入图的类型(0-3表示DG,DN,UDG,UDN)、顶点数、边数：\n");
scanf("%d%d%d",&g.kind,&g.vexnum,&g.edgenum);
for(i=0;i<g.vexnum;i++) /*构造头结点数组*/
{
g.vertices[i].vex=i;
g.vertices[i].firstarc=NULL; /*初始化头结点指针域为空*/
}
//printf("请按顶点编号从小到大的顺序输入各条边的两顶点：\n");
for(k=0;k<g.edgenum;k++) /*构造邻接表*/
{
scanf("%d%d",&i,&j); /*输入一条边所依附的两个顶点的编号*/
/*将顶点Vj插入到第i个单链表的表头，也就是用“头插法”建立一个单链表*/
p=(ENode *)malloc(sizeof(ENode)); /*生成表结点*/
p->adjvex=j; p->weight=0;
p->nextarc=g.vertices[i].firstarc; /*插入表结点*/
g.vertices[i].firstarc=p;
/*将顶点Vi插入到第j个单链表的表头，也就是用“头插法”建立一个单链表*/
p=(ENode *)malloc(sizeof(ENode));
p->adjvex=i; p->weight=0;
p->nextarc=g.vertices[j].firstarc;
g.vertices[j].firstarc=p;
}
}第3关：图的广度优先遍历
任务描述
本关任务：图的广度优先遍历。
相关知识
为了完成本关任务，你需要掌握：图的广度优先遍历。
图的广度优先遍历
设初始时，图中所有顶点未曾被访问过： ● 从图中某个顶点 v 出发，访问此顶点； ● 依次访问 v 的各个未被访问的多个邻接点； ● 分别从这些邻接点出发依次访问它们的邻接点，并使 “先被访问顶点的邻接点” 先于 “后被访问顶点的邻接点” 被访问，直至图中所有已被访问的顶点的邻接点都被访问到； ● 如果此时还有未被访问的顶点，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 如：下图从V0出发，可以得到一个广度优先遍历序列为{ V0 ,V1 ,V2 ,V3 ,V4 ,V5 ,V6 ,V7 }
编程要求
在右侧编辑器中补充代码，完成BFSTraverse函数，实现图的深度优先遍历。具体要求如下：
* BFSTraverse：广度优先遍历邻接表存储的图，需借助队列实现。
测试说明
可在右侧文件夹中查看step3/Main.cpp文件，以便于你的操作。
平台会对你编写的代码进行测试。
输入输出说明： 第一行输入图的类型、图的顶点数和边数。 第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。 输出广度优先遍历的结果。 如图G2，
测试输入: 2 5 6 0 1 0 3 1 2 1 4 2 3 2 4
预期输出： 0 3 1 2 4 //广度优先遍历的结果
开始你的任务吧，祝你成功！
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraph.h"
int visited[MAXVEX]; /*设访问标志数组为全局变量*/
void BFSTraverse(ALGraph g)
{/*广度优先遍历以邻接表存储的图g，由于BFS要求”先被访问的顶点的邻接点也先被访问”，故需借助队列Q实现*/
// 请在这里补充代码，完成本关任务
/********** Begin *********/
int i;
SeqQueue Q; //创建队列
for (i=0; i<g.vexnum; ++i){ /*访问标志数组初始化*/
visited[i] = 0;
}
InitQueue(Q); //队列的初始化
for (i=0; i<g.vexnum; ++i){
if(!visited[i]){ //如果第i个结点没有被访问
visited[i] = 1;
printf("%d ", g.vertices[i].vex);
EnQueue(Q, i); //将元素x入队
while (Q.len!=0){ //当队列不为空时,或者 Q.front != Q.rear
DeQueue(Q, i); //将队头元素出队
ENode *p = g.vertices[i].firstarc;
while (p){
if (!visited[p->adjvex]){
visited[p->adjvex] = 1;
printf("%d ", g.vertices[p->adjvex].vex);
EnQueue(Q, p->adjvex); //将元素x入队
}
p = p->nextarc;
}
}
}
}
/********** End **********/
}
void InitQueue(SeqQueue &q)//队列的初始化
{
q.front=q.rear=0;q.len=0;
}
int QueueEmpty(SeqQueue q)//判队空
{
if(q.len==0)return 1;
else return 0;
}
void EnQueue(SeqQueue &q, datatype x)//将元素x入队
{
if(q.len==MAXSIZE)//判队满
{
printf("Queue is full\n");return;
}
q.data[q.rear]=x; q.rear=(q.rear+1)%MAXSIZE;
q.len++;
}
void DeQueue(SeqQueue &q, datatype &x)//将队头元素出队
{
if(q.len==0)//判队空
{
printf("Queue is empty\n");return;
}
x=q.data[q.front]; q.front=(q.front+1)%MAXSIZE;
q.len--;
}
void CreateUDG_ALG(ALGraph &g) /*构造无向图的邻接表*/
{
int i,j,k;ENode *p;
//printf("请输入图的类型(0-3表示DG,DN,UDG,UDN)、顶点数、边数：\n");
scanf("%d%d%d",&g.kind,&g.vexnum,&g.edgenum);
for(i=0;i<g.vexnum;i++) /*构造头结点数组*/
{
g.vertices[i].vex=i;
g.vertices[i].firstarc=NULL; /*初始化头结点指针域为空*/
}
//printf("请按顶点编号从小到大的顺序输入各条边的两顶点：\n");
for(k=0;k<g.edgenum;k++) /*构造邻接表*/
{
scanf("%d%d",&i,&j); /*输入一条边所依附的两个顶点的编号*/
/*将顶点Vj插入到第i个单链表的表头，也就是用“头插法”建立一个单链表*/
p=(ENode *)malloc(sizeof(ENode)); /*生成表结点*/
p->adjvex=j; p->weight=0;
p->nextarc=g.vertices[i].firstarc; /*插入表结点*/
g.vertices[i].firstarc=p;
/*将顶点Vi插入到第j个单链表的表头，也就是用“头插法”建立一个单链表*/
p=(ENode *)malloc(sizeof(ENode));
p->adjvex=i; p->weight=0;
p->nextarc=g.vertices[j].firstarc;
g.vertices[j].firstarc=p;
}
}附其余头文件：
ALGraph.h
#include"stdio.h"
#include"stdlib.h"
#define MAXVEX 20 /*最大顶点数*/
#define MAXSIZE MAXVEX /*队列最大容量*/
typedef enum{DG,DN,UDG,UDN} GraphKind; /*有向图，有向网，无向图，无向网*/
typedef struct ENode /*表结点类型*/
{
int adjvex;
struct ENode *nextarc;
int weight;
}ENode;
typedef int VexType;
typedef struct VNode /*头结点类型*/
{
VexType vex;
ENode *firstarc;
}VNode, AdjList[MAXVEX]; /*邻接表类型定义*/
typedef struct
{
AdjList vertices; /*用邻接表存储顶点集合及边集合*/
int vexnum,edgenum;
GraphKind kind;
}ALGraph; /*邻接表存储的图的类型定义*/
typedef int datatype;
typedef struct
{
datatype data[MAXSIZE]; /*存放顶点编号*/
int front;
int rear; //队尾指针，指向队尾元素的下一个位置
int len;
}SeqQueue; //循环顺序队列的类型定义
/*******函数声明*******/
void CreateUDG_ALG(ALGraph &g); /*构造无向图的邻接表*/
void PrintAdjList(ALGraph g); /*输出邻接表*/
void DFSTraverse(ALGraph g); /*深度优先遍历以邻接表存储的图g*/
void DFS(ALGraph g, int i); /*从未被访问的顶点Vi出发深度优先遍历图g*/
void BFSTraverse(ALGraph g); /*广度优先遍历以邻接表存储的图g*/
void InitQueue(SeqQueue &q); /*队列初始化*/
int QueueEmpty(SeqQueue q); /*判队空*/
void EnQueue(SeqQueue &q, datatype x); /*入队*/
void DeQueue(SeqQueue &q, datatype &x); /*出队*/第一关main.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraph.h"
//#include "ALGraph.cpp"
int main()
{
ALGraph g;
CreateUDG_ALG(g); /*创建邻接表存储的无向图*/
//printf("\n图的邻接表：\n");
PrintAdjList(g); /*输出邻接表*/
return 0;
}第二关：
ALGraph.h
#include"stdio.h"
#include"stdlib.h"
#define MAXVEX 20 /*最大顶点数*/
#define MAXSIZE MAXVEX /*队列最大容量*/
typedef enum{DG,DN,UDG,UDN} GraphKind; /*有向图，有向网，无向图，无向网*/
typedef struct ENode /*表结点类型*/
{
int adjvex;
struct ENode *nextarc;
int weight;
}ENode;
typedef int VexType;
typedef struct VNode /*头结点类型*/
{
VexType vex;
ENode *firstarc;
}VNode, AdjList[MAXVEX]; /*邻接表类型定义*/
typedef struct
{
AdjList vertices; /*用邻接表存储顶点集合及边集合*/
int vexnum,edgenum;
GraphKind kind;
}ALGraph; /*邻接表存储的图的类型定义*/
typedef int datatype;
typedef struct
{
datatype data[MAXSIZE]; /*存放顶点编号*/
int front;
int rear; //队尾指针，指向队尾元素的下一个位置
int len;
}SeqQueue; //循环顺序队列的类型定义
/*******函数声明*******/
void CreateUDG_ALG(ALGraph &g); /*构造无向图的邻接表*/
void PrintAdjList(ALGraph g); /*输出邻接表*/
void DFSTraverse(ALGraph g); /*深度优先遍历以邻接表存储的图g*/
void DFS(ALGraph g, int i); /*从未被访问的顶点Vi出发深度优先遍历图g*/
void BFSTraverse(ALGraph g); /*广度优先遍历以邻接表存储的图g*/
void InitQueue(SeqQueue &q); /*队列初始化*/
int QueueEmpty(SeqQueue q); /*判队空*/
void EnQueue(SeqQueue &q, datatype x); /*入队*/
void DeQueue(SeqQueue &q, datatype &x); /*出队*/#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraph.h"
//#include "ALGraph.cpp"
int main()
{
ALGraph g;
CreateUDG_ALG(g); /*创建邻接表存储的无向图*/
DFSTraverse(g); /*深度优先遍历*/
return 0;
}第三关：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraph.h"
//#include "ALGraph.cpp"
int main()
{
ALGraph g;
CreateUDG_ALG(g); /*创建邻接表存储的无向图*/
BFSTraverse(g); /*广度优先遍历*/
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-11-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
