第1关:图的邻接矩阵存储及求邻接点操作

任务描述

本关任务:要求从文件输入顶点和边数据,包括顶点信息、边、权值等,编写程序实现以下功能。 1)构造无向网G的邻接矩阵和顶点集,即图的存储结构为邻接矩阵。 2)输出无向网G的各顶点和邻接矩阵。 3)输出无向网G中顶点H的所有邻接顶点。

相关知识

图是表达“多对多”的关系的一种数据结构,由非空的有限顶点集合和有限边集合组成。将图的类型定义为枚举类型,在枚举值表中罗列:

enum GraphKind{DG,DN,UDG,UDN}; // 有向图,有向网,无向图,无向网

顶点集合

每个顶点数据类型为VertexType,一个图的顶点集合用数组表示,数组下标表示顶点位置。数组内容包含顶点的信息,图的顶点集合的数据类型定义如下:

 
  1. #define MAX_VERTEX_NUM 20 // 最大顶点个数
  2. typedef char VertexType[16]; // 顶点类型
  3. VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量

将顶点数据类型定义为长度为16的字符数组类型,可以将表示的城市名称存储在计算机中。

边集合

邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:

图及邻接矩阵

网及邻接矩阵

用邻接矩阵来表示一个具有n个顶点的图时,用邻接矩阵中的n×n个元素存储顶点间相邻关系,对于无权图,当邻接矩阵中的元素仅表示相应的边是否存在时,VRType可定义为值为01的枚举类型,0表示两个顶点之间没有边,即没有关系。对于带权图,则为权值,如果两个顶点之间没有边,则用一个很大很大的数代替。将顶点关系类型VRType定义为整型:

typedef int VRType; // 顶点关系边的数据类型

顶点关系边的数据类型类型,对于无权图,用1或0表示相邻否;对于带权图,则为权值。

图的边集合的数据类型定义如下:

 
  1. #define INFINITY INT_MAX // 用整型最大值代替∞
  2. typedef struct
  3. {
  4. VRType adj;
  5. } ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

说明: AcrCellAdjMatrix都是类型的名称,若有定义: AdjMatrix arcs;arcs是一个以元素类型为AcrCell20*20二维数组。上述声明与下面等同: ArcCell arcs [MAX_VERTEX_NUM][MAX_VERTEX_NUM];

图的邻接矩阵存储表示,类型定义如下:

 
  1. struct MGraph
  2. {
  3. VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
  4. AdjMatrix arcs; // 邻接矩阵
  5. int vexnum, arcnum; // 图的当前顶点数和弧数
  6. GraphKind kind; // 图的种类标志
  7. };

图的邻接矩阵表示法是图的一种顺序存储结构,优点是可以快速判断两个顶点之间是否存在边,可以快速添加边或者删除边,可以快速计算顶点度数、求邻接点的操作等;而其缺点是如果顶点之间的边比较少,会比较浪费空间。

邻接矩阵具有如下性质: (1)图中各项点的序号确定后,图的邻接矩阵是唯一确定的; (2)无向图和无向网的邻接矩阵是一个对称矩阵; (3)无向图邻接矩阵中第i行(或第i列)的非0元素的个数即为第i个顶点的度; (4)有向图邻接矩阵中第i行非0元素的个数为第i个顶点的出度,第i列非0元素的个数为第i个顶点的入度,第i个顶点的度为第i行与第j非0元素个数之和; (5)无向图的边数等于邻接矩阵中非0元素个数之和的一半,有向图的弧数等于邻接矩阵中非0元素个数之和。

编程要求

根据提示,在右侧编辑器补充代码,要求从文件中输入顶点和边数据,包括顶点信息、边、权值等,编写函数实现图的基本运算:

 
  1. void CreateGraphF(MGraph &G);// 采用数组(邻接矩阵)表示法,由文件构造无向网G
  2. void Display(MGraph G); // 输出邻接矩阵存储表示的图G
  3. int LocateVex(MGraph G,VertexType u);//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
  4. VertexType& GetVex(MGraph G,int v); // v是G中某个顶点的序号,返回v的值
  5. int FirstAdjVex(MGraph G,VertexType v);//v是图G中某个顶点,返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
  6. int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是G中某个顶点,w是v的邻接顶点,返回v的(相对于w的)下一个邻接顶点的序号,若w是v的最后一个邻接顶点,则返回-1
  7. void DestroyGraph(MGraph &G); // 销毁图G

