图的两种存储结构及基本算法
一、图的邻接矩阵存储
1.存储表示
#define vexnum 10
typedef struct{
vextype vexs[vexnum];
int arcs[vexnum][vexnum];
}mgraph;
2.建立无向图的邻接矩阵算法
void creat(mgraph *g, int e){
for(i=0;i scanf(“%c”,&g->vexs[i]); for(i=0;i for(j=0;j g->arcs[i][j]=0; for(k=0;k scanf(“%d,%d”,&i,&j); g->arcs[i][j]=1; g->arcs[j][i]=1;} } 3.建立有向图的邻接矩阵算法 void creat(mgraph *g, int e){ for(i=0;i scanf(“%c”,&g->vexs[i]); for(i=0;i for(j=0;j g->arcs[i][j]=0; for(k=0;k scanf(“%d,%d,%d”,&i,&j,&w); g->arcs[i][j]=w; } } 二、图的邻接表存储 1.邻接表存储表示 #define vexnum 10 typedef struct arcnode{ int adjvex; struct arcnode *nextarc; }Arcnode; typedef struct vnode{ vextype data; Arcnode *firstarc; }Vnode; typedef struct{ Vnode vertices[vexnum]; int vexnum,arcnum; }algraph; 2.建立无向图的邻接表算法： void creat(algraph *g, int e){ for(i=0;i scanf(“%c”,&g->vertices[i]->data); g->vertices[i]->firstarc=NULL;} for(k=0;k scanf(“%d,%d”,&i,&j); q=(Arcnode *)malloc(sizeof(Arcnode)); p=(Arcnode *)malloc(sizeof(Arcnode)); p->adjvex=j; p->nextarc=g->vertices[i]->firstarc; g->vertices[i]->firstarc=p; q->adjvex=i; q->nextarc=g->vertices[j]->firstarc; g->vertices[j]->firstarc=q; } } 3.建立有向图邻接表算法： void creat(algraph *g, int e){ for(i=0;i scanf(“%c”,&g->vertices[i]->data); g->vertices[i]->firstarc=NULL;} for(k=0;k scanf(“%d,%d”,&i,&j); p=(Arcnode *)malloc(sizeof(Arcnode)); p->adjvex=j; p->nextarc=g->vertices[i]->firstarc; g->vertices[i]->firstarc=p; } } 三、图的遍历 1.连通图的深度优先搜索遍历 int visited[vexnum]={0}; void dfs(mgraph *g, int i){ printf(“%3c”,g->vexs[i]); visited[i]=1; for(j=0;j if((g->arcs[i][j]==1)&&(!visited[j])) dfs(g, j); } 2.联通图的广度优先搜索遍历 int visited[vexnum]={0}; void bfs(mgraph *g, int k){ int q[20], f, r; f=0; r=0; printf(“%3c”,g->vexs[k]); visited[k]=1; q[r]=k; r++; while(r!=f){ i=q[f]; f++; for(j=0;j if((g->arcs[i][j]==1)&&!visited[j]){ printf(“%3c”,g->vexs[j]); visited[j]=1; q[r]=j; r++;} } } 4.求图的联通分量 int visited[vexnum]={0}; void component(mgraph *g){ int count=0; for(j=0;j if(!visited[j]){ count++; printf(“\n第%d个联通分量:”, count); dfs(g, j); } printf(“\n 共有%d个联通分量。\n”, count); } //算法功能：采用邻接表存储结构建立无向图 #include 2007 C C C 语言的特点，简单的C 程序介绍，C 程序的上机步骤。1 、算法的概念2、简单的算法举例3、算法的特性4、算法的表示（自然语言、流程图、N-S 图表示） 1 、 C 的数据类型、常量与变星、整型数据、实型数据、字符型数据、字符串常量。2、 C 的运算符运算意义、优先级、结合方向。3、算术运算符和算术表达式，各类数值型数据间的混合运算。4、赋值运算符和赋值表达式。5、逗号运算符和逗号表达式。 1 、程序的三种基本结构。2、数据输入输出的概念及在C 语言中的实现。字符数据的输入输出，格式输入与输出。 1 、关系运算符及其优先级，关系运算和关系表达式。2、逻辑运算符及其优先级，逻辑运算符和逻辑表达式。3、if语句。if语句的三种形式，if语句的嵌套，条件运算符。4、switch 语句. 1 、while 语句。2、do/while 语句。3、for 语句。4、循环的嵌套。5、break 语句和continue 语句。1 、一维数组的定义和引用。2、二维数组的定义和引用。3、字符数组。4、字符串与字符数组。5、字符数组的输入输出。6、字符串处理函数1 、函数的定义。2、函数参数和函数的值，形式参数和实际参数。3、函数的返回值。4、函数调用的方式，函数的声明和函数原型。5、函数的嵌套调用。 6、函数的递归调用。 7、数组作为函数参数。 8、局部变量、全局变量的作用域。 9、变量的存储类别，自动变星，静态变量。1 、带参数的宏定义。2、“文件包含”处理。1 、地址和指针的概念。2、变量的指针和指向变量的指针变量。3、指针变量的定义 和引用。4、指针变量作为函数参数。5、数组的指针和指向数组的指针变量。6、指向数组元素的指针。7、通过指针引用数组元素。8、数组名作函数参数。9、二维数组与指针。 1 0、指向字符串的指针变星。字符串的指针表示形式，字符串指针作为函数参数。11 、字符指针变量和字符数组的异同。1 2、返回指针值的函数。1 3、指针数组。1 、定义结构体类型变星的方法。2、结构体变量的引用。3、结构体变量的初始化。4、结构体数组5、指向结构体类型数据的指针。6、共用体的概念，共用体变量的定义和引用，共用体类型数据的特点。typedef 1 、数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。2、数据结构的两大类逻辑结构和常用的存储表示方法。3、算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。 1 、线性表的逻辑结构特征。2、线性表上定义的基本运算。3、顺序表的特点，即顺序表如何反映线性表中元素之间的逻辑关系。4、顺序表上的插入、删除操作及其平均时间性能分析。5、链表如何表示线性表中元素之间的逻辑关系。6、链表中头指针和头结点的使用。7、单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。8、顺序表和链表的主要优缺点。9、针对线性表上所需的主要操作，选择时空性能优越的存储结构。 1 、栈的逻辑结构特点．栈与线性表的异同。2、顺序栈和链栈实现的进栈、退栈等基本算法。3、栈的空和栈满的概念及其判定条件。4、队列的逻辑结构特点，队列与线性表的异同。5、顺序队列(主要是循 复习题集─参考答案 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别设在这片存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。 （×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。 第 6 章图 课后习题讲解 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 实验三图的存储结构及各种运算的实现 （必做） 计算机与信息技术学院 14级3班黄雨梅 201421012808 计算机科学与技术 实验目的： 1、掌握图的逻辑结构及其常用的存储表示方法，建立图的邻接表与邻接矩阵。 2、熟练掌握图的深度与广度优先搜索算法的基本思想，并能在不同存储结构上实现算法。 3、深入理解最小生成树的定义，掌握Prim算法和Kruskar算法构造最小生成树的基本思想，并实现Prim算法。 4、掌握用DIJKSTTRA算法求解单源最短路径的基本过程和算法。 实验学时:8 实验内容： 1、建立图的邻接表与邻接矩阵，并在不同存储结构上实现深度与广度优先搜索算法。 2、用Prim算法构造带权网络的最小生成树。 3、用DIJKSTTRA算法求解单源最短路径。 选做部分 4、求拓朴序列和关键路径。 第一题： 建立图的邻接表与邻接矩阵，并在不同存储结构上实现深度与广度优先搜索算法#include public: void InitQueue(){ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; } void EnQueue(int e) { base[rear]=e; rear=(rear+1)%QUEUE_SIZE; } void DeQueue(int &e) { e=base[front]; front=(front+1)%QUEUE_SIZE; } public: int *base; int front; int rear; }; //图G中查找元素c的位置 int Locate(Graph G,char c) { for(int i=0;i 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十三图的基本操作—邻接表存储结构 学生姓名专业班级学号 实验成绩指导老师（签名）日期2015-1-15 一.实验目的和要求 1、掌握图的存储结构：邻接表。 2、学会对图的存储结构进行基本操作。 二.实验内容 1、图的邻接表的定义及实现：建立头文件AdjLink.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test5_2.cpp中调用这些函数进行验证。 2、选做：编写图的深度优先遍历函数与广度优先遍历函数，要求把这两个函数添加到头文件AdjLink.h中，并在主函数文件test5_2.cpp中添加相应语句进行测试。 3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc及源程序文件test5_2.cpp、AdjLink.h到Ftp服务器上自己的文件夹下。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 邻接表表示法的C语言描述： typedef struct Node { int adjvex; // 邻接点的位置 WeightType weight; //权值域，根据需要设立 struct Node *next; // 指向下一条边（弧） } edgenode; // 边结点 typedef edgenode *adjlist[ MaxVertexNum ];//定义图的邻接表结构类型（没包含顶点信息） typedef struct{ vexlist vexs; //顶点数据元素 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 《图的邻接表存储结构实验报告》1.需解决的的问题 利用邻接表存储结果，设计一种图。 2.数据结构的定义 typedef struct node {//边表结点 int adj;//边表结点数据域 struct node *next; }node; typedef struct vnode {//顶点表结点 char name[20]; node *fnext; }vnode,AList[M]; typedef struct{ AList List;//邻接表 int v,e;//顶点树和边数 }*Graph; 3.程序的结构图 4.函数的功能 1）建立无向邻接表 Graph Create1( )//建立无向邻接表{ Graph G; int i,j,k; node *s; G=malloc(M*sizeof(vnode)); printf("输入图的顶点数和边数："); scanf("%d%d",&G->v,&G->e);//读入顶点数和边数for(i=0;i 一、图的邻接矩阵存储 1.存储表示 #define vexnum 10 typedef struct{ vextype vexs[vexnum]; int arcs[vexnum][vexnum]; }mgraph; 2.建立无向图的邻接矩阵算法 void creat(mgraph *g, int e){ for(i=0;i for(i=0;i 图的邻接表存储方式——数组实现初探 焦作市外国语中学岳卫华在图论中，图的存储结构最常用的就是就是邻接表和邻接矩阵。一旦顶点的个数超过5000，邻接矩阵就会“爆掉”空间，那么就只能用邻接表来存储。比如noip09的第三题，如果想过掉全部数据，就必须用邻接表来存储。 但是，在平时的教学中，发现用动态的链表来实现邻接表实现时，跟踪调试很困难，一些学生于是就觉得邻接表的存储方式很困难。经过查找资料，发现，其实完全可以用静态的数组来实现邻接表。本文就是对这种方式进行探讨。 我们知道，邻接表是用一个一维数组来存储顶点，并由顶点来扩展和其相邻的边。具体表示如下图： 其相应的类型定义如下： type point=^node; node=record v:integer; //另一个顶点 next:point; //下一条边 end; var a:array[1..maxv]of point; 而用数组实现邻接表，则需要定义两个数组：一个是顶点数组，一个 是边集数组。 顶点编号结点相临边的总数s第一条邻接边next 此边的另一邻接点边权值下一个邻接边 对于上图来说，具体的邻接表就是： 由上图我们可以知道，和编号为1的顶点相邻的有3条边，第一条边在边集数组里的编号是5，而和编号为5同一个顶点的下条边的编号为3，再往下的边的编号是1，那么和顶点1相邻的3条边的编号分别就是5，3，1。同理和顶点3相邻的3条边的编号分别是11，8，4。如果理解数组表示邻接表的原理，那么实现就很容易了。 类型定义如下： 见图的代码和动态邻接表类似： 下面提供一道例题 邀请卡分发deliver.pas/c/cpp 【题目描述】 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i [试题分类]：数据结构与算法 1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。 A.操作 B.存储映像 C.关系 D.数据元素 答案:C 题型:单选题 知识点:1.2 基本概念和术语 难度:1 2.一般而言，最适合描述算法的语言是( )。 A.自然语言 B.计算机程序语言 C.介于自然语言和程序设计语言之间的伪语言 D.数学公式 答案:C 题型:单选题 知识点:1.4 算法和算法分析 难度:1 3．在下列序列中，不是线性表的是( )。 A. (‘a’,‘b’) B. (a, b) C. (‘AB’,‘CD’) D. (‘a’, b) 答案:D 题型:单选题 知识点:2.1 线性表的类型定义 难度:2 4.对于顺序表的优缺点，以下说法错误的是( )。 A.插入和删除操作较方便 B.可以方便地随机存取表中的任一结点 C.无需为表示结点间的逻辑关系而增加额外的存储空间 D.由于顺序表要求占用连续的空间，存储分配只能预先进行 题型:单选题 知识点:2.2线性表的顺序表示和实现 难度:2 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。 A. s->next=p->next;p->next=s; B. p->next=s->next;s->next=p; C. q->next=s;s->next=p; D. p->next=s;s->next=q; 题型:单选题 知识点:2.3线性表的链式表示和实现 难度:2 6.若某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。 A.单链表 B.带头结点的单链表 C.单循环链表 实验四图的存储、遍历与应用姓名：班级： 学号：日期：一、实验目的： 二、实验内容： 三、基本思想，原理和算法描述: 四、源程序： （1）邻接矩阵的存储： #include 2.3 课后习题解答 2.3.2 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×） 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×） 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 12．线性表的特点是每个元素都有一个前驱和一个后继。（×） 2.3.3 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ } } 时间复杂度为O(n)。 图采用邻接矩阵存储结构 #define TRUE 1 #define FALSE 0 #define MAXV 20 typedef int V ertexType; //用顶点编号表示顶点 typedef struct { // 图的定义 int edges[MAXV][MAXV] ; // 边数组 int n, e; //顶点数，弧数 V ertexType vexs[MAXV]; // 顶点信息 } MGraph; 1、创建具有n个顶点e条边的无向图 void CreateUDG(MGraph &G,int n,int e) { int i,j,u,v; G.n=n;G.e=e; /* printf("请输入%d个顶点的编号：\n",n); for(i=0;i void CreateDG(MGraph &G,int n,int e) { int i,j,u,v; G.n=n;G.e=e; /* printf("请输入%d个顶点的编号：\n",n); for(i=0;i #include 数据结构图的存储结构及基本操作 1.实验目的 通过上机实验进一步掌握图的存储结构及基本操作的实现。 2.实验内容与要求 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。 3.数据结构设计 逻辑结构：图状结构 存储结构：顺序存储结构、链式存储结构 4.算法设计 #include }ArcNode; typedef struct VNode { char data[2]; //顶点就设置和书上V1等等一样吧 ArcNode *firstarc; }VNode,AdjList[MAX _VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; typedef struct { int data[MAX_VERTEX_ NUM+10]; int front; int rear; }queue; int visited[MAX_VERTE X_NUM]; queue q; int main() { ALGraph G; int CreateUDG(ALGraph &G); int DeleteUDG(ALGraph &G); int InsertUDG(ALGraph &G); void BFSTraverse(ALGrap h G, int (*Visit)(ALGraph 分别以邻接矩阵和邻接表作为图的存储结构，给出连通图的深度优先 遍历的递归算法 算法思想： （1）访问出发点vi，并将其标记为已访问过。 （2）遍历vi的的每一个邻接点vj，若vi未曾访问过，则以vi为新的出发点继续进行深度优先遍历。 算法实现： Boolean visited[max]; // 访问标志数 void DFS(Graph G, int v) { // 算法7.5从第v个顶点出发递归地深度优先遍历图G int w; visited[v] = TRUE; printf("%d ",v); // 访问第v个顶点for (w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w)) if (!visited[w]) // 对v的尚未访问的邻接顶点w递归调用DFS DFS(G, w); } /*****************************************************/ /*以邻接矩阵作为存储结构*/ DFS1(MGraph G,int i) {int j; visited[i]=1; printf("%c",G.vexs[i]); for(j=1;j<=G.vexnum;j++) if(!visited[j]&&G.arcs[i][j]==1) DFS1(G,j); } /*以邻接表作为存储结构*/ DFS2(ALGraph G,int i) {int j; ArcPtr p; visited[i]=1; printf("%c",G.vertices[i].data); for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc) {j=p->adjvex; if(!visited[j]) DFS2(j); } } 1.实验目的 通过上机实验进一步掌握图的存储结构及基本操作的实现。 2.实验内容与要求 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。 3.数据结构设计 逻辑结构：图状结构 存储结构：顺序存储结构、链式存储结构 4.算法设计 #include int vexnum,arcnum; }ALGraph; typedef struct { int data[MAX_VERTEX_NUM+10]; int front; int rear; }queue; int visited[MAX_VERTEX_NUM]; queue q; int main() { ALGraph G; int CreateUDG(ALGraph &G); int DeleteUDG(ALGraph &G); int InsertUDG(ALGraph &G); void BFSTraverse(ALGraph G, int (*Visit)(ALGraph G,ArcNode v)); int PrintElement(ALGraph G,ArcNode v); void menu(); void depthfirstsearch(ALGraph *g,int vi); void travel(ALGraph *g); void breadfirstsearch(ALGraph *g); int i; G.arcnum = G.vexnum = 0; while(1) { menu(); do { printf ( "请输入要进行的操作\n" ); scanf ("%d",&i); if (i<1||i>6) printf("错误数字，请重新输入\n"); }while (i<1||i>6); switch (i) { case 1: CreateUDG(G);邻接表存储结构建立无向图
数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系
数据结构与算法复习题及参考答案
数据结构与算法第6章图答案
实验三 图的存储结构及各种运算的实现
实验十三 图的基本操作—邻接表存储结构
数据结构实验---图的储存与遍历
图的邻接表存储结构实验报告
图的两种存储结构及基本算法
图的邻接表存储方式.
数据结构实验 - 图的储存与遍历
数据结构与算法
数据结构 图的存储、遍历与应用 源代码
《数据结构与算法》课后习题答案
图采用邻接矩阵存储结构
实现图的邻接矩阵和邻接表存储
数据结构图的存储结构及
分别以邻接矩阵和邻接表作为图的存储结构
数据结构图的存储结构及基本操作