下载文档原格式
1图的遍历问题在实践中常常遇到这样的问题：给定n个点，从任一点出发对所有的点访问一次并且只访问一次。
如果用图中的顶点表示这些点，图中的边表示可能的连接，那么这个问题就可以表示成图的遍历问题，即从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
图的遍历操作和树的遍历操作功能相似，是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础上。
由于图结构本身的复杂性，所以图的遍历操作也比较复杂，主要表现在以下几个方面：(1) 在图结构中，没有一个确定的首结点，图中任意一个顶点都可以作为第一个被访问的结点。
(2) 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需要考虑如何选取下一个出发点以访问图中其余的连通分量。
(3) 在图结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点。
⑷在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
基于以上分析，图的遍历方法目前有深度优先搜索(DFS)和广度优先搜索(BFS)两种算法。
下面将介绍两种算法的实现思路，分析算法效率并编程实现。
1.1深度优先搜索算法深度优先搜索算法是树的先根遍历的推广，它的实现思想是：从图G的某个顶点V o出发，访问V o,然后选择一个与V o相邻且没被访问过的顶点V i访问，再从V i出发选择一个与V i相邻且未被访问的顶点V j进行访问，依次继续。
如果当前被访问过的顶点的所有邻接顶点都已被访问，贝U退回已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样的方法向前遍历，直到图中所有顶点都被访问。
其递归算法如下：Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void DFSTraverse (Graph G Status(*Visit)(i nt v)){VisitF unc = Visit;for(v=0; vvG.vex num; ++v)visited[v] = FALSE; //访问标志数组初始化for(v=0; v<G .vex num; ++v)if(!visited[v])DFS(G v); //对尚未访问的顶点调用DFS}void DFS(Graph G int v){ //从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE; VisitFunc(v); // 访问第v 个顶点for(w=FirstAdjVex(G ,v); w>=0;w=NextAdjVex(G ,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)。
实验6.1实现图的存储和遍历一，实验目的掌握图的邻接矩阵和邻接表存储以及图的邻接矩阵存储的递归遍历。
二，实验内容6.1实现图的邻接矩阵和邻接表存储编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：（1）建立如教材图7.9所示的有向图G的邻接矩阵，并输出。
（2）由有向图G的邻接矩阵产生邻接表，并输出。
（3）再由（2）的邻接表产生对应的邻接矩阵，并输出。
6.2 实现图的遍历算法（4）在图G的邻接矩阵存储表示基础上，输出从顶点V1开始的深度优先遍历序列（递归算法）。
（5）利用非递归算法重解任务（4）。
（6）在图G的邻接表存储表示基础上，输出从顶点V1开始的广度优先遍历序列。
三，源代码及结果截图#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<malloc.h>#define MAX_VERTEX_NUM 20typedef char VRType;typedef int InfoType; // 存放网的权值typedef char VertexType; // 字符串类型typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网}/*建立有向图的邻接矩阵*/typedef struct ArcCell{VRType adj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻;对带权图则为权值类型InfoType *info; //该弧相关信息的指针(可无)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];//顶点向量AdjMatrix arcs;//邻接矩阵int vexnum,arcnum;;//图的当前顶点数和弧数GraphKind kind;//图的种类标志}MGraph;/* 顶点在顶点向量中的定位*/int LocateVex(MGraph &M,VRType v1){int i;for(i=0;i<M.vexnum;i++)if(v1==M.vexs[i])return i;return -1;}void CreateGraph(MGraph &M)//建立有向图的邻接矩阵{int i,j,k,w;VRType v1,v2;M.kind=DN;printf("构造有向网:\n");printf("\n输入图的顶点数和边数(以空格作为间隔):");scanf("%d%d",&M.vexnum,&M.arcnum);printf("输入%d个顶点的值(字符):",M.vexnum);getchar();for(i=0;i<M.vexnum;i++) //输入顶点向量{scanf("%c",&M.vexs[i]);}printf("建立邻接矩阵:\n");for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++){M.arcs[i][j].adj=0;M.arcs[i][j].info=NULL;}printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");for(k=0;k<M.arcnum;++k)// 构造表结点链表{cin>>w>>v1>>v2;i=LocateVex(M,v1);j=LocateVex(M,v2);M.arcs[i][j].adj=w;}}//按邻接矩阵方式输出有向图void PrintGraph(MGraph M){int i,j;printf("\n输出邻接矩阵:\n");for(i=0; i<M.vexnum; i++){printf("%10c",M.vexs[i]);for(j=0; j<M.vexnum; j++)printf("%2d",M.arcs[i][j].adj);printf("\n");}}// 图的邻接表存储表示typedef struct ArcNode{int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧的指针InfoType *info; // 网的权值指针）}ArcNode; // 表结点typedef struct VNode{VertexType data; // 顶点信息ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];// 头结点typedef struct{AdjList vertices;int vexnum,arcnum; // 图的当前顶点数和弧数int kind; // 图的种类标志}ALGraph;void CreateMGtoDN(ALGraph &G,MGraph &M){//由有向图M的邻接矩阵产生邻接表int i,j;ArcNode *p;G.kind=M.kind;G.vexnum=M.vexnum;G.arcnum=M.arcnum;for(i=0;i<G.vexnum;++i){//构造表头向量G.vertices[i].data=M.vexs[i];G.vertices[i].firstarc=NULL;//初始化指针}for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)if(M.arcs[i][j].adj){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.vexnum;++i)M.vexs[i]=G.vertices[i].data;for(i=0;i<M.vexnum;++i){p=G.vertices[i].firstarc;while(p){M.arcs[i][p->adjvex].adj=1;p=p->nextarc;}//whilefor(j=0;j<M.vexnum;++j)if(M.arcs[i][j].adj!=1)M.arcs[i][j].adj=0;}//for}//输出邻接表void PrintDN(ALGraph G){int i;ArcNode *p;printf("\n输出邻接表：\n");printf("顶点:\n");for(i=0;i<G.vexnum;++i)printf("%2c",G.vertices[i].data);printf("\n弧:\n");for(i=0;i<G.vexnum;++i){p=G.vertices[i].firstarc;while(p){printf("%c→%c(%d)\t",G.vertices[i].data,G.vertices[p->adjvex].data,p->info);p=p->nextarc;}printf("\n");}//for}int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)void(*VisitFunc)(char* v); // 函数变量(全局量)// 从第v个顶点出发递归地深度优先遍历图G。
数据结构课程设计报告设计题目：图的邻接矩阵存储结构院系计算机学院年级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.邻接矩阵邻接矩阵是一种使用二维数组来表示图中顶点之间关系的方法。
如果图中有n个顶点，那么对应的邻接矩阵就是一个n*n的矩阵，其中元素a[i][j]表示顶点i和顶点j之间是否有边，通常用0和1表示。
邻接矩阵适用于稠密图，其存储结构简单，可以直观地展示图的结构，但对于稀疏图来说可能会造成存储空间的浪费。
2.邻接表邻接表是一种使用链表来表示图中顶点之间关系的方法。
对于图中的每一个顶点，都维护一个相邻顶点的列表，图中所有顶点的列表再组合成一个链表，用于表示整个图的结构。
邻接表适用于稀疏图，其存储结构灵活，可以有效地节省存储空间，但查找任意两个顶点之间的关系可能会比较耗时。
二、深度遍历和广度遍历原理1.深度遍历深度遍历是一种用于遍历或搜索图中节点的算法，其原理是从图的某一顶点出发，沿着一条路径不断向下遍历直到末端，然后回溯到上一个节点继续遍历。
深度遍历使用栈来实现，可以通过递归或迭代来进行。
2.广度遍历广度遍历是一种用于遍历或搜索图中节点的算法，其原理是从图的某一顶点出发，依次访问其所有相邻节点，然后再依次访问这些相邻节点的相邻节点，以此类推。
广度遍历使用队列来实现。
三、深度遍历和广度遍历的应用1.深度遍历的应用深度遍历常用于求解图的连通分量、拓扑排序、解决迷宫问题等。
在连通分量中，深度遍历可以帮助我们找到图中的所有连通分量，并对其进行标记，用于进一步的算法运算。
在拓扑排序中，深度遍历可以帮助我们找到一个合理的顺序，用以处理依赖关系问题。
在解决迷宫问题时，深度遍历可以帮助我们找到一条从起点到终点的路径。
2.广度遍历的应用广度遍历常用于求解最短路径、解决迷宫问题等。
在求解最短路径中，广度遍历可以帮助我们找到起点到终点的最短路径，从而解决了许多实际问题。
邻接矩阵的深度优先遍历算法简介邻接矩阵是一种常见的图存储结构，它使用二维数组来表示图中各个顶点之间的关系。
而深度优先遍历算法是一种常用的图遍历算法，用于遍历和搜索图的各个顶点。
本文将介绍邻接矩阵的深度优先遍历算法，包括其基本思想、实现步骤以及应用场景等内容。
基本思想深度优先遍历算法（Depth-First Search，DFS）是一种针对图和树的遍历算法，它通过从起始顶点开始，逐个探索图中的顶点，并沿着某一条路径一直深入，直到无法继续为止，然后回溯到前一顶点继续探索其它路径，直到所有顶点都被访问过为止。
邻接矩阵是一种常见的图表示方法，它通过一个二维数组来表示图中各个顶点之间的关系。
邻接矩阵中的每个元素表示两个顶点之间是否存在一条边，具体而言，如果顶点i和顶点j之间存在一条边，则邻接矩阵中下标为(i, j)和(j, i)的元素值为1；否则，它们的元素值为0。
邻接矩阵的深度优先遍历算法是通过对邻接矩阵进行遍历，找出与起始顶点相连接的顶点，并依次对这些顶点进行深度优先遍历。
实现步骤邻接矩阵的深度优先遍历算法可以使用递归或迭代的方式来实现。
下面分别介绍这两种实现方法的具体步骤。
递归实现1.创建一个数组visited，用来记录每个顶点是否已被访问过，初始时所有元素都设为0。
2.选择一个起始顶点v，并将visited[v]设置为1，表示该顶点已被访问过。
3.遍历邻接矩阵中与v相连的所有顶点w，如果visited[w]为0，则递归调用深度优先遍历函数，将w作为新的起始顶点。
4.重复步骤3，直到所有顶点都被访问过为止。
迭代实现1.创建一个数组visited，用来记录每个顶点是否已被访问过，初始时所有元素都设为0。
2.创建一个栈，用来存储待访问的顶点。
3.选择一个起始顶点v，并将visited[v]设置为1，表示该顶点已被访问过。
4.将v入栈。
5.当栈不为空时，执行以下操作：–出栈一个顶点u，访问它。
–遍历邻接矩阵中与u相连的所有顶点w，如果visited[w]为0，则将w入栈，并将visited[w]设置为1。
邻接矩阵例题
（原创版）
目录
1.邻接矩阵的定义和作用
2.邻接矩阵的存储方式
3.邻接矩阵的实例分析
4.邻接矩阵的计算方法
5.邻接矩阵在网络分析中的应用
正文
邻接矩阵是一种用于表示有向图或无向图中各个顶点间关系的矩阵。
在图论中，邻接矩阵被广泛应用于表示图的结构，以及进行图的遍历、寻找最短路径等算法。
邻接矩阵的存储方式通常采用二维数组。
对于有向图来说，设图中有n 个顶点，那么邻接矩阵就是一个 n×n 的矩阵。
如果图中的顶点 i 到顶点 j 有边，则矩阵的第 i 行第 j 列（记作 aij）处的元素为 1（如果是有向边），或者对应的边的权（如果是带权边）；如果顶点 i 到顶点 j 没有边，则 aij 为 0。
对于无向图来说，因为顶点 i 到顶点 j 的边和顶点 j 到顶点 i 的边是等价的，所以无向图的邻接矩阵总是对称的。
以一个简单的例子来说明邻接矩阵的计算方法。
假设有一个无向图，有 3 个顶点，分别是 1、2、3，它们之间的边关系是：1 到 2、1 到 3、2 到 3。
那么，这个图的邻接矩阵就是：
1 2 3
1 0 1 1
2 1 0 1
3 1 1 0
在网络分析中，邻接矩阵可以方便地表示网络的结构，并且可以快速进行图的遍历，寻找最短路径等操作。
例如，如果要从顶点 1 到顶点 3 寻找最短路径，可以通过遍历邻接矩阵，依次沿着最短路径前进，直到到达目标顶点。
邻接矩阵法邻接矩阵法是图论中一种常用的表示图结构的方法。
它通过一个二维矩阵来表示图中各个顶点之间的连接关系。
在邻接矩阵中，矩阵的行和列分别代表图中的顶点，而矩阵中的元素则表示对应顶点之间是否存在边。
邻接矩阵的定义假设有一个无向图G=(V,E)，其中V为顶点集合，E为边集合。
邻接矩阵A是一个n×n的方阵，其中n为图中顶点的个数。
邻接矩阵A满足以下条件：•如果顶点i和顶点j之间存在边，则A[i][j]=1；•如果顶点i和顶点j之间不存在边，则A[i][j]=0。
对于有向图来说，邻接矩阵也可以用来表示其连接关系，只是在有向图中，边具有方向性。
邻接矩阵的应用邻接矩阵作为一种常见的图表示方法，在许多算法和应用中都得到了广泛的应用。
下面介绍一些常见的应用场景：1. 图遍历通过邻接矩阵，我们可以方便地遍历图中的顶点和边。
对于一个顶点i，我们只需要遍历邻接矩阵的第i行（或第i列），就可以获取到与该顶点直接相连的所有顶点。
2. 最短路径算法邻接矩阵常被用于求解最短路径问题，例如Dijkstra算法和Floyd-Warshall算法。
在这些算法中，通过邻接矩阵来表示各个顶点之间的距离或权重，然后根据具体的算法逻辑来计算最短路径。
3. 最小生成树邻接矩阵也可以用于求解最小生成树问题，例如Prim算法和Kruskal算法。
在这些算法中，邻接矩阵用来表示图中各个顶点之间的连接关系，并根据具体的算法逻辑选择合适的边来构建最小生成树。
4. 图的连通性判断通过邻接矩阵，我们可以判断一个图是否是连通图。
如果一个无向图的邻接矩阵是对称且连通的，则说明该图是一个连通图。
如果一个有向图的邻接矩阵是强连通的，则说明该有向图是强连通图。
邻接矩阵的优缺点邻接矩阵作为一种图的表示方法，具有以下优点：•表示简单：邻接矩阵直观地表示了图中各个顶点之间的连接关系，易于理解和实现。
•查询高效：通过邻接矩阵，可以快速判断两个顶点之间是否存在边，时间复杂度为O(1)。
一、实验目的1. 理解邻接矩阵的概念及其在图论中的应用。
2. 掌握邻接矩阵的构建方法。
3. 学会使用邻接矩阵进行图的深度优先遍历和广度优先遍历。
4. 比较邻接矩阵和邻接表两种图的存储结构的优缺点。
二、实验内容1. 构建邻接矩阵2. 使用邻接矩阵进行图的深度优先遍历3. 使用邻接矩阵进行图的广度优先遍历4. 分析邻接矩阵和邻接表的优缺点三、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019四、实验步骤1. 构建邻接矩阵（1）定义图的顶点数量n。
（2）创建一个nn的二维数组A，用于存储邻接矩阵。
（3）根据图的边信息，将对应的A[i][j]值设置为1（表示存在边）或0（表示不存在边）。
2. 使用邻接矩阵进行图的深度优先遍历（1）初始化访问标记数组visited，用于记录顶点是否被访问过。
（2）从某个顶点v开始，将其标记为已访问，并将其加入访问序列。
（3）对于v的每个邻接顶点u，如果u未被访问过，则递归调用深度优先遍历算法，并将u加入访问序列。
（4）重复步骤3，直到所有顶点都被访问过。
3. 使用邻接矩阵进行图的广度优先遍历（1）初始化队列Q和一个访问标记数组visited。
（2）将起始顶点v入队，并将其标记为已访问。
（3）当队列不为空时，执行以下步骤：a. 从队列中取出一个顶点v。
b. 将v的邻接顶点u入队，并将u标记为已访问。
c. 将v加入访问序列。
（4）重复步骤3，直到队列空为止。
4. 分析邻接矩阵和邻接表的优缺点（1）邻接矩阵的优点：a. 查找边的时间复杂度为O(1)。
b. 遍历图的时间复杂度为O(n^2)。
c. 适用于稠密图。
（2）邻接矩阵的缺点：a. 空间复杂度为O(n^2)，对于稀疏图，空间利用率低。
b. 查找边和遍历图的时间复杂度较高。
（3）邻接表的优点：a. 空间复杂度为O(n+e)，对于稀疏图，空间利用率高。
b. 查找边和遍历图的时间复杂度为O(n+e)。
第7章 《图》习题参考答案一、单选题（每题1分，共16分）（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的倍。
A ．1/2 B. 1 C. 2 D. 4 （B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。
A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有条边。
A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有条边。
A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有条边。
A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。
A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。
A ．栈 B. 队列 C. 树 D. 图（ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 23465 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 1 3 4 2 5 6D. 0 3 6 1 5 4 2⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3A．0 3 2 1 B. 0 1 2 3C. 0 1 3 2D. 0 3 1 2（A）12. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）13. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）14. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。
图的存储实验报告图的存储实验报告引言在计算机科学领域中，图是一种重要的数据结构，用于描述对象之间的关系。
图的存储方式对于图的遍历、搜索和其他操作有着重要的影响。
本实验旨在探究不同的图存储方式，并比较它们在不同操作下的性能差异。
一、邻接矩阵存储方式邻接矩阵是一种常见的图存储方式，它使用二维数组来表示图中各个顶点之间的关系。
在邻接矩阵中，行和列分别代表图中的顶点，矩阵中的元素表示两个顶点之间的边的关系。
实验中，我们通过一个简单的例子来说明邻接矩阵的存储方式。
假设有一个无向图，其中包含5个顶点和6条边。
我们可以使用一个5x5的矩阵来表示这个图，矩阵中的元素为1表示两个顶点之间存在边，为0表示不存在边。
邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，时间复杂度为O(1)。
然而，邻接矩阵的缺点是当图中的边数较少时，会造成存储空间的浪费。
此外，在图中顶点的增加和删除操作时，需要重新调整矩阵的大小，开销较大。
二、邻接表存储方式邻接表是另一种常见的图存储方式，它使用链表来表示图中各个顶点之间的关系。
在邻接表中，每个顶点都有一个链表，链表中存储了与该顶点相邻的顶点。
实验中，我们同样以一个简单的例子来说明邻接表的存储方式。
假设有一个有向图，其中包含4个顶点和5条边。
我们可以使用一个包含4个链表的数组来表示这个图，数组中的每个元素表示一个顶点，链表中的元素表示与该顶点相邻的顶点。
邻接表的优点是在图中边的数量较少时，可以节省存储空间。
此外，在图中顶点的增加和删除操作时，开销较小。
然而，邻接表的缺点是判断两个顶点之间是否存在边的时间复杂度较高，需要遍历链表，时间复杂度为O(顶点的度数)。
三、性能比较与结论通过实验，我们对比了邻接矩阵和邻接表两种图存储方式在不同操作下的性能差异。
在判断两个顶点之间是否存在边的操作中，邻接矩阵的时间复杂度为O(1)，而邻接表的时间复杂度为O(顶点的度数)。
因此，在此操作下，邻接矩阵的性能更优。
实验五 图的邻接矩阵存储及遍历一、实验学时 2学时二、背景知识1．图的邻接矩阵存储结构设图G ＝（V ，E ）有 n>=1个顶点，其编号分别为1，2，…，n 。
描述图G 的邻接矩阵为二维数组A[1…n ，1…n]，A 的元素定义为：A []j i ,＝⎩⎨⎧，，01否则）属于）或（若（E ,,i j j i v v v v显然无向图的邻接矩阵一定是对称的。
对于网，其邻接矩阵A 的元素定义为：A []j i ,＝⎪⎩⎪⎨⎧∞=无邻接边到顶点若顶点若为该边上的权有邻接边，到顶点若顶点j i j i w j i w j i j i 0,,2.图的遍历深度优先遍历（DFS ）法：算法步骤：1）初始化：（1）置所有顶点“未访问”标志；（2）打印起始顶点；（3）置起始顶点“已访问”标志；（4）起始顶点进栈。
2）当栈非空时重复做：（1）取栈顶点；（2）如栈顶顶点存在被访问过的邻接顶点，则选择一个顶点做：① 打印该顶点；② 置顶点为“已访问”标志；③ 该顶点进栈；否则，当前栈顶顶点退栈。
3）结束。
广度优先遍历（BFS ）法：算法步骤：1) 初始化：（1）置所有顶点“未访问”标志；（2）打印起始顶点；（3）置起始顶点“已访问”标志；（4）起始顶点入队。
2）当队列非空时重复做：（1）取队首顶点；（2）对与队首顶点邻接的所有未被访问的顶点依次做：① 打印该顶点；② 置顶点为“已访问”标志；③ 该顶点入队；否则，当前队首顶点出队。
3) 结束。
三、目的要求1．掌握图的基本存储方法；2．掌握有关图的操作算法并用高级语言实现；3．熟练掌握图的两种搜索路径的遍历方法。
四、实验内容编写程序实现下图的邻接矩阵表示及其基础上的深度和广度优先遍历。
五、程序实例图的邻接矩阵表示法的C语言描述：#include<stdio.h>#include<conio.h>#include<stdlib.h>#define INFINITY 32767#define MAX_VERTEX_MUN 20int visited[20];typedef struct ArcCell{int adj;char *info;}ArcCell,AdjMatrix[20][20];typedef struct{char vexs[20];AdjMatrix arcs;int vexnum,arcnum;}MGragh;typedef struct QNode{int data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(0);Q.front->next=NULL;return 1;}int EnQueue(LinkQueue &Q,int e){QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->next=NULL;p->data=e;Q.rear->next=p;Q.rear=p;return 1;}int DeQueue(LinkQueue &Q,int e){QueuePtr p;if(Q.front==Q.rear)exit(0);p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return 1;}int EmptyQueue(LinkQueue Q){if(Q.front==Q.rear)return 1;return 0;}int LocateVex(MGragh G,char v){ int t;for(t=0;t<G.vexnum;t++)if(v==G.vexs[t])return t;return -1;}int FirstAdjVex(MGragh G,char v){ int i,j;i=LocateVex(G,v);if(i==-1)return 0;for(j=0;j<G.vexnum;j++)if(G.arcs[i][j].adj==1)return j;return -1;}int NextAdjVex(MGragh G,char v,char w){int j,i1,i2;i1=LocateVex(G,v);i2=LocateVex(G,w);if(i1==-1||i2==-1||i1==i2)return 0;for(j=i2+1;j<G.vexnum;j++)if(G.arcs[i1][i2].adj==1)return j;return -1;}int Visit(char v){printf("%c",v);return 1;}//构造无向图int CreateUDG(MGragh &G){int v,e,i,j,t;char v1,v2;printf("input the number of the vertices:");scanf("%d",&v);if(v<0)return 0;G.vexnum=v;printf("input the number of the arcs:");scanf("%d",&e);if(e<0)return 0;G.arcnum=e;for(t=0;t<G.vexnum;t++){printf("input the vertice %d 's information",t+1);fflush(stdin);scanf("%c",&G.vexs[t]);}for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}for(t=0;t<G.arcnum;t++){fflush(stdin);printf("input v1 and v2 is information :v1-v2");scanf("%c%*c%c",&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i==-1||j==-1||i==j)return 0;G.arcs[i][j].adj=G.arcs[j][i].adj=1;}return 1;}int BFSTraverse(MGragh G,int(*Visit)(char v)){LinkQueue Q;int v,w,u;for(v=0;v<G.vexnum;v++)visited[v]=0;InitQueue(Q);for(v=0;v<G.vexnum;v++){if(!visited[v]){visited[v]=1;Visit(G.vexs[v]);EnQueue(Q,v);while(!EmptyQueue(Q)){DeQueue(Q,v);w=FirstAdjVex(G,G.vexs[v]);for(;w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w])) if(!visited[w]){visited[w]=1;Visit(G.vexs[w]);EnQueue(Q,w);}}}}return 1;}void DFS(MGragh G,int v){int w;visited[v]=1;Visit(G.vexs[v]);w=FirstAdjVex(G,G.vexs[v]);for(;w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w])) if(!visited[w])DFS(G,w);}void DFSTraverse(MGragh G){int v;for(v=0;v<G.vexnum;v++)visited[v]=0;for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);}void main(){MGragh G;printf("create the UND G:\n");if(CreateUDG(G)){printf("output the UDG G in DFS order:");DFSTraverse(G);printf("\n");printf("output the UDG G in BFS order:");BFSTraverse(G,Visit);printf("\n");}}。