测试说明

平台会对你编写的代码进行测试:

测试输入: 3 lt.txt 武汉

输入说明: 第一行输入3,表示输入图的类型为无向网。 第二行输入文件名,该文件里保存了图的数据信息,内容如下: 6 9 武汉 上海 长沙 南京 成都 广州 武汉 长沙 9 武汉 成都 2 长沙 上海 2 长沙 南京 2 上海 南京 5 上海 广州 4 上海 成都 3 南京 广州 8 成都 广州 6

第1行为图的顶点的个数n; 第2行为图的边的条数m; 第3行至第n+2行是n个顶点的数据; 第n+3行至第n+m+2行是m条边的数据; 最后输入一个顶点的数据

预期输出: 无向网 6个顶点9条边。顶点依次是: 武汉 上海 长沙 南京 成都 广州 图的邻接矩阵: ∞ ∞ 9 ∞ 2 ∞ ∞ ∞ 2 5 ∞ ∞ 9 2 ∞ 2 ∞ ∞ ∞ 5 2 ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 长沙 成都

输出说明: 第一行输出图的类型。 第二行起输出图的顶点和边的数据信息。 最后一行输出输入顶点的所有邻接点。


开始你的任务吧,祝你成功!

最后通关代码

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<limits.h>

typedef int VRType;    // 顶点关系类型

typedef char VertexType[20]; // 顶点类型

// 图的数组(邻接矩阵)存储表示

#define INFINITY INT_MAX // 用整型最大值代替∞

#define MAX_VERTEX_NUM 20 // 最大顶点个数

typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向图,有向网,无向图,无向网}

typedef struct

