课程名称: 《数据结构》课程设计课程设计题目:图的邻接矩阵存储结构建立
姓名: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.程序流程图：
3.3调试分析
程序的设计严格遵循结构化的程序设计思想，由简单到复杂，注意规范。在此次程序运行中，出现了很多的错误，开始的时候，不能很好的创建一个图，后来改进了算法，使得程序能够正确的运行。
3.4用户手册
①进入程序后，您会看到以下提示：
“无向图的创建及DFS和BFS的递归和非递归实现!”
1.“创建无向图!”；
2.“图的深度优先遍历!”；
3.“图的广度优先遍历!”；
4.“退出!”；
请选择相应的数字键实现相应的功能。
②在执行图的遍历前必须先创建图，创建图时，按照系统的提示进行操作即可。
3.5程序清单
#include
#include
#define MAX 20
int visited[MAX]; //访问标志数组
typedef struct
{
char vexs[MAX]; //顶点向量
int arcs[MAX][MAX]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}Graph;
typedef struct Qnode
int data;
struct Qnode *next;
}Qnode,*Queueptr;
typedef struct
{
Queueptr front;
Queueptr rear;
}Linkqueue;
void InitQueue(Linkqueue &Q)
{
Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode));
if(Q.front)
Q.front->next=NULL;
}
void EnQueue(Linkqueue &Q,int e)
{
Queueptr p;
p=(Queueptr)malloc(sizeof(Qnode));
if(p)
{
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
}
int DeQueue(Linkqueue &Q)
{
int e;
Queueptr p;
if(Q.rear!=Q.front)
{
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
if(Q.front==p)
Q.rear=Q.front;
return e;
}
int Locatevex(Graph G,char v) //返回元素v的位置
{
int i;
for(i=0;i if(G.vexs[i]==v) return i; return -1; } void CreateGraph(Graph &G) //创建无向图的邻接矩阵 { int i,j,w,m,n; char a,b,c; printf("请输入图G的顶点数和弧数:"); scanf("%d%d",&G.vexnum,&G.arcnum); getchar(); for(i=0;i visited[i]=0; for(i=0;i { printf("请输入第%d个顶点信息:",i+1); scanf("%c",&G.vexs[i]); getchar(); } for(i=0;i for(j=0;j G.arcs[i][j]=0; for(i=0;i { printf("请输入第%d条弧依附的两个顶点及权值: ",i+1); scanf("%c %c %d%c",&a,&b,&w,&c); m=Locatevex(G,a); n=Locatevex(G,b); G.arcs[m][n]=w; G.arcs[n][m]=w; } } void PrintMatrix(Graph G) //输出邻接矩阵 { int i,j; printf("\n由图G生成的邻接矩阵如下:\n"); for(i=0;i { for(j=0;j printf("%-2d",G.arcs[i][j]); printf("\n"); } } int FirstAdiVex(Graph G,int v) //图G中顶点v的第一个邻接顶点 { int i; if(v>=0&&v { for(i=0;i if(G.arcs[v][i]!=0) return i; } return -1; } int NextAdVex(Graph G,int i,int j) //图G中顶点i的第j个邻接顶点的下一个邻接顶点 { int k; if(i>=0&&i { for(k=j+1;k if(G.arcs[i][k]!=0) return k; } return -1; } void DFS(Graph G,int v) //从第v个顶点出发深度递归遍历图 { int u; printf("%2c",G.vexs[v]); visited[v]=1; u=FirstAdiVex(G,v); while(u>=0) { if(!visited[u]) DFS(G,u); u=NextAdVex(G,v,u); } } void BFS(Graph G)//广度非递归遍历 { int i,w,k; Linkqueue Q; InitQueue(Q); for(i=0;i visited[i]=0; for(i=0;i if(!visited[i]) { visited[i]=1; printf("%2c",G.vexs[i]); EnQueue(Q,i); while(Q.front!=Q.rear) { k=DeQueue(Q); for(w=FirstAdiVex(G,k);w>=0;w=NextAdVex(G,k,w)) if(!visited[w]) { visited[w]=1; printf("%2c",G.vexs[w]); EnQueue(Q,w); } } } } int main() { int m; Graph G; printf("无向图的创建及DFS和BFS的递归和非递归实现!\n\n"); while(1) { printf("1.创建无向图!\n"); printf("2.图的深度优先遍历!\n"); printf("3.图的广度优先遍历!\n"); printf("4.退出!\n"); printf("请选择功能:"); scanf("%d",&m); if(m==1) { CreateGraph(G); PrintMatrix(G); } else if(m==2) { printf("图G的深度递归优先遍历序列为:\n"); DFS(G,0); printf("\n"); } else if(m==3) { printf("图G的广度非递归优先遍历序列为:\n"); BFS(G); printf("\n"); } else if(m==4) { printf("成功退出!\n"); break; } else printf("重新输入!\n"); } return 0; } 3.6测试结果 测试数据如下： 深度优先遍历序列：A->B->D->C->E 广度优先遍历序列：A->B->C->E->D （1）程序开始的界面。 （2）创建无向图。 (3)图的深度优先遍历。 (4)图的广度优先遍历。 4.小结 在数据结构课程设计的过程中，我不仅认识到了学好解理论知识的必要性，更认识到了上机操作的重要性。上机操作能过培养我们解决实际问题的能力，通过对上机操作遇到的各种问题的解决，自己感到一丝成功的同时，更下决心努力学好专业课，为以后的学习及实践打下好的基础。 5.参考文献 ①严蔚敏,吴伟民编著.数据结构(C语言版)--北京:清华大学出版社 一、单选题 C01、在一个图中，所有顶点的度数之和等于图的边数的倍。 A)1/2 B)1 C)2 D)4 B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A)1/2 B)1 C)2 D)4 B03、有8个结点的无向图最多有条边。 A)14 B)28 C)56 D)112 C04、有8个结点的无向连通图最少有条边。 A)5 B)6 C)7 D)8 C05、有8个结点的有向完全图有条边。 A)14 B)28 C)56 D)112 B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。 A)O(n) B)O(e) C)O(n+e) D)O(n2) C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。 A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2 B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。 A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6 D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。 A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3 A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。 A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2 A13、图的深度优先遍历类似于二叉树的。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 D14、图的广度优先遍历类似于二叉树的。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 B15、任何一个无向连通图的最小生成树。 A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在 A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。 A)n、2e B)n、e C)n、n+e D)2n、2e C17、判断有向图是否存在回路，可以利用___算法。 A)关键路径 B)最短路径的Dijkstra C)拓扑排序 D)广度优先遍历 A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。 A)图中每个顶点的入度 B)图中每个顶点的出度 C)图中弧的条数 D)图中连通分量的数目 课程名称: 《数据结构》课程设计课程设计题目:图的邻接矩阵存储结构建立 姓名: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.程序流程图： //算法功能：采用邻接表存储结构建立无向图 #include 图的邻接矩阵和邻接表相互转换 图的邻接矩阵存储方法具有如下几个特征：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 以邻接矩阵存储的图类型构造n个城市连接的最小生成树代码： #include scanf("%d" ,&(G->vexs[i])) ; /* 输入顶点信息，建立顶点表*/ } for (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; //顶点数据元素 实验报告实验日期：数据结构与算法课程： 图的邻接矩阵实验名称： 一、实验目的掌握图的邻接矩阵 二、实验内容必做部分 、给出图的邻接矩阵存储结构的类型定义。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 数据结构 课程设计报告 设计题目：图的邻接矩阵存储结构 院系计算机学院 年级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描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。 关键词：网络化；计算机；对策；图；储存。 《图的邻接表存储结构实验报告》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 #include 图的邻接表存储方式——数组实现初探 焦作市外国语中学岳卫华在图论中，图的存储结构最常用的就是就是邻接表和邻接矩阵。一旦顶点的个数超过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={ 一旦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类型 题目：以实验3.1所示邻接矩阵为存储结构，编写程序，实现图的深度、宽度优先遍历。 部分代码： 邻接矩阵的单一顶点DFS： //邻接矩阵的单一顶点DFS void DFS(int v,int visited[],mGraph g){ int j; printf("%d ",v); //访问顶点v visited[v] = 1; //为顶点v打上访问标记 for(j = 0;j < g.n; j++){ //遍历v的邻接点 if(!visited[j] && g.a[v][j] > 0){ //当未被访问且有权值 DFS(j,visited,g); } } } 邻接矩阵的全图DFS： //邻接矩阵的全图DFS void DFSGraph(mGraph g){ int i; int *visited = (int*)malloc(g.n * sizeof(int)); //动态生成标记数组visted for(i = 0;i < g.n;i ++){ visited[i] = 0; //visted数组初始化 } //visted数组初始化 for(i = 0;i < g.n;i ++){ //逐一检查每个顶点,若未被访问,则调用DFS if(!visited[i]){ //当未被访问且有权值 DFS(i,visited,g); } } free(visited); //释放visted数组 } 邻接矩阵的单一顶点BFS： //邻接矩阵的单一顶点BFS void BFS(int v,int visited[],mGraph g){ Queue q; Create(&q,g.n); //初始化队列 visited[v] = 1; //为顶点v打上访问标记 图采用邻接矩阵存储结构 #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 韩山师范学院 实验题目： 邻接矩阵创建有向网算法实现 班级：2015级软工班作者：黄俊聪 #include for(i=0; i *问题描述： 建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或 若图中每个顶点只含一个编号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, 若 目录 前言 (1) 1. 邻接矩阵发展简史 (3) 2．基本概念及记号 (4) 3. 无向图的邻接矩阵 (6) 3.1 无向图的邻接矩阵定义及表示 (6) 3.2 无向图的邻接矩阵的性质 (8) 4. 有向图的邻接矩阵 (9) 4.1 有向图的邻接矩阵的定义及表示 (9) 4.2 有向图的邻接矩阵的性质 (10) 5. 邻接矩阵的重要定理及应用 (11) 6. 邻接矩阵的应用 (13) 6.1 邻接矩阵生成图的遍历序列 (13) 6.2用邻接矩阵生成图的广度优先遍历序列 (15) 6.3 矩阵构造最小生成树 (16) 6.4 用邻接矩阵寻找关键路径 (19) 参考文献 (21) 致谢 (22) 平顶山学院本科毕业论文（设计） 前言 图论最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题．这些古老的难题，当时吸引了很多学者的注意．在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿（环游世界）数学难题． 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，发挥出越来越大的作用．在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一，因此越来越受到数学家和实际工作者的喜爱．我们所学的这一章只是介绍一些基本概念、原理以及一些典型的应用实例，目的是在今后对工程技术有关学科的学习研究时，可以把图论的基本知识、方法作为工具[]1． “图论”是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系. 图论是一门极有兴趣的学问，其广阔的应用领域涵盖了人类学、计算机科学、化学、环境保护、电信领域等等.严格地讲，图论是组合数学的一个分支，例如，它交叉运用了拓扑学、群论和数论.图论就是研究一些事物及它们之间关系的学科，现实世界中的许多事物能用图来表示其拓扑结构，把实际问题的研究转化为图的研究，利用图论的相关结论 对这些问题作分析或判断[]1. 图论是近二十年来发展十分迅速、应用比较广泛的一个新兴的数学分支，在许多领域，诸如物理学、化学、运筹学、信息论、控制论、计算机等方面甚至在生产生活中都有广泛的应用.因此受到全世界越来越广泛的重视。图论的内容十分丰富，涉及面也比较广. 研究节点和边组成的图形的数学理论和方法，为运筹学的一个分支。图论的基本元素是节点和边（也称线、弧、枝），用节点表示所研究的对象，用 1 #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; #include 数据结构第7章-答案
图的邻接矩阵存储结构建立汇总
邻接表存储结构建立无向图
图的邻接矩阵和邻接表相互转换
以邻接矩阵存储的图类型构造n个城市连接的最小生成树
实验十三 图的基本操作—邻接表存储结构
数据结构与算法-图的邻接矩阵
数据结构课程设计-图的邻接矩阵
图的邻接表存储结构实验报告
用邻接矩阵表示法创建有向图(数据结构)
图的邻接表存储方式.
实现图的邻接矩阵和邻接表存储
数据结构实验3.2：以邻接矩阵为存储结构的图的深度、宽度优先遍历
图采用邻接矩阵存储结构
邻接矩阵创建有向网的实现
邻接矩阵表示图深度广度优先遍历
邻接矩阵的应用1
建立图的邻接矩阵或邻接表存储并在此基础知识上实现图的深度和广度优先遍历
图的邻接矩阵的建立与输出
相关主题
文本预览