图的邻接矩阵和邻接表相互转换

图的邻接矩阵和邻接表相互转换

图的邻接矩阵存储方法具有如下几个特征：1)无向图的邻接矩阵一定是一个对称矩阵。

2）对于无向图的邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的度()i v TD 。3）对于有向图，邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的出度()i v OD （或入度

()i v ID ）

。4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所发费得时间代价大。

邻接表是图的一种顺序存储与链式存储相结合的存储方法。若无向图中有n 个顶点、e 条边，则它的邻接表需n 个头结点和2e 个表结点。显然，在边稀疏的情况下，用邻接表表示图比邻接矩阵存储空间。在无向图的邻接表中，顶点i v 的度恰好是第i 个链表中的结点数，而在有向图中，第i 个链表中结点个数是顶点i v 的出度。

在建立邻接表或邻逆接表时，若输入的顶点信息即为顶点的编号，则建立临接表的时间复杂度是)(e n O +；否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为)*(e n O 。在邻接表上容易找到任意一顶点的第一个邻接点和下一个邻接点，但要判断任意两个顶点之间是否有边或弧，则需要搜索第i 个或第j 个链表，因此，不及邻接矩阵方便。

邻接矩阵和邻接表相互转换程序代码如下：

#include

#define MAX 20

//图的邻接表存储表示

typedef struct ArcNode{

int adjvex; //弧的邻接定点

char info; //邻接点值

struct ArcNode *nextarc; //指向下一条弧的指针

}ArcNode;

typedef struct Vnode{ //节点信息

char data;

ArcNode *link;

}Vnode,AdjList[MAX];

typedef struct{

AdjList vertices;

int vexnum; //节点数

int arcnum; //边数

}ALGraph;

//图的邻接矩阵存储表示

typedef struct{

int n; //顶点个数

char vexs[MAX]; //定点信息

int arcs[MAX][MAX]; //边信息矩阵

}AdjMatrix;

/***_____________________________________________________***/

//函数名：AdjListToMatrix(AdjList g1,AdjListMatrix &gm,int n)

//参数：（传入）AdjList g1图的邻接表,（传入）int n顶点个数，（传出）AdjMatrix gm图的邻接矩阵

//功能：把图的邻接表表示转换成图的邻接矩阵表示

void AdjListToAdjMatrix(ALGraph gl,AdjMatrix &gm){

int i,j,k;

ArcNode *p;

gm.n=gl.vexnum;

for(k=0;k

gm.vexs[k]=gl.vertices[k].data;

for(i=0;i

for(j=0;j

gm.arcs[i][j]=0;

for(i=0;i

p=gl.vertices[i].link; //取第一个邻接顶点

while(p!=NULL){ //取下一个邻接顶点

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

p=p->nextarc;

}

}

}

/***________________________________________________***/

//函数名：AdjMatrixToAdjList

void AdjMatrixToAdjList(AdjMatrix gm,ALGraph &gl){

int i,j,k,choice;

ArcNode *p;

k=0;

gl.vexnum=gm.n;

cout<<"请选择所建立的图形是无向图或是有向图：";

cin>>choice;

for(i=0;i

gl.vertices[i].link=NULL;

}

for(i=0;i

for(j=0;j

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

k++;p=new ArcNode;

p->adjvex=j;p->info=gm.vexs[j];p->nextarc=gl.vertices[i].link;

gl.vertices[i].link=p;

}

if(choice==1)

k=k/2;

gl.arcnum=k;

}

void CreateAdjList(ALGraph &G){

int i,s,d,choice;

ArcNode *p;

cout<<"请选择所建立的图形是有向图或是无向图：";

cin>>choice;

cout<<"请输入节点数和边数："<

cin>>G.vexnum>>G.arcnum;

for(i=0;i

cout<<"第"<

cin>>G.vertices[i].data;

G.vertices[i].link=NULL;

}

if(choice==1){

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

cout<<"边----起点序号，终点序号：";

cin>>s>>d;

p=new ArcNode;

p->adjvex=d;

p->info=G.vertices[d].data;

p->nextarc=G.vertices[s].link;

G.vertices[s].link=p;

}

}

else{

for(i=0;i

cout<<"边----起点序号，终点序号：";

cin>>s>>d;

p=new ArcNode;

p->adjvex=d;

p->nextarc=G.vertices[s].link;

G.vertices[s].link=p;

}

}

}

void CreateAdjMatrix(AdjMatrix &M){

int i,j,k,choice;

cout<<"请输入顶点个数：";

cin>>M.n;

cout<<"请输入如顶点信息:"<

for(k=0;k

cin>>M.vexs[k];

cout<<"请选择所建立的图形是无向图或是有向图：";

cin>>choice;

cout<<"请输入边信息："<

for(i=0;i

for(j=0;j

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

switch(choice){

case 1:{for(k=0;k

cin>>i>>j;M.arcs[i][j]=M.arcs[j][i]=1;

}

};break;

case 2:{for(k=0;k

cin>>i>>j;M.arcs[i][j]=1;

}

};break;

}

}

void OutPutAdjList(ALGraph &G){

int i;ArcNode *p;

cout<<"图的邻接表如下："<

for(i=0;i

cout<

p=G.vertices[i].link;

while(p!=NULL){

cout<<"---->("<adjvex<<" "<info<<")";

p=p->nextarc;

}

cout<

}

}

void OutPutAdjMatrix(AdjMatrix gm){

cout<<"图的邻接矩阵如下："<

for(int i=0;i

for(int j=0;j

cout<

cout<

}

}

void main(){

ALGraph gl1,gl2;

AdjMatrix gm1,gm2;

CreateAdjList(gl1);

AdjListToAdjMatrix(gl1,gm1);

OutPutAdjList(gl1);OutPutAdjMatrix(gm1);

CreateAdjMatrix(gm2);

AdjMatrixToAdjList(gm2,gl2);

OutPutAdjList(gl2);OutPutAdjMatrix(gm2); }

图的邻接矩阵和邻接表相互转换

图的邻接矩阵和邻接表相互转换 图的邻接矩阵存储方法具有如下几个特征：1)无向图的邻接矩阵一定是一个对称矩阵。 2）对于无向图的邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的度()i v TD 。3）对于有向图，邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的出度()i v OD （或入度 ()i v ID ） 。4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所发费得时间代价大。 邻接表是图的一种顺序存储与链式存储相结合的存储方法。若无向图中有n 个顶点、e 条边，则它的邻接表需n 个头结点和2e 个表结点。显然，在边稀疏的情况下，用邻接表表示图比邻接矩阵存储空间。在无向图的邻接表中，顶点i v 的度恰好是第i 个链表中的结点数，而在有向图中，第i 个链表中结点个数是顶点i v 的出度。 在建立邻接表或邻逆接表时，若输入的顶点信息即为顶点的编号，则建立临接表的时间复杂度是)(e n O +；否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为)*(e n O 。在邻接表上容易找到任意一顶点的第一个邻接点和下一个邻接点，但要判断任意两个顶点之间是否有边或弧，则需要搜索第i 个或第j 个链表，因此，不及邻接矩阵方便。 邻接矩阵和邻接表相互转换程序代码如下： #include #define MAX 20 //图的邻接表存储表示 typedef struct ArcNode{ int adjvex; //弧的邻接定点 char info; //邻接点值 struct ArcNode *nextarc; //指向下一条弧的指针 }ArcNode; typedef struct Vnode{ //节点信息 char data; ArcNode *link; }Vnode,AdjList[MAX]; typedef struct{ AdjList vertices; int vexnum; //节点数 int arcnum; //边数

图的矩阵表示及习题-答案讲解

177 图的矩阵表示 图是用三重组定义的，可以用图形表示。此外，还可以用矩阵表示。使用矩阵表示图，有利于用代数的方法研究图的性质，也有利于使用计算机对图进行处理。矩阵是研究图的重要工具之一。本节主要讨论无向图和有向图的邻接矩阵、有向图的可达性矩阵、无向图的连通矩阵、无向图和有向图的完全关联矩阵。 定义9.4.1 设 G =是一个简单图，V =?v 1,v 2,…,v n ? A (G )=(ij a ) n ×n 其中： 1j i v v v v a j i j i ij =???=无边或到有边到 i ,j =1,…,n 称A (G )为G 的邻接矩阵。简记为A 。 例如图9.22的邻接矩阵为： ?????? ? ? ?=011110101101 1010)(G A 又如图9.23(a)的邻接矩阵为： ?????? ? ? ?=0001101111000010 )(G A 由定义和以上两个例子容易看出邻接矩阵具有以下性质： ①邻接矩阵的元素全是0或1。这样的矩阵叫布尔矩阵。邻接矩阵是布尔矩阵。 ②无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。

178 ③邻接矩阵与结点在图中标定次序有关。例如图9.23(a)的邻接矩阵是A (G )，若将图9.23(a)中的接点v 1和v 2的标定次序调换，得到图9.23(b)，图9.23(b)的邻接矩阵是A ′(G )。 ?????? ? ? ?='001010110001 1100)(G A 考察A (G )和A ′(G )发现，先将A (G )的第一行与第二行对调，再将第一列与第二列对调可 得到A ′(G )。称A ′(G )与A (G )是置换等价的。 一般地说，把n 阶方阵A 的某些行对调，再把相应的列做同样的对调，得到一个新的n 阶方阵A ′，则称A ′与A 是置换等价的。可以证明置换等价是n 阶布尔方阵集合上的等价关系。 虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。 ④对有向图来说，邻接矩阵A (G )的第i 行1的个数是v i 的出度， 第j 列1的个数是v j 的入度。 ⑤零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。 设G =为有向图，V =?v 1,v 2,…,v n ?，邻接矩阵为A =(a ij )n ×n 若a ij =1，由邻接矩阵的定义知，v i 到v j 有一条边，即v i 到v j 有一条长度为1的路；若a ij =0，则v i 到v j 无边，即v i 到v j 无长度为1的路。故a ij 表示从v i 到v j 长度为1的路的条数。 设A 2=AA ，A 2=(2 ij a )n ×n ，按照矩阵乘法的定义， nj in j i j i ij a a a a a a a +++= 22112 若a ik a kj =1，则a ik =1且a kj =1，v i 到v k 有边且v k 到v j 有边，从而v i 到v j 通过v k 有一条长 度为2的路；若 kj ik a a =0，则a ik =0或a kj =0，v i 到v k 无边或v k 到v j 无边，因而v i 到v j 通过 v k 无长度为2的路，k =1,…,n 。故2 ij a 表示从v i 到v j 长度为2的路的条数。 设A 3=AA 2，A 3=(3 ij a ) n ×n ，按照矩阵乘法的定义， 22222113nj in j i j i ij a a a a a a a +++= 若2kj ik a a ≠0，则ik a =1且2kj a ≠0，v i 到v k 有边且v k 到v j 有路，由于2kj a 是v k 到v j 长度为2 的路的条数，因而2kj ik a a 表示v i 到v j 通过v k 长度为3的路的条数；若2kj ik a a =0, ik a =0或2kj a =0， 则v i 到v k 无边或v k 到v j 无长度为2的路，所以v i 到v j 通过v k 无路，k =1,…,n 。故3 ij a 表示从v i 到v j 长度为3的路的条数。 …… 可以证明，这个结论对无向图也成立。因此有下列定理成立。 定理9.4.1 设A (G )是图G 的邻接矩阵，A (G )k =A (G )A (G )k-1，A (G )k 的第i 行，第j 列元素 k ij a 等于从v i 到v j 长度为k 的路的条数。其中k ii a 为v i 到自身长度为k 的回路数。 推论 设G =是n 阶简单有向图，A 是有向图G 的邻接矩阵，B k =A ＋A 2＋…＋A k ，

经典代码之图 邻接表转换成邻接矩阵

运行结果是： 请输入节点数和弧数:3 3 第1 个节点信息:5 第2 个节点信息:6 第3 个节点信息:7 第1 条弧的弧尾和弧头的位置:1 2 第2 条弧的弧尾和弧头的位置:2 3 第3 条弧的弧尾和弧头的位置:1 3 图的邻接表表示为： [1,5]-->[3,7]-->[2,6]-->^ [2,6]-->[3,7]-->[1,5]-->^ [3,7]-->[1,5]-->[2,6]-->^ 交换后是:: 图的邻接矩阵表示为： 0 1 1 1 0 1 1 1 0 请按任意键继续. . . 代码是： #include #include #define MAXV 100 typedef struct { int no; int info; }vertextype; typedef struct { int num; int edges[MAXV][MAXV]; // vertextype vexs[MAXV]; }mgraph; struct arcnode { int adjvex; int info;

struct arcnode *nextarc; }; struct vexnode { int data; struct arcnode *firstarc; }; struct graph { int vexnum,arcnum; vexnode vexpex[100]; }; struct graph *creatgraph() { int i,s,d; struct graph *g; struct arcnode *p,*q; g = (struct graph *)malloc(sizeof(struct graph)); printf("请输入节点数和弧数:"); scanf("%d%d", &g->vexnum, &g->arcnum); for(i=1; i<=g->vexnum; i++) { printf("第%d 个节点信息:",i); scanf("%d", &g->vexpex[i].data); g->vexpex[i].firstarc = NULL; } for(i=1; i<=g->arcnum; i++) { p = (struct arcnode *)malloc(sizeof(struct arcnode)); q = (struct arcnode *)malloc(sizeof(struct arcnode)); printf("第%d 条弧的弧尾和弧头的位置:",i); scanf("%d%d",&s,&d); p->adjvex = d; p->info = g->vexpex[d].data; p->nextarc = g->vexpex[s].firstarc; g->vexpex[s].firstarc = p; q->adjvex = s; q->info = g->vexpex[s].data; q->nextarc = g->vexpex[d].firstarc; g->vexpex[d].firstarc = q;

图的邻接矩阵存储结构建立汇总

课程名称: 《数据结构》课程设计课程设计题目:图的邻接矩阵存储结构建立 姓名:XXX 院系:计算机学院 专业:计算机科学技术 年级:11级 学号:XXXXXXXX 指导教师:XXX 2013年9月28日

目录 1 课程设计的目的 (3) 2需求分析 (3) 3 课程设计报告内容 (3) 3.1 概要设计 (3) 3.2 详细设计 (4) 3.3 调试分析 (5) 3.4 用户手册 (5) 3.5 程序清单 (5) 3.6 测试结果 (10) 4 小结 (12) 5 参考文献 (12)

1.课程设计的目的 (1) 熟练使用 C 语言编写程序，解决实际问题; (2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2.需求分析 问题描述:建立图的邻接矩阵存储结构(图的类型可以是有向图或有向网、无向图或无向网，学生可以任选一种类型)，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后给出图的DFS,BFS次序。 要求： ①先任意创建一个图； ②图的DFS,BFS的递归和非递归算法的实现。 3.课程设计报告内容 3.1概要设计 1.函数 ①主函数：main( ) ②创建无向图：CreateGraph( )

③深度优先遍历图：DFS( ) ④广度优先遍历图：BFS( ) 3.2详细设计 1.使用邻接矩阵作为图的存储结构，程序中主要用到的抽象数据类型： typedef struct { char vexs[MAX]; //顶点向量 int arcs[MAX][MAX]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数}Graph; 2.程序流程图：

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

实现图的邻接矩阵和邻接表存储 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类型

用邻接矩阵表示法创建有向图(数据结构)

#include #include #include #define MAX_VERTEX_NUM 20 //定义最多顶点个数 #define INFINITY32768 //定义无穷大 //描述图的类型，用枚举型类型来说明 typedef enum{DG,DN,UDG,UDN}GraphKind; //定义顶点数据类型 typedef char V ertexData; //定义邻接矩阵中元素值(即边信息）的数据类型 typedef int ArcNode; //定义图的邻接矩阵类型：一个顶点信息的一维数组，一个邻接矩阵、当前图中包含的顶点数、边数以及图类型（有向图、有向网、无向图、无向网） typedef struct { V ertexData vertex[MAX_VERTEX_NUM]; ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vertexnum,arcnum; GraphKind kind; } AdjMatrix;//图的邻接矩阵表示类型 int LocateV ertex(AdjMatrix *G,V ertexData v) //求顶点位置函数 { int j=-1,k; for(k=0;kvertexnum;k++) { if(G->vertex[k]==v) { return k; } } return j; } int CreateDN(AdjMatrix *G) //创建一个又向网 { int i,j,k,weight; V ertexData v1,v2; printf("输入图的顶点数和弧数，以逗号分隔\n"); //输入图的顶点数和弧数 scanf("%d,%d",&G->vertexnum,&G->arcnum); for(i=0;ivertexnum;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 【题目描述】

数据结构课程设计-图的邻接矩阵

数据结构 课程设计报告 设计题目：图的邻接矩阵存储结构 院系计算机学院 年级x 级 学生xxxx 学号xxxxxxxxxx 指导教师xxxxxxxxx 起止时间10-6/10-10 2013年10月10日

目录 1 需求分析 (4) 2 概要设计 (4) 2.1 ADT描述 (4) 2.2程序模块结构 (5) 2.3各功能模块 (6) 3详细设计 (7) 3.1类的定义 (7) 3.2 初始化 (8) 3.3 图的构建操作 (8) 3.4 输出操作 (9) 3.5 get操作 (9) 3.6 插入操作 (10) 3.7 删除操作 (100) 3.8 求顶点的度操作 (111) 3.9 深度遍历作 (11) 3.10 判断连通操作 (12) 3.11 主函数 (13) 4 调试分析 (16) 4.1调试问题 (16) 4.2 算法时间复杂度 (16) 5用户手册 (16) 5.1主界面 (16) 5.2 创建图 (17) 5.3插入节点 (17) 5.4 深度优先遍历 (17) 5.5 求各顶点的度 (18) 5.6 输出图 (18) 5.7 判断是否连通 (19) 5.8 求边的权值 (19) 5.9 插入边 (19) 5.10 删除边 (20) 结论 (20) 参考文献 (20)

摘要 随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。 首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。 关键词：网络化；计算机；对策；图；储存。

采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作

/* 采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作 */ #include "stdio.h" #include "string.h" #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Status; #define INFINITY INT_MAX /*最大值“无穷”*/ #define MAX_VERTEX_NUM 20 /*最大顶点个数*/ typedef int Boolean; typedef char VertexType[20]; typedef int VRType; /**************以下为队列的操作************/ /****队列的类型定义****/ typedef int QElemType; typedef struct QNode {QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; /****初始化队列****/ Status InitQueue(LinkQueue *Q) { (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if (!(*Q).front) exit(OVERFLOW); (*Q).front->next=NULL; return OK; } /****判断队列是否为空****/ Status QueueEmpty (LinkQueue Q) { if (Q.front==Q.rear) return TRUE; else

数据结构与算法-图的邻接矩阵

实验报告实验日期：数据结构与算法课程： 图的邻接矩阵实验名称： 一、实验目的掌握图的邻接矩阵 二、实验内容必做部分 、给出图的邻接矩阵存储结构的类型定义。1 -1。v，返回其在vexs数组中的下标，否则返回2、实现LocateVex(G,v)操作函数：若找到顶点。、实现算法7.2（构造无向网）3&G) Status CreateUDN(MGraph 设计并实现无向网的输出算法，要求能显示顶点以及顶点之间的邻接关系（方式自定）4、 并进行输出。要求给出至少两组测试数据。在主函数中调用CreateUDN创建一个无向网，5、 选做部分 类型）编写下述操作函数：基于图的邻接矩阵存储结构（即MGraph若找不到这样返回该邻接点在顶点数组中的下标；1个邻接点，1、求下标为v的顶点的第-1。的邻接点，返回int FirstAdjVex(MGraph G,int v) 的顶点的下一个邻接点，返回该邻接点的下标；若w求下标为v的顶点相对于下标为2、找不到这样的邻接点，返回-1。 int NextAdjVex(MGraph G,int v,int w) 在主函数调用上述函数，给出测试结果。 三、实验步骤 必做部分 给出图的邻接矩阵存储结构的类型定义。、 1．

2、实现LocateVex(G,v)操作函数：若找到顶点v，返回其在vexs数组中的下标，否则返回-1。 3、实现算法7.2（构造无向网）。 &G) CreateUDN(MGraph Status

设计并实现无向网的输出算法，要求能显示顶点以及顶点之间的邻接关系（方式自定）、

4． 要求给出至少两组测试数据。并进行输出。、在主函数中调用CreateUDN创建一个无向网，5

实验12 图的基本操作-邻接矩阵

浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十二图的基本操作—邻接矩阵存储结构 实验成绩指导老师（签名）日期 一.实验目的和要求 1、掌握图的存储结构：邻接矩阵。 2、学会对图的存储结构进行基本操作。 二.实验内容 1、图的邻接矩阵定义及实现：建立头文件AdjMatrix.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test5_1.cpp，编译并调试程序，直到正确运行。 2、选做：编写图的深度优先遍历函数与广度优先遍历函数，要求把这两个函数添加到头文件AdjMatrix.h中，并在主函数文件test5_1.cpp中添加相应语句进行测试。 3、填写实验报告，实验报告文件取名为report12.doc。 4、上传实验报告文件report12.doc及源程序文件test5_1.cpp、AdjMatrix.h 到Ftp服务器上自己的文件夹下。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 函数：void CreateGraph(MGraph &G, GraphKind kd) 功能：采用数组邻接矩阵表示法，构造图G 思路：按照输入值确定图的顶点数、弧数、类型，并按照类型初始化邻接矩阵，其中图的构造初值赋为0，网的构造初值赋为之前定义好的MaxValue值，再按照输入构造邻接矩阵。 函数：void PrintMGraph(MGraph &G) 功能：输出邻接矩阵 思路：根据已有矩阵信息（顶点数=行列数），控制格式进行输出 函数：void countdig(MGraph G,int comp) 功能：计算图的入度或出度

邻接表转换成邻接矩阵

请输入节点数和弧数:3 3 第1 个节点信息:5 第2 个节点信息:6 第3 个节点信息:7 第1 条弧的弧尾和弧头的位置:1 2 第2 条弧的弧尾和弧头的位置:2 3 第3 条弧的弧尾和弧头的位置:1 3 图的邻接表表示为： [1,5]-->[3,7]-->[2,6]-->^ [2,6]-->[3,7]-->[1,5]-->^ [3,7]-->[1,5]-->[2,6]-->^ 交换后是:: 图的邻接矩阵表示为： 0 1 1 1 0 1 1 1 0 请按任意键继续. . . 代码是： #include #include #define MAXV 100 typedef struct { int no; int info; }vertextype; typedef struct { int num; int edges[MAXV][MAXV]; // vertextype vexs[MAXV]; }mgraph; struct arcnode { int adjvex; int info; struct arcnode *nextarc; }; struct vexnode { int data; struct arcnode *firstarc; }; struct graph

{ int vexnum,arcnum; vexnode vexpex[100]; }; struct graph *creatgraph() { int i,s,d; struct graph *g; struct arcnode *p,*q; g = (struct graph *)malloc(sizeof(struct graph)); printf("请输入节点数和弧数:"); scanf("%d%d", &g->vexnum, &g->arcnum); for(i=1; i<=g->vexnum; i++) { printf("第%d 个节点信息:",i); scanf("%d", &g->vexpex[i].data); g->vexpex[i].firstarc = NULL; } for(i=1; i<=g->arcnum; i++) { p = (struct arcnode *)malloc(sizeof(struct arcnode)); q = (struct arcnode *)malloc(sizeof(struct arcnode)); printf("第%d 条弧的弧尾和弧头的位置:",i); scanf("%d%d",&s,&d); p->adjvex = d; p->info = g->vexpex[d].data; p->nextarc = g->vexpex[s].firstarc; g->vexpex[s].firstarc = p; q->adjvex = s; q->info = g->vexpex[s].data; q->nextarc = g->vexpex[d].firstarc; g->vexpex[d].firstarc = q; } return g; //return graph! } void changeto(graph *G, mgraph &g) { int i,j; arcnode *m; g.num = G->vexnum; for(i = 1; i<=G->vexnum; i++) for(j = 1; j<=G->vexnum; j++) g.edges[i][j] = 0;

“邻接矩阵表示的带权有向图(网)”演示程序

班级:信息1102 姓名：贾孟涛 ========实习报告十四“邻接矩阵表示的带权有向图（网）”演示程序========== （一）、程序的功能和特点 该程序可以建立有向图的带权邻接矩阵，能够对建立的邻接矩阵进行添加顶点，添加边和删除顶点，删除边的操作，并能显示输出邻接矩阵。该程序的特点是采用java面向对象语言，对边，顶点和邻接矩阵用类进行封装。采用链式存储结构。 （二）、程序的算法设计 算法一：“插入一个顶点”算法： 1.【逻辑结构与存储结构设计】 逻辑结构：线性结构。 存储结构：顺序存储与链式存储结合。 2.【基本操作设计】 文字说明： 创建新结点，找到结点L位置，在 L后插入新结点。 3.【算法设计】 文字说明： （1）.首先判断顶点表是否满。 （2）.若满则插入失败，放回false。 （3）.顶点表若不满，创建新顶点，将新顶点加入顶点表。 （4）.插入顶点成功，返回true。 4.【高级语言代码】 //插入一个顶点 public int InsertVertex ( char vertex ){ if(IsGraphFull()) return -1; //插入失败 //顶点表增加一个元素 VerticesList[CurrentVertices]=vertex; //邻接矩阵增加一行一列 for ( int j = 0;j <=CurrentVertices;j++ ) { Edge[CurrentEdges][j]=MaxValue; Edge[j][CurrentEdges]=MaxValue; } Edge[CurrentEdges][CurrentEdges]=0; CurrentVertices++; return CurrentVertices; //插入位置 }

图邻接矩阵 邻接表的建立c _数据结构课程设计

一.需求分析 1.运行环境 硬件：计算机486/64M以上 操作系统： WIN9x 以上/WIN2000/WIN XP/WIN ME 相关软件：vistualC++ 2．程序所实现的功能： （1）建立并显示图的邻接表。 （2）深度优先遍历，显示遍历结果。 （3）对该图进行拓扑排序，显示排序结果。 （4）给出某一确定顶点到所有其它顶点的最短路径。 3.程序的输入，包含输入的数据格式和说明 (1)输入顶点数,及各顶点信息(数据格式为整形) (2)输入边数,及权值(数据格式为整形) 4.程序的输出，程序输出的形式 (1)输出图的邻接表、深度优先遍历结果、拓扑排序结果。 (2)输入某一确定顶点到其它所有顶点的最短路径。 5.测试数据 二、设计说明 1、算法设计的思想 建立图类，建立相关成员函数。最后在主函数中实现。具体成员函数的实现请参看源程序。 2、主要的数据结构设计说明 图邻接矩阵、邻接表的建立。图的深度优先遍历、拓扑排序、顶点之间的最短路径。 3、程序的主要模板template class Graph 4、程序的主要函数 Graph、link()、DFTraverse()、TopologicalOrder()、 TopologicalOrder()、GetVertexPos()、ShortestPath 三、上机结果及体会 1、实际完成的情况说明 主要程序参考教材《数据结构——C++版》。 2、程序的性能分析 可连续建图 3、上机过程中出现的问题及其解决方案。 编译没有错误，但结果有问题。解决方案：虽然程序的编译通过，只能说明语法上没有问题，结果只所以不正确是因为算法上原因。 4、程序中可以改进的地方说明 程序中的深度优先遍历，浪费空间较大，可以考虑用循环来做。但这样将付出代码长度度加长的代价。 5、程序中可以扩充的功能及设计实现假想 实现假想：随用户的输入可以随时动态的显示图的生成。 6、收获及体会 编写程序即是一件艰苦的工作，又是一件愉快的事情。最大的收获：编程时如果遇到看似简单但又无法解决的问题，很容易灰心丧气。此时切不可烦躁，一定要冷静的思考，认真的分析。要勇敢的面对问题，勇敢的接受问题，勇敢的处理问题，最后最勇敢的解决问题。 四、参考文献

邻接矩阵表示的带权有向图

实习报告——“邻接矩阵表示的带权有向图”演示程序 （一）、程序的功能和特点 主要实现的功能：1.使用邻接矩阵表示带权有向图； 2.查找指定顶点序号； 3.判断图是否为空； 4.判断图是否满； 5.取得顶点数、边数、一条边的权值； 6.插入一个顶点、边； 7.删除一个顶点、边； （二）、程序的算法设计 “邻接矩阵的表示”算法： 1.【逻辑结构与存储结构设计】 逻辑结构：非线性结构——网状结构 存储结构:内存中连续的存储结构，邻接矩阵 2.【基本操作设计】 按指定输入，生成图并打印该图 删除一个顶点并打印 删除一条边并打印 3. 【算法设计】 插入一个顶点的算法： 首先判断该图是否已满，若已满：插入失败； 否则进行插入：1.顶点表增加一个元素 2.邻接矩阵增加一行一列 删除一个顶点的算法： A F E D C B

判断要删除顶点的存在性，若不存在：出错； 否则：1.修改顶点表，即在顶点数组中删除 该点； 2.修改邻接矩阵，即需要统计与该顶 点相关联的边，并将这些边也删除4.【高级语言代码】 public class Graph { static int MaxEdges=50; static int MaxVertices=10; static int MaxValue=9999;//无穷大 //存放顶点的数组 private char VerticesList[]=new char[MaxVertices]; //邻接矩阵（存放两个顶点的权值） private int Edge[][]=new int[MaxVertices][MaxVertices]; private int CurrentEdges;//现有边数 private int CurrentVertices;//现有顶点数 //构造函数：建立空的邻接矩阵 public Graph(){ for(int i=0;i

建立图的邻接矩阵或邻接表存储并在此基础知识上实现图的深度和广度优先遍历

#include "stdafx.h" #include "conio.h" #include "stdio.h" #include "stdlib.h" typedef enum {FALSE, TRUE} BOOLEAN; #define OVERFLOW -1 #define OK 1 #define ERROR 0 #define INFINITY INT_MAX /* 最大值∞ */ /* 根据图的权值类型，分别定义为最大整数或实数 */ #define MAX_VERTEX_NUM 20 /* 最大顶点数目 */ typedef enum {DG, DN, UDG,UDN} GraphKind ; /* {有向图，有向网，无向图，无向网} */ BOOLEAN Visited[MAX_VERTEX_NUM]; BOOLEAN visited[MAX_VERTEX_NUM]; #define VEX_NUM 20 #define MAXSIZE 50 typedef char Vextype; typedef int ElemType; typedef int Status; ////////////////////////////// 邻接矩阵结构定义typedef struct { Vextype vexs[VEX_NUM]; int adj[VEX_NUM][VEX_NUM]; /*邻接矩阵*/ int n,e; /*顶点数和边数*/ }Mgraph;

////////////////////////////// 邻接表结构定义 typedef struct node { /*边结点*/ int adjvex; /*邻接点域*/ struct node * nextarc; /*指向下一个边结点的指针域*/ } EdgeNode; typedef struct vnode { //顶点结构，2个域，结点信息和第一个邻接点Vextype vertex; EdgeNode *firstedge; }VertexNode; typedef struct { //图结构 VertexNode adjlist[MAXSIZE]; int n,e; } ALGraph; //// int FirstAdjVex(ALGraph G,int v) {//在图G中寻找第v个顶点的第一个邻接顶点 if(!G.adjlist[v].firstedge) return -1; else return(G.adjlist[v].firstedge->adjvex); } int NextAdjVex(ALGraph G,int v,int w) {//在图G中寻找第v个顶点的相对于w的下一个邻接顶点 EdgeNode *p; int vi; p=G.adjlist[v].firstedge; if(!p) return -1;

邻接矩阵表示图深度广度优先遍历

*问题描述： 建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或∈E； A[i,j]={ 0，反之 图5-2中有向图G1和无向图G2的邻接矩阵分别为M1和M2: M1=┌0 1 0 1 ┐ │ 1 0 1 0 │ │ 1 0 0 1 │ └0 0 0 0 ┘ M2=┌0 1 1 1 ┐ │ 1 0 1 0 │ │ 1 1 0 1 │ └ 1 0 1 0 ┘ 注意无向图的邻接是一个对称矩阵，例如M2。 用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。因此其类型定义如下： VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧(边)数 GraphKind kind; // 图的种类标志

若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array[1..vnum,1..vnum]of adj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。 对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即 n n D(Vi)＝∑A[i,j]（或∑A[i,j]） j=1 i=1 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若或(Vi,Vj) A[i,j]＝{ ∞, 否则。 其中Wij为或(Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型定义应作如下的修改：adj:weightype ; {weightype为权类型} 图5-6列出一个网和它的邻接矩阵。 ┌∞３１∞∞┐ │∞∞５１∞│ │∞∞∞∞∞│ │∞∞６∞∞│ └∞３２２∞┘ (a)网(b)邻接矩阵 图5-6 网及其邻接矩阵 对无向图或无向网络，由于其邻接矩阵是对称的，故可采用压缩存贮的方法，

分别以邻接矩阵和邻接表作为图的存储结构

分别以邻接矩阵和邻接表作为图的存储结构，给出连通图的深度优先 遍历的递归算法 算法思想： （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); } }