{

    VRType adj; // 顶点关系类型。对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组

typedef struct      // 图的数组(邻接矩阵)存储

{

    VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量

    AdjMatrix arcs; // 邻接矩阵

    int vexnum,arcnum; // 图的当前顶点数和弧数

    GraphKind kind; // 图的种类标志

}MGraph;  

void visit(VertexType i);

void CreateGraphF(MGraph &G);// 采用数组(邻接矩阵)表示法,由文件构造无向网G

void Display(MGraph G);    // 输出邻接矩阵存储表示的图G

int LocateVex(MGraph G,VertexType u);//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1

VertexType& GetVex(MGraph G,int v);    // v是G中某个顶点的序号,返回v的值

int FirstAdjVex(MGraph G,VertexType v);//v是图G中某个顶点,返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1

int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是G中某个顶点,w是v的邻接顶点,返回v的(相对于w的)下一个邻接顶点的序号,若w是v的最后一个邻接顶点,则返回-1

void DestroyGraph(MGraph &G); // 销毁图G




 

int main()

{

    MGraph g;

    VertexType v1,v2;

    CreateGraphF(g);      // 利用数据文件创建邻接矩阵表示的图  

    Display(g);           // 输出图  

    int i,j,k,n;

    //printf("请输入顶点的值: ");

    scanf("%s",v1);

    //printf("输出图G中顶点%s的所有邻接顶点: ",v1);

    k=FirstAdjVex(g,v1);

    while(k!=-1)

    {

        strcpy(v2, g.vexs[k] );

        visit(v2);

        k=NextAdjVex(g,v1,v2);

    }

    printf("\n");    

    return 0;

}

void visit(VertexType i)

{

    printf("%s ",i);

}


 

void CreateGraphF(MGraph &G)

{

    // 采用数组(邻接矩阵)表示法,由文件构造无向网G

    /********** Begin **********/

int i,j,k,w;

    char filename[13];

    VertexType va,vb;

    FILE *graphlist;

    scanf("%d",&G.kind);

    scanf("%s",filename);  

    graphlist=fopen(filename,"r");      

    fscanf(graphlist,"%d",&G.vexnum);

    fscanf(graphlist,"%d",&G.arcnum);

    for(i=0;i<G.vexnum;++i)        

        fscanf(graphlist,"%s",G.vexs[i]);

    for(i=0;i<G.vexnum;++i)          

        for(j=0;j<G.vexnum;++j)

        {

            if(G.kind%2)            

                G.arcs[i][j].adj=INFINITY;      

            else                    

                G.arcs[i][j].adj=0;

        }

        for(k=0;k<G.arcnum;++k)

        {

            if(G.kind%2)                

                fscanf(graphlist,"%s%s%d",va,vb,&w);

            else                    

                fscanf(graphlist,"%s%s",va,vb);

            i=LocateVex(G,va);

            j=LocateVex(G,vb);

            if(G.kind == 0)          

                G.arcs[i][j].adj =1;

            else if(G.kind == 1)

                G.arcs[i][j].adj=w;    

            else   if(G.kind == 2)      

                G.arcs[i][j].adj =  G.arcs[j][i].adj=1;

            else

                G.arcs[i][j].adj =  G.arcs[j][i].adj = w;

        }

    fclose(graphlist);  

   

   

    /********** End **********/

}


 

void Display(MGraph G)

{

    // 输出邻接矩阵存储表示的图G

    /********** Begin **********/

int i,j;

    switch(G.kind)

    {

    case DG: printf("有向图\n");         break;

    case DN: printf("有向网\n");          break;

    case UDG:printf("无向图\n");         break;

    case UDN:printf("无向网\n");

    }

    printf("%d个顶点%d条边。顶点依次是: ",G.vexnum,G.arcnum);

    for(i=0;i<G.vexnum;++i)        

        printf("%s ",G.vexs[i]);

    printf("\n图的邻接矩阵:\n");    

    for(i=0;i<G.vexnum;i++)

    {

        for(j=0;j<G.vexnum;j++)

            if(G.kind%2)  

            {

                if(G.arcs[i][j].adj==INFINITY)

                    printf("%s\t","∞");

                else

                    printf("%d\t",G.arcs[i][j].adj);

            }

            else

                printf("%d\t",G.arcs[i][j].adj);

        printf("\n");

    }  

   

    /********** End **********/

}


 

int LocateVex(MGraph G,VertexType u)

{

    //初始条件:图G存在,u和G中顶点有相同特征

    // 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1

    /********** Begin **********/

int i;

    for(i=0;i<G.vexnum;++i)

        if(strcmp(u,G.vexs[i]) == 0)    

            return i;  

    return -1;      

   

    /********** Begin **********/

}

VertexType& GetVex(MGraph G,int v)

{

    // 初始条件:图G存在,v是G中某个顶点的序号。操作结果:返回v的值

    /********** Begin **********/

if( v>=G.vexnum || v<0 )

        exit(0);

    return (G.vexs[v]);

   

    /********** End **********/

}



 

int FirstAdjVex(MGraph G,VertexType v)

{

    // 初始条件:图G存在,v是G中某个顶点

    // 操作结果:返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1

    /********** Begin **********/

int i,j=0,k;

    k=LocateVex(G,v); // k为顶点v在图G中的序号

    if(G.kind%2) // 网

        j=INFINITY;

    for(i=0;i<G.vexnum;i++)

        if(G.arcs[k][i].adj!=j)

            return i;

    return -1;  

   

    /********** End **********/

}

int NextAdjVex(MGraph G,VertexType v,VertexType w)

{

    // 初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点

    // 操作结果:返回v的(相对于w的)下一个邻接顶点的序号,若w是v的最后一个邻接顶点,则返回-1

    /********** Begin **********/

int i,j=0,k1,k2;

    k1=LocateVex(G,v); // k1为顶点v在图G中的序号

    k2=LocateVex(G,w); // k2为顶点w在图G中的序号

    if(G.kind%2) // 网

        j=INFINITY;

    for(i=k2+1;i<G.vexnum;i++)

        if(G.arcs[k1][i].adj!=j)

            return i;

    return -1;  

   

    /********** End **********/

}


 

void DestroyGraph(MGraph &G)

{ // 初始条件:图G存在。操作结果:销毁图G

    /********** Begin **********/

int i,j,k=0;

    if(G.kind%2)

        k=INFINITY;

    G.vexnum=0;

    G.arcnum=0;

   

    /********** End **********/

}




第2关:图的深度优先遍历任务描述

本关任务:以邻接矩阵存储图,要求编写程序实现图的深度优先遍历。

相关知识

图的深度优先遍历类似于树的先序遍历, 是树的先序遍历的推广,其基本思想如下:

  1. 从某个顶点v出发,访问此顶点。
  2. 访问一个与v邻接的顶点u之后,再从u出发,访问与u邻接且未被访问的顶点w,依此类推。
  3. 当到达一个所有邻接顶点都被访问的顶点时,则又从最后被访问过的顶点开始,依次退回到最近被访问的尚有邻接顶点的末被访问过的顶点,从该顶点出发,重复步骤 2 和 3 ,直到所有被访问过的顶点的邻接顶点都被访问过为止。

在程序里完成遍历需要在函数体外定义全局访问标志数组,记录顶点是否被访问过,初始时,所有元素均为0,表示所有顶点未被访问过:

int visited[MAX_VERTEX_NUM] = {0};

访问每个顶点时,定义输出顶点数据的专用函数:

 
  1. void visit(VertexType i)
  2. {
  3. printf("%s ",i); // VertexType是char [20]类型
  4. }

以邻接矩阵作为存储结构进行深度优先遍历的算法如下:

深度优先遍历的代码分为两部分,遍历的图可能是非连通图,从一个顶点出发,可能不能遍历所有顶点,故对于每个顶点都要检查一次,是否被访问过,如果没有,从这个没被访问的顶点出发执行一次深度优先遍历,算法如下:

 
  1. void DFSTraverse(Mgraph G)
  2. {
  3. // 初始条件:图G存在,vi是顶点的输出函数的指针。
  4. // 操作结果:从第1个顶点起,深度优先遍历图G,并对每个顶点访问一次且仅一次
  5. int v;
  6. for(v=0;v<G.vexnum;v++)
  7. visited[v]=0; // 访问标志数组初始化(未被访问)
  8. for(v=0;v<G.vexnum;v++)
  9. if(!visited[v])
  10. DFS(G,v); // 对尚未访问的顶点v调用DFS
  11. printf("\n");
  12. }

编程要求

根据提示,在右侧编辑器补充代码,实现以邻接矩阵作为存储结构的图深度优先遍历算法:

  • void DFS(MGraph G,int v); // 从第v个顶点出发递归地深度优先遍历图G
  • void DFSTraverse(MGraph G); // 图G存在,从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数visit一次且仅一次

测试说明

平台会对你编写的代码进行测试:

测试输入: 0 lt2.txt

输入说明: 第一行输入0,表示输入图的类型为有向图。 第二行输入文件名,该文件里保存了图的数据信息,内容如下:

有向图的世界里

第1行为图的顶点的个数n; 第2行为图的边的条数m; 第3行至第n+2行是n个顶点的数据; 第n+3行至第n+m+2行是m条边的数据;

预期输出: 有向图 7个顶点9条边。顶点依次是: 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统 图的邻接矩阵: 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 深度优先遍历序列: 高等数学 C语言 数据结构 编译原理 操作系统 离散数学 程序设计基础

输出说明: 第一行输出图的类型。 第二行起输出图的顶点和边的数据信息。 最后一行为从“高等数学”出发进行深度优先遍历的序列。


开始你的任务吧,祝你成功!

最后通关代码

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<limits.h>

#include"MGraph.h"

void DFS(MGraph G,int v);// 从第v个顶点出发递归地深度优先遍历图G

void DFSTraverse(MGraph G);// 图G存在,从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数visit一次且仅一次

int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)

