下载文档原格式
图-存储结构-数组表⽰法（邻接矩阵）⽂字描述 ⽤两个数组分别存储顶点信息和边/弧信息。
⽰意图算法分析 构造⼀个采⽤邻接矩阵作存储结构、具有n个顶点和e条边的⽆向⽹(图)G的时间复杂度是(n*n + e*n), 其中对邻接矩阵G.arcs的初始化耗费了n*n的时间。
借助于邻接矩阵容易判定两个顶点之间是否有边/弧相连，并容易求得各个顶点的度。
对于⽆向图，顶点vi的度是邻接矩阵地i⾏(或第i列)的元素之和；对于有向图，第i⾏的元素之和为顶点vi的出度；第j列的元素之和为顶点vj的⼊度；代码实现1/*2以数组表⽰法(邻接矩阵)作为图的存储结构创建图。
3*/4 #include <stdio.h>5 #include <stdlib.h>6 #include <string.h>78#define INFINITY 100000 //最⼤值9#define MAX_VERTEX_NUM 20 //最⼤顶点数10 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向⽹，⽆向图，⽆向⽹}11 typedef int VRType;12 typedef char VertexType;13 typedef struct{14char note[10];15 }InfoType;16 typedef struct ArcCell{17 VRType adj; //顶点关系类型：1)对⽆权图，⽤1或0表⽰相邻否；2)对带权图，则为权值类型18 InfoType *info; //该弧相关信息的指针19 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];20 typedef struct{21 VertexType vexs[MAX_VERTEX_NUM]; //顶点向量22 AdjMatrix arcs; //邻接矩阵23int vexnum, arcnum; //图的当前顶点数和弧数24 GraphKind kind; //图的种类标志25 }MGraph;2627/*28若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。
数据结构课程设计报告设计题目：图的邻接矩阵存储结构院系计算机学院年级x 级学生xxxx学号xxxxxxxxxx指导教师xxxxxxxxx起止时间10-6/10-102013年10月10日目录1 需求分析 (3)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 删除操作 (10)3.8 求顶点的度操作 (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（或者边的权重，如果是带权图），否则为0。
邻接矩阵适用于表示稠密图，即边的数量接近顶点数量的平方的图。
邻接矩阵的优点是可以快速地判断任意两个顶点之间是否存在边，但是当图非常稀疏时，它会占用较多的内存空间。
总的来说，邻接表和邻接矩阵各有优势，选择哪种数据结构取决于具体的应用场景。
如果图是稀疏的，并且需要节省存储空间，邻接表通常更合适；如果需要快速查询任意两点之间的关系，而图又相对稠密，邻接矩阵可能是更好的选择。
数据结构图的存储结构及基本操作数据结构图的存储结构及基本操作1·引言数据结构图是一种用来描述数据元素之间关系的图形结构，它可以表示实体之间的联系和依赖关系。
本文将介绍数据结构图的存储结构及基本操作。
2·存储结构2·1 邻接矩阵邻接矩阵是使用二维数组来表示数据结构图中各个节点之间的关系。
矩阵的行和列代表节点，如果两个节点之间存在边，则矩阵相应位置的值为1，否则为0。
2·2 邻接表邻接表是使用链表来表示数据结构图中各个节点之间的关系。
每个节点都有一个链表，链表中的每个元素表示与该节点相邻的节点。
2·3 十字链表十字链表是使用链表来表示数据结构图中各个节点之间的关系。
每个节点都有两个链表，一个表示该节点指向的节点，另一个表示指向该节点的节点。
2·4 邻接多重表邻接多重表是使用链表来表示数据结构图中各个节点之间的关系。
每个节点都有一个链表，链表中的每个元素表示与该节点相邻的边。
3·基本操作3·1 创建图创建一个空的数据结构图，根据需要选择适当的存储结构。
3·2 插入节点在数据结构图中插入一个节点，并建立与其他节点的关系。
3·3 删除节点从数据结构图中删除一个节点，并删除与其他节点的关系。
3·4 插入边在数据结构图中插入一条边，连接两个节点。
3·5 删除边从数据结构图中删除一条边，断开两个节点的连接。
3·6 遍历图按照某种规则遍历整个数据结构图，访问每个节点。
本文档涉及附件：无本文所涉及的法律名词及注释：1·邻接矩阵：用于表示图的存储结构，矩阵的行和列代表图的节点，矩阵的值表示节点之间的连接关系。
2·邻接表：用于表示图的存储结构，每个节点都有一个链表，链表中的每个元素表示与该节点相邻的节点。
3·十字链表：用于表示图的存储结构，每个节点都有两个链表，一个表示该节点指向的节点，另一个表示指向该节点的节点。
实验报告课程名称：数据结构与算法课程类型：必修实验项目：图型结构及应用实验题目：图的存储结构的建立与搜索一、实验目的1.了解图的两种存储方式：邻接矩阵和邻接表。
2.掌握邻接矩阵和邻接表的建立算法。
3.掌握图的深度优先搜索和广度优先搜索算法。
4.更加熟练文件的相关操作。
二、实验要求及实验环境实验要求：1．分别实现图的邻接矩阵、邻接表存储结构的建立算法，分析和比较各建立算法的时间复杂度以及存储结构的空间占用情况；2．实现图的邻接矩阵、邻接表两种存储结构的相互转换算法；3．在上述两种存储结构上，分别实现图的深度优先搜索（递归和非递归)和广度优先搜索算法。
并以适当的方式存储和显示相应的搜索结果（深度优先或广度优先生成森林（或生成树）、深度优先或广度优先序列和编号）；4．分析搜索算法的时间复杂度；5．以文件形式输入图的顶点和边，并显示相应的结果。
要求顶点不少于10个，边不少于13个；6．软件功能结构安排合理，界面友好，便于使用。
实验环境：codeblocks/Dev-C++三、设计思想（本程序中的用到的所有数据抽象数据性ADT的定义，主程序的流程图及各程序模块之间的调用关系）1. 所用的抽象数据性ADT的定义1）逻辑结构：栈：是一种特殊形式的线性表，所有的插入和删除操作都在栈顶。
栈的置空操作：void makenull(stack* s)判断栈是否为空：int empty(stack* s)返回栈顶元素：btree* top(stack* s)入栈操作：void push(btree* x, stack* s)出栈操作：void pop(stack* s)队列：是一种特殊形式的线性表，队尾入队，队首出队。
将队列置空：void makenull_q(queue* duilie)在队列后面插入T：void enqueue_q(btree* T, queue* duilie)判断队列是否为空：int empty_q(queue* duilie)返回队列的第一个元素：btree* front_q(queue* duilie)删除队列的第一个元素:void dequeue_q(queue* duilie)2) 存储结构：定义了一个邻接矩阵结构体mtgraph，一个边表节点结构体edgenode，一个顶点表结点结构体vertexnode，一个邻接表结构体adjgraph，一个栈结构体stack，一个队列节点结构体node2，一个队列结构体queue，邻接表先深递归访问标记数组visited_1[20]，邻接表先深递归顶点的先深标号数组dfn_1[20]，邻接矩阵先深递归访问标记数组visited_2[20]，邻接矩阵先深递归顶点的先深标号数组dfn_2[20]，邻接表先深非递归访问标记数组visited_5[20]，邻接表先深非递归顶点的先深标号数组dfn_5[20]，邻接矩阵先深非递归访问标记数组visited_6[20]，邻接矩阵先深非递归顶点的先深标号数组dfn_6[20]，邻接表先广访问标记数组visited_3[20]，邻接表先广顶点的先深标号数组dfn_3[20]，邻接矩阵先广访问标记数组visited_4[20]，邻接矩阵先广顶点的先深标号数组dfn_4[20]。
邻接矩阵和邻接表邻接矩阵与邻接表都是建立在图结构中的逻辑关系，用于存储图中相邻节点之间的连接关系，是用来表示网络的重要的数据结构，大量应用于无权图或带权图的表示、存储和操作。
一、邻接矩阵1.概念：邻接矩阵（Adjacency Matrix）是一种用来存储图G中顶点之间的关系的结构，它是由一个二维数组来表示的，数组中的每一行和每一列都代表一个顶点，而数组元素之间的值有一定含义，这些值代表了两个顶点之间是否存在连接，也就是说，只有存在边才能够表示值，否则以无穷大表示。
2.特点：（1）存储空间大：邻接矩阵是一个矩形数组，其中的每一行和每一列都代表一个顶点，那么它所占用的空间一定是与节点的度数有关的，因此在稀疏图结构中使用邻接矩阵对空间也会非常消耗；（2）查找方便：邻接矩阵存储的是节点两两之间的连接关系，只要矩阵中相应位置上的值不为无穷大，就能判断这两个节点之间是否存在连接，因此在查找图中某两节点之间连接关系的时候，邻接矩阵的效率会比较高。
二、邻接表1.概念：邻接表也是一种非常常用的表示图的数据结构，它采用的是链表的形式来存储顶点的相邻的结点的关系，也就是说，每个顶点都会有一个链表来存储它周围的结点。
它能够比较好的展示出图中各个顶点之间的关系，以及图中结点的孤立情况。
2.特点：（1）存储空间小：由于邻接表使用链表的方式存储节点，它可以精确的表示两个节点的距离，而非像邻接矩阵一样，数组中的每一行和每一列都代表一个节点，因此，它所占用的空间会比邻接矩阵小些，在内存空间中有比较大的空间优势；（2）查找速度略低：虽然邻接表能精确的表示两个节点之间的距离，而且只需要占用少量内存，但是查找两点之间连接关系所花费的时间会略大于邻接矩阵。
摘要图(Gｒaph)是一种复杂的非线性结构。
图可以分为无向图、有向图。
若将图的每条边都赋上一个权，则称这种带权图网络。
在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。
在图结构中，对结点（图中常称为顶点)的前趋和后继个数都是不加以限制的,即结点之间的关系是任意的。
图中任意两个结点之间都可能相关。
图有两种常用的存储表示方法:邻接矩阵表示法和邻接表表示法。
在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。
在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。
当然对于图的广度优先遍历还利用了队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。
这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。
目录第一章课程设计目的..................................................................................... 错误!未定义书签。
第二章课程设计内容和要求....................................................................... 错误!未定义书签。
2．1课程设计内容.................................................................................. 错误!未定义书签。
2.1.1图的邻接矩阵的建立与输出ﻩ错误!未定义书签。
2．１.２图的邻接表的建立与输出............................................... 错误!未定义书签。
2.1.3图的遍历的实现.................................................................... 错误!未定义书签。
1.采用邻接矩阵（邻接表）存储，构造无向图（网）输入：顶点数、边数、顶点信息、边信息输出：图的顶点，图的边邻接矩阵（数组表示法）处理方法：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。
假设图G＝(V,E)有n个顶点，则邻接矩阵是一个n×n 的方阵，定义为：如果(vi,vj)属于边集，则edges[i][j]=1，否则edges[i][j]=0。
邻接表存储的处理方法：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。
程序代码：#include<iostream>using namespace std;#define MAX_VERTEX_NUM 20 //最大顶点个数#define OK 1typedef int Status;//图的数组（邻接矩阵）存储表示typedef struct ArcCell { // 弧的定义int adj; // VRType是顶点关系类型。
// 对无权图，用1或0表示相邻否；// 对带权图，则为权值类型。
int *info; // 该弧相关信息的指针} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct { // 图的定义char vexs[MAX_VERTEX_NUM];//顶点向量AdjMatrix arcs; // 邻接矩阵int vexnum, arcnum; // 图的当前顶点数、弧数} MGraph;int LocateV ex(MGraph G, char v){int a;for (int i = 0; i <= G.vexnum; i++){if (G.vexs[i] == v)a= i;}return a;}Status CreateUDN(MGraph &G) { //采用邻接矩阵表示法，构造无向网Gint i, j, k, w;char v1, v2;cout <<"输入顶点数，边数："<< endl;cin >> G.vexnum >> G.arcnum;//IncInfo为0,表示各弧无信息cout <<"各顶点分别为："<< endl;for (i = 0; i<G.vexnum; i++)cin >> G.vexs[i]; //构造顶点向量for (i = 0; i<G.vexnum; i++) //初始化邻接矩阵for (j = 0; j<G.vexnum; j++){G.arcs[i][j].adj =NULL;}cout <<"顶点信息、边信息："<< endl;for (k = 0; k<G.arcnum; k++) { //构造邻接矩阵cin >> v1 >> v2 >> w; //输入一条边依附的顶点及权值i = LocateV ex(G, v1); j = LocateV ex(G, v2);G.arcs[i][j].adj = w;G.arcs[j][i] = G.arcs[i][j];} return OK;} //CreateUDN (p162 算法7.2)Status printf1(MGraph G){cout <<"该图的顶点分别为：";for (int i = 0; i<G.vexnum; i++)cout << G.vexs[i] <<"";return OK;}Status printf2(MGraph G){cout <<"该图的边为：";for (int i = 1; i<G.vexnum; i++) //初始化邻接矩阵for (int j = 0; j<i; j++){if (G.arcs[i][j].adj !=NULL)cout << G.vexs[j]<< G.vexs[i] <<"," ;}return OK;}int main(){MGraph G;CreateUDN(G);printf1(G);cout << endl;printf2(G);cout << endl;system("pause");return 0;}。
课程名称: 《数据结构》课程设计课程设计题目:图的邻接矩阵存储结构建立姓名:XXX院系:计算机学院专业:计算机科学技术年级:11级学号:XXXXXXXX指导教师:XXX2013年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<stdio.h>#include<malloc.h>#define MAX 20int visited[MAX]; //访问标志数组typedef struct{char vexs[MAX]; //顶点向量int arcs[MAX][MAX]; //邻接矩阵int vexnum,arcnum; //图的当前顶点数和边数}Graph;typedef struct Qnodeint 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<G.vexnum;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<G.vexnum;i++)visited[i]=0;for(i=0;i<G.vexnum;i++){ printf("请输入第%d个顶点信息:",i+1);scanf("%c",&G.vexs[i]);getchar();}for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[i][j]=0;for(i=0;i<G.arcnum;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<G.vexnum;++i){for(j=0;j<G.vexnum;++j)printf("%-2d",G.arcs[i][j]);printf("\n");}}int FirstAdiVex(Graph G,int v) //图G中顶点v的第一个邻接顶点{int i;if(v>=0&&v<G.vexnum){for(i=0;i<G.vexnum;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<G.vexnum&&j>=0&&j<G.vexnum){for(k=j+1;k<G.vexnum;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<MAX;i++)visited[i]=0;for(i=0;i<G.vexnum;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;}elseprintf("重新输入!\n");}return 0;}3.6测试结果测试数据如下：深度优先遍历序列：A->B->D->C->E广度优先遍历序列：A->B->C->E->D（1）程序开始的界面。
（2）创建无向图。
(3)图的深度优先遍历。
(4)图的广度优先遍历。
4.小结在数据结构课程设计的过程中，我不仅认识到了学好解理论知识的必要性，更认识到了上机操作的重要性。
上机操作能过培养我们解决实际问题的能力，通过对上机操作遇到的各种问题的解决，自己感到一丝成功的同时，更下决心努力学好专业课，为以后的学习及实践打下好的基础。
5.参考文献①严蔚敏,吴伟民编著.数据结构(C语言版)--北京:清华大学出版社。
