实现图的邻接矩阵和邻接表存储

实现图的邻接矩阵和邻接表存储

1．需求分析

对于下图所示的有向图G，编写一个程序完成如下功能：

1．建立G的邻接矩阵并输出之

2．由G的邻接矩阵产生邻接表并输出之

3．再由2的邻接表产生对应的邻接矩阵并输出之

2．系统设计

1．图的抽象数据类型定义：

ADT Graph{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集

数据关系R：

R={VR}

VR={|v,w∈V且P(v,w),表示从v到w的弧，

谓词P(v,w)定义了弧的意义或信息}

基本操作P：

CreatGraph(&G,V,VR)

初始条件：V是图的顶点集，VR是图中弧的集合

操作结果：按V和VR的定义构造图G

DestroyGraph(&G)

初始条件：图G存在

操作结果：销毁图G

InsertV ex(&G,v)

初始条件：图G存在，v和图中顶点有相同特征

操作结果：在图G中增添新顶点v

……

InsertArc(&G,v,w)

初始条件：图G存在，v和w是G中两个顶点

操作结果：在G中增添弧，若G是无向的则还增添对称弧

……

DFSTraverse(G,V isit())

初始条件：图G存在，V isit是顶点的应用函数

操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数V isit一次且仅一次。

一旦Visit()失败，则操作失败

BFSTraverse(G,V isit())

初始条件：图G存在，V isit是顶点的应用函数

操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数V isit一次且仅一次。一旦Visit()失败，则操作失败

}ADT Graph

2．主程序的流程：

调用CreateMG函数创建邻接矩阵M；

调用PrintMatrix函数输出邻接矩阵M

调用CreateMGtoDN函数，由邻接矩阵M创建邻接表G

调用PrintDN函数输出邻接表G

调用CreateDNtoMG函数，由邻接表M创建邻接矩阵N

调用PrintMatrix函数输出邻接矩阵N

3．函数关系调用图：

3．调试分析

（1）在MGraph的定义中有枚举类型

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

赋值语句G.kind(int)=M.kind(GraphKind);是正确的，而反过来M.kind=G.kind则是错误的，要加上那个强制转换M.kind=GraphKind(G.kind);枚举类型enum{DG,DN,UDG,UDN}

会自动赋值DG=0；DN=1，UDG=2，UDN=3；可以自动从GraphKind类型转换到int型，但不会自动从int型转换到GraphKind类型

（2）算法的时间复杂度分析：

CreateMG、CreateMGtoDN、CreateDNtoMG、PrintMatrix、PrintDN的时间复杂度均为O(n2) n为图的顶点数，所以main：T(n)= O(n2)

4．测试结果

用需求分析中的测试数据

输入：

输出：

5、用户手册

（1）输入顶点数和弧数；

（2）输入顶点内容；

（3）按行序输入邻接矩阵，输入各弧相应权值

（4）回车输出邻接矩阵M、邻接表G和邻接矩阵N

6、附录

源程序：

#include

#include

#define MAX_VERTEX_NUM 20

typedef int VRType;

typedef int InfoType;

typedef int V ertexType;

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

VRType adj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻；

//对带权图则为权值类型

InfoType *info;//该弧相关信息的指针

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{

V ertexType vexs[MAX_VERTEX_NUM];//顶点向量

AdjMatrix arcs;//邻接矩阵

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

GraphKind kind;//图的种类标志

}MGraph;