int main()

{

   MGraph g;

    VertexType v1,v2;

    CreateGraphF(g); /* 利用数据文件创建无向图*/

    Display(g); /* 输出无向图*/  

    printf("深度优先遍历序列:\n");

    DFSTraverse(g);

    return 0;

}



 

void DFS(MGraph G,int v)

{

    // 从第v个顶点出发递归地深度优先遍历图G

    /********** Begin **********/

int w;

    visited[v]=1;

    visit(G.vexs[v]);

    for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))

        if(!visited[w])

            DFS(G,w);  

    /********** End **********/

}

void DFSTraverse(MGraph G)

{   //图G存在,从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数visit一次且仅一次

    /********** Begin **********/

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

    printf("\n");  

    /********** End **********/

}

第3关:图的广度优先遍历

任务描述

本关任务:以邻接矩阵存储图,要求编写程序实现图的广度优先遍历。

相关知识

广度优先遍历类似于树的按层次遍历的过程。

假设从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过和邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。

若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

换句话说,广度优先遍历图的过程中以v为起始点,由近至远,依次访问和v有路径相通且路径长度为1,2,…的顶点。

本关卡提供顺序队列sqqueue的相关操作和功能,顺序队列数据类型定义及相关操作函数接口定义如下,在进行图的广度优先遍历的过程中,可以根据需要调用以下操作:

 
  1. struct SqQueue
  2. {
  3. QElemType *base; // 初始化的动态分配存储空间
  4. int front; // 头指针,若队列不空,指向队列头元素
  5. int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置
  6. };
  7. void InitQueue(SqQueue &Q); // 构造一个空循环队列Q
  8. void DestroyQueue(SqQueue &Q); // 销毁循环队列Q,Q不再存在
  9. void ClearQueue(SqQueue &Q); // 将Q清为空循环队列
  10. int QueueEmpty(SqQueue Q); // 若循环队列Q为空队列,则返回TRUE;否则返回FALSE
  11. int QueueLength(SqQueue Q); // 返回Q的元素个数,即循环队列的长度
  12. int GetHead(SqQueue Q,QElemType &e); // 若循环队列不空,则用e返回Q的队头元素,并返回OK;否则返回ERROR
  13. int EnQueue(SqQueue &Q,QElemType e); // 插入元素e为循环队列Q的新的队尾元素
  14. int DeQueue(SqQueue &Q,QElemType &e); // 若循环队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR
  15. void QueueTraverse(SqQueue Q,void(*vi)(QElemType)); // 从队头到队尾依次对队列Q中每个元素调用函数vi()

编程要求

根据提示,在右侧编辑器补充代码,实现以邻接矩阵作为存储结构的图广度优先遍历算法:

  • void BFSTraverse(MGraph G); // 图G存在,从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数visit一次且仅一次

测试说明

平台会对你编写的代码进行测试:

测试输入: 0 lt2.txt

输入说明: 第一行输入0,表示输入图的类型为有向图。 第二行输入文件名,该文件里保存了图的数据信息,内容如下:

有向图的世界里

第1行为图的顶点的个数n; 第2行为图的边的条数m; 第3行至第n+2行是n个顶点的数据; 第n+3行至第n+m+2行是m条边的数据;

预期输出: 有向图 7个顶点9条边。顶点依次是: 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统 图的邻接矩阵: 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 广度优先遍历序列: 高等数学 C语言 离散数学 数据结构 编译原理 操作系统 程序设计基础

输出说明: 第一行输出图的类型。 第二行起输出图的顶点和边的数据信息。 最后一行为从“高等数学”出发进行广度优先遍历的序列。


开始你的任务吧,祝你成功!

最后通关代码

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<limits.h>

#include"MGraph.h"

#include"sqqueue.h"


 

void BFSTraverse(MGraph G);// 图G存在,从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数visit一次且仅一次

int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)

int main()

{

    MGraph g;

    VertexType v1,v2;

    CreateGraphF(g);    // 利用数据文件创建图

    Display(g);         // 输出图  

    printf("广度优先遍历序列:\n");

    BFSTraverse(g);

    return 0;

}



 

void BFSTraverse(MGraph G)

{   // 图G存在,从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数visit一次且仅一次

    /********** Begin **********/

int v,u,w;

    SqQueue Q;

    for(v=0;v<G.vexnum;v++)

        visited[v]=0;

    InitQueue(Q);

    for(v=0;v<G.vexnum;v++)

        if(!visited[v]){

            visited[v]=1;

            visit(G.vexs[v]);

            EnQueue(Q,v);

            while(!QueueEmpty(Q)){

                DeQueue(Q,u);

                for(w=FirstAdjVex(G,G.vexs[u]);w>=0;w=NextAdjVex(G,G.vexs[u],G.vexs[w]))

                    if(!visited[w]){

                        visited[w]=1;

                        visit(G.vexs[w]);

                        EnQueue(Q,w);

                    }

            }

        }

        printf("\n");

    /********** End **********/

}


 

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