void CreateMG(MGraph &M){

int i,j;

M.kind=DN;

printf("输入顶点数:");

scanf("%d",&M.vexnum);

printf("输入弧数:");

scanf("%d",&M.arcnum);

printf("输入顶点:\n");

for(i=0;i

scanf("%d",&M.vexs[i]);

printf("建立邻接矩阵:\n");

for(i=0;i

for(j=0;j

scanf("%d",&M.arcs[i][j].adj);

printf("输入相应权值:\n");

for(i=0;i

for(j=0;j

if(M.arcs[i][j].adj){

scanf("%d",&M.arcs[i][j].info);

}

}

typedef struct ArcNode{

int adjvex;//该弧所指向的顶点在数组中的下标

struct ArcNode *nextarc;

InfoType *info;//该弧相关信息的指针

}ArcNode;

typedef struct VNode{

V ertexType data;//顶点信息

ArcNode *firstarc;//指向第一条依附该顶点的弧的指针

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{

AdjList vertices;

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

int kind;//图的种类标志

}ALGraph;

void PrintDN(ALGraph G){

int i;ArcNode *p;

printf("顶点:\n");

for(i=0;i

printf("%2d",G.vertices[i].data);

printf("\n弧:\n");

for(i=0;i

p=G.vertices[i].firstarc;

while(p){

printf("%d→%d(%d)\t",i,p->adjvex,p->info);

p=p->nextarc;

}

printf("\n");

}//for

}

void CreateMGtoDN(ALGraph &G,MGraph M){

//采用邻接表存储表示,构造有向图G(G.kind=DN)

int i,j;ArcNode *p;

G.kind=M.kind;

G.vexnum=M.vexnum;

G.arcnum=M.arcnum;

for(i=0;i

G.vertices[i].data=M.vexs[i];

G.vertices[i].firstarc=NULL;//初始化指针

}

for(i=0;i

for(j=0;j

if(M.arcs[i][j].adj==1){

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=M.arcs[i][j].info;

G.vertices[i].firstarc=p;

}

}

void CreateDNtoMG(MGraph &M,ALGraph G){

int i,j;ArcNode *p;

M.kind=GraphKind(G.kind);

M.vexnum=G.vexnum;

M.arcnum=G.arcnum;

for(i=0;i

M.vexs[i]=G.vertices[i].data;

for(i=0;i

p=G.vertices[i].firstarc;

while(p){

M.arcs[i][p->adjvex].adj=1;

p=p->nextarc;

}//while

for(j=0;j

if(M.arcs[i][j].adj!=1)

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

}//for

}

void PrintMatrix(MGraph M){ int i,j;

for(i=0;i

}

}

void main(){

MGraph M,N;ALGraph G; CreateMG(M);

PrintMatrix(M); CreateMGtoDN(G,M); PrintDN(G); CreateDNtoMG(N,G); PrintMatrix(N);

}

邻接表存储结构建立无向图

//算法功能：采用邻接表存储结构建立无向图 #include #include #define OK 1 #define NULL 0 #define MAX_VERTEX_NUM 20 // 最大顶点数 typedef int Status; //函数的类型，其值是函数结果状态代码 typedef char VertexType; typedef int VRType; typedef int InforType; typedef struct ArcNode { int adjvex; //该边所指的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针 int weight; //边的权 }ArcNode; //表的结点 typedef struct VNode { VertexType data; //顶点信息（如数据等） ArcNode *firstarc; //指向第一条依附该顶点的边的弧指针}VNode, AdjList[MAX_VERTEX_NUM]; //头结点 typedef struct ALGraph { AdjList vertices; int vexnum, arcnum; //图的当前顶点数和弧数 }ALGraph; //返回顶点v在顶点向量中的位置 int LocateVex(ALGraph G, char v) { int i; for(i = 0; v != G.vertices[i].data && i < G.vexnum; i++) ; if(i >= G.vexnum) return -1;

数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系

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、顺序队列(主要是循

邻接表存储表示

邻接表存储表示 Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf("%d",&v); if(v<0) return ERROR; G.vexnum=v; scanf("%d",&a); if(a<0) return ERROR; G.arcnum=a; for(m=0;mnextarc;q=q->nextarc); q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList 邻接多重表存储表示 Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表 { InitAMLGraph(G); scanf("%d",&v); if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(%d",&a); if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m

图的两种存储结构及基本算法

一、图的邻接矩阵存储 1.存储表示 #define vexnum 10 typedef struct{ vextype vexs[vexnum]; int arcs[vexnum][vexnum]; }mgraph; 2.建立无向图的邻接矩阵算法 void creat(mgraph *g, int e){ for(i=0;ivexs[i]); for(i=0;iarcs[i][j]=0; for(k=0;karcs[i][j]=1; g->arcs[j][i]=1;} } 3.建立有向图的邻接矩阵算法 void creat(mgraph *g, int e){ for(i=0;ivexs[i]);

for(i=0;iarcs[i][j]=0; for(k=0;karcs[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;

实验十三 图的基本操作—邻接表存储结构

浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十三图的基本操作—邻接表存储结构 学生姓名专业班级学号 实验成绩指导老师（签名）日期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 #include #include V0 V1 V4 V3 V2 ??? ? ??? ? ????????=010000000101010 1000100010A 1 0 1 0 3 3 4

#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;in;i++) scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1])); for (i = 0;in;i++) for (j = 0;jn;j++) GA->edge[i][j] = 0; for (k = 0;ke;k++) { printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edge[i][j] = w; } return(GA); } void dfs(Graph *GA, int v) { int i; printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;

图的邻接表存储结构实验报告

《图的邻接表存储结构实验报告》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;iv;i++)//建立顶点表 { printf("请输入图第%d个元素:",i+1); scanf("%s",&G->List[i].name);//读入顶点信息 G->List[i].fnext=NULL;//边表置为空表 } for(k=0;ke;k++)//建立边表--建立了2倍边的结点{ printf("请输入边的两顶点序号：（从0考试）"); scanf("%d%d",&i,&j);//读入边（Vi,Vj）的顶点对序号 s=(node *)malloc(sizeof(node));//生成边表结点 s->adj=j; s->next=G->List[i].fnext; G->List[i].fnext=s;//将新结点*s插入顶点Vi的边表头部s=(node *)malloc(sizeof(node)); s->adj=i;//邻接点序号为i s->next=G->List[j].fnext; G->List[j].fnext=s;// 将新结点*s插入顶点Vj的边表头部} return G;

图的邻接表存储方式.

图的邻接表存储方式——数组实现初探 焦作市外国语中学岳卫华在图论中，图的存储结构最常用的就是就是邻接表和邻接矩阵。一旦顶点的个数超过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 【题目描述】

实现图的邻接矩阵和邻接表存储

实现图的邻接矩阵和邻接表存储 1．需求分析 对于下图所示的有向图G，编写一个程序完成如下功能： 1．建立G的邻接矩阵并输出之 2．由G的邻接矩阵产生邻接表并输出之 3．再由2的邻接表产生对应的邻接矩阵并输出之 2．系统设计 1．图的抽象数据类型定义： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集 数据关系R： R={VR} VR={|v,w∈V且P(v,w),表示从v到w的弧， 谓词P(v,w)定义了弧的意义或信息} 基本操作P： CreatGraph(&G,V,VR) 初始条件：V是图的顶点集，VR是图中弧的集合 操作结果：按V和VR的定义构造图G DestroyGraph(&G) 初始条件：图G存在 操作结果：销毁图G InsertVex(&G,v) 初始条件：图G存在，v和图中顶点有相同特征 操作结果：在图G中增添新顶点v …… InsertArc(&G,v,w) 初始条件：图G存在，v和w是G中两个顶点 操作结果：在G中增添弧，若G是无向的则还增添对称弧 …… DFSTraverse(G,Visit()) 初始条件：图G存在，Visit是顶点的应用函数 操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。

一旦Visit()失败，则操作失败 BFSTraverse(G,Visit()) 初始条件：图G存在，Visit是顶点的应用函数 操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败 }ADT Graph 2．主程序的流程： 调用CreateMG函数创建邻接矩阵M； 调用PrintMatrix函数输出邻接矩阵M 调用CreateMGtoDN函数，由邻接矩阵M创建邻接表G 调用PrintDN函数输出邻接表G 调用CreateDNtoMG函数，由邻接表M创建邻接矩阵N 调用PrintMatrix函数输出邻接矩阵N 3．函数关系调用图： 3．调试分析 （1）在MGraph的定义中有枚举类型 typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网} 赋值语句G.kind(int)=M.kind(GraphKind);是正确的，而反过来M.kind=G.kind则是错误的，要加上那个强制转换M.kind=GraphKind(G.kind);枚举类型enum{DG,DN,UDG,UDN} 会自动赋值DG=0；DN=1，UDG=2，UDN=3；可以自动从GraphKind类型转换到int型，但不会自动从int型转换到GraphKind类型

数据结构实验 - 图的储存与遍历

一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 三、附录： 在此贴上调试好的程序。 #include #include #include ????????????????=010******* 010101000100010A

#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;in;i++) scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1])); for (i = 0;in;i++) for (j = 0;jn;j++) GA->edge[i][j] = 0; for (k = 0;ke;k++) { printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edge[i][j] = w; } return(GA); } void dfs(Graph *GA, int v) { int i; printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;

邻接表表示的带权有向图(网)

===实习报告一“邻接表表示的带权有向图（网）”演示程序=== （一）、程序的功能和特点 1. 程序功能：建立有向图的带权邻接表，能够对建立的邻接表进行添加顶点，添加边和删除顶点，删除边的操作，并能显示输出邻接表。 2. 程序特点：采用java面向对象语言，对边，顶点和邻接表用类进行封装。采用链式存储结构。 （二八程序的算法设计 算法一：“插入一个顶点”算法： 1. 【逻辑结构与存储结构设计】 逻辑结构：线性结构。存储结构：顺序存储与链式存储结合。 邻接表（Adjacency List）是图的一种顺序存储与链式存储结合的存储方法。。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。如下图就是一个临界表的存储图。 vertex firstedge adjvex n ext 序号vertex firstedge 图的邻接表表示在邻接表表示中有两种结点 结构，如图所示。 邻接矩阵表示的结点结构

顶点域边指针 流程示意图：顶点数据组成的数组 顶点数组表的顺序存储: V0 V1— V2— O 2.【基本操作设计】 文字说明： （1） .首先判断顶点表是否满。 （2） .若满则插入失败，放回false 。 （3） .顶点表若不满，创建新顶点，将新顶点加入顶点表 （4） .插入顶点成功，返回true 。

添加顶点前状态 添加顶点v2后 网图的边表结构 //插入一个顶点 public boolea n In sertVertex ( char vertex ){ if (NumVertices ==MaxVertices ) return false ; // 顶点表满 Vertex t= n ewVertex(); t. data =vertex; t. adj =null ; NodeTable[ NumVertices ]=t; NumVertices++; //注明：企图以下赋值不合Java 语法 〃NodeTable[NumVertices].data=vertex; 〃NodeTable[NumVertices].adj=null; return true ; } 算法二：“插入一条边”算法： 1. 【逻辑结构与存储结构设计】 逻辑结构：线性结构。 存储结构：链式存储结构 网图的边表结构如图所示。 邻接点域 4.【高级语言代码】

数据结构 图的存储、遍历与应用 源代码

实验四图的存储、遍历与应用姓名：班级： 学号：日期：一、实验目的： 二、实验内容： 三、基本思想，原理和算法描述:

四、源程序： （1）邻接矩阵的存储： #include #include #define INFINITY 10000 //定义最大值无穷大 #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef int AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM ]; typedef struct{ int vexs[MAX_VERTEX_NUM ]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧或边数 }MGraph; void CreatGragh(MGraph G) //用邻接矩阵构造图 { int i,j,k,w; printf("请输入顶点个数和边数:\n"); scanf("%d %d",&G.vexnum,&G.arcnum); printf("请按顺序输入顶点中间用‘空格’间隔\n"); for(i=0;i #include

实现图的邻接矩阵和邻接表存储

#include #include #define MAXV 100 //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 int info; //顶点其余的信息 }VertexType; typedef struct { int edges[MAXV][MAXV]; //邻接矩阵 int n,e; //顶点数，弧数 VertexType vexs[MAXV]; //存放顶点信息 }MGraph; //一下定义邻接表类型 typedef struct ANode //弧的节点结构类型 { int adjvex; //该弧的终点位置 struct ANode *nextarc; int info; //弧的相关信息 } ArcNode; typedef struct Vnode //邻接表头结点类型 { int data; //顶点信息 ArcNode *firstarc; //指向第一条弧 }VNode; typedef VNode AdjList[MAXV]; typedef struct { AdjList adjlist; int n,e; }ALGraph; void MatToList(MGraph g,ALGraph *&G) //将邻接矩阵 g 转换为邻接表 G { int i,j,n=g.n; ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph)); for(i=0;iadjlist[i].firstarc=NULL; for(i=0;i=0;j--) if(g.edges[i][j]) { p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=g.edges[i][j]; p->nextarc=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p;

实验六 图的邻接表存储及遍历

实验六图的邻接表存储及遍历 一、实验学时 2学时 二、背景知识 1．图的邻接表存储结构 在图的邻接表中，图中每个顶点都建立一个单链表，第i个单链表中的结点数为顶点i的出度。(逆邻接表中，第i个单链表中的结点数为顶点i的入度) 邻接表的数据结构描述为： struct node { int vertex; struct node *nextnode; }; typedef struct node *graph; struct node head[vertexnum]; 2.图的遍历 深度优先遍历（DFS）法： 算法步骤： 1）初始化： （1）置所有顶点“未访问”标志； （2）打印起始顶点； （3）置起始顶点“已访问”标志； （4）起始顶点进栈。 2）当栈非空时重复做： （1）取栈顶点； （2）如栈顶顶点存在未被访问过的邻接顶点，则选择第一个顶点做： ①打印该顶点； ②置顶点为“已访问”标志； ③该顶点进栈； 否则，当前栈顶顶点退栈。 3）结束。 广度优先遍历（BFS）法： 算法步骤： 1) 初始化： （1）置所有顶点“未访问”标志； （2）打印起始顶点； （3）置起始顶点“已访问”标志； （4）起始顶点入队。 2）当队列非空时重复做： （1）取队首顶点； （2）对与队首顶点邻接的所有未被访问的顶点依次做： ①打印该顶点； ②置顶点为“已访问”标志； ③该顶点入队； 否则，当前队首顶点出队。 3) 结束。

三、目的要求 1．掌握图的基本存储方法； 2．掌握有关图的操作算法并用高级语言实现； 3．熟练掌握图的两种搜索路径的遍历方法。 四、实验内容 1．编写程序实现下图的邻接表表示及其基础上的深度和广度优先遍历。 五、程序实例 图的邻接表表示法的C语言描述： #include #include struct node /* 图形顶点结构定义 */ { int vertex; /* 顶点 */ struct node *nextnode; /* 指下一顶点的指针 */ }; typedef struct node *graph; /* 图形的结构重定义 */ struct node head[6]; /* 图形顶点结构数组 */ /*----------建立图形--------*/ void creategraph(int *node,int num) { graph newnode; /* 新顶点指针 */ graph ptr; int from; /* 边线的起点 */ int to; /* 边线的终点 */ int i; for ( i = 0; i < num; i++ ) /* 读取边线的回路 */ { from = node[i*2]; /* 边线的起点 */ to = node[i*2+1]; /* 边线的终点 */ /* 申请存储新顶点的内存空间 */ newnode = ( graph ) malloc(sizeof(struct node)); newnode->vertex = to; /* 建立顶点内容 */ newnode->nextnode = NULL; /* 设定指针初值 */ ptr = &(head[from]); /* 顶点位置 */ while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */ ptr = ptr->nextnode; /* 下一个顶点 */ ptr->nextnode = newnode; /* 插入结尾 */ } }

数据结构图的存储结构及

数据结构图的存储结构及基本操作

1.实验目的 通过上机实验进一步掌握图的存储结构及基本操作的实现。 2.实验内容与要求 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。 3.数据结构设计 逻辑结构：图状结构 存储结构：顺序存储结构、链式存储结构 4.算法设计 #include #include #include #define MAX_VERTEX_NU M 20 typedef struct ArcNode { int adjvex; struct ArcNode *nextarc;

}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 #include #include #define MAX_VERTEX_NUM 20 typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; }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_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);

邻接表存储结构建立无向图

ata && i < ; i++) ; if(i >= return -1; return i; } ata); irstarc = NULL; getchar(); } char v1, v2; for(int k = 0; k < ; k++) { printf("输入第 %d 条边依附的顶点v1: ", k+1); scanf("%c", &v1); getchar(); printf("输入第 %d 条边依附的顶点v2: ", k+1); scanf("%c", &v2); getchar(); int i = LocateVex(G, v1); int j = LocateVex(G, v2); irstarc; [i].firstarc =s; t->adjvex = i; irstarc; [j].firstarc =t;

} return OK; } Status PrintAdjList(ALGraph &G) { ArcNode *p; printf("%4s%6s%12s\n", "编号", "顶点", "相邻边编号"); for(int i = 0; i < ; i++) { printf("%4d%6c", i, [i].data); for(p = [i].firstarc; p; p = p->nextarc) printf("%4d", p->adjvex); printf("\n"); } return OK; } int main() { ALGraph G; CreateUDN(G); rintAdjList(G); return 0; }

2-深度优先遍历以邻接表存储的图-实验报告

福建江夏学院 《数据结构与关系数据库（本科）》实验报告姓名班级学号实验日期 课程名称数据结构与关系数据库（本科）指导教师成绩 实验名称：深度优先遍历以邻接表存储的图 一、实验目的 1、掌握以邻接表存储的图的深度优先遍历算法； 二、实验环境 1、硬件环境：微机 2、软件环境：Windows XP，VC6.0 三、实验内容、步骤及结果 1、实验内容： 基于图的深度优先遍历编写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。 2、代码： #include #include #define MaxVertexNum 100 /*最大顶点数为100*/ typedef char VertexType; typedef struct node{ /*边表结点*/ int adjvex; /*邻接点域*/ struct node * next; /*指向下一个邻接点的指针域*/ /*若要表示边上信息，则应增加一个数据域info*/ }EdgeNode; typedef struct vnode{ /*顶点表结点*/ VertexType vertex; /*顶点域*/ EdgeNode * firstedge; /*边表头指针*/ }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; /*AdjList 是邻接表类型*/ typedef struct{ AdjList adjlist; /*邻接表*/ int n,e; /*顶点数和边数*/ }ALGraph; /*ALGraph 是以邻接表方式存储的图类型*/ bool visited[MaxVertexNum]; void CreateALGraph(ALGraph *G)