下载文档原格式
图-存储结构-数组表⽰法（邻接矩阵）⽂字描述 ⽤两个数组分别存储顶点信息和边/弧信息。
⽰意图算法分析 构造⼀个采⽤邻接矩阵作存储结构、具有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。
邻接矩阵的有向图⼀、邻接矩阵有向图的介绍邻接矩阵有向图是指通过邻接矩阵表⽰的有向图。
待补充；上⾯的图G2包含了"A,B,C,D,E,F,G"共7个顶点，⽽且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9条边。
上图右边的矩阵是G2在内存中的邻接矩阵⽰意图。
A[i][j]=1表⽰第i个顶点到第j个顶点是⼀条边，A[i][j]=0则表⽰不是⼀条边；⽽A[i][j]表⽰的是第i⾏第j列的值；例如，A[1,2]=1，表⽰第1个顶点(即顶点B)到第2个顶点(C)是⼀条边。
⼆、邻接矩阵有向图的代码说明1. 基本定义#define MAX 100class MatrixDG {private:char mVexs[MAX]; // 顶点集合int mVexNum; // 顶点数int mEdgNum; // 边数int mMatrix[MAX][MAX]; // 邻接矩阵public:// 创建图(⾃⼰输⼊数据)MatrixDG();// 创建图(⽤已提供的矩阵)MatrixDG(char vexs[], int vlen, char edges[][2], int elen);~MatrixDG();// 打印矩阵队列图void print();private:// 读取⼀个输⼊字符char readChar();// 返回ch在mMatrix矩阵中的位置int getPosition(char ch);};MatrixDG是邻接矩阵有向图对应的结构体。
mVexs⽤于保存顶点，mVexNum是顶点数，mEdgNum是边数；mMatrix则是⽤于保存矩阵信息的⼆维数组。
例如，mMatrix[i][j]=1，则表⽰"顶点i(即mVexs[i])"和"顶点j(即mVexs[j])"是邻接点，且顶点i是起点，顶点j是终点。
1. 假设用于通信的电文仅由8个字母（a, b, c, d, e, f, g, h ）组成，字母在电文中出现的频率分别是0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21和0.10。
为这8个字母设计一套哈夫曼编码，并计算其一个字母的平均编码长度（二进制位数）。
以上述8个字母为叶子结点构造的一棵最优二叉树如下：由其可得一套哈夫曼编码：a 0010b 10c 00000d 0001e 01f 00001g 11h 0011平均编码长度是 ∑P i ∙L i = 0.07×4 + 0.19×2 + 0.02×5 + 0.06×4 + 0.32×2 + 0.03×5 + 0.21×2 + 0.10×4 = 2.612. 无向网的5个顶点依序为a, b, c, d, e ，其邻接矩阵如下，画出该图及其最小生成树。
⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞713741143101338111083. 画出如下有向图的邻接表。
4. 编写运用栈实现图的深度优先搜索的非递归算法。
void dfs(graph G, int v0) // 一个连通分量上的深度优先搜索{ int v, w;visit(G,v0); // 访问出发顶点G.list[v0].visited=1;init_stack(S); // 初始化栈push(S,v0); // 出发顶点地址（下标）入栈while(!empty_stack(S)) // 当栈非空则执行以下循环{ v=gettop(S); // 取栈顶w=first_adj(G,v); // 求其第一个邻接点while(w && G.list[w].visited) // 寻找一个未被访问的邻接点 w=next_adj(G,v,w);if(w) // 若存在一个v的未被访问的邻接点w{ visit(G,w); // 访问wG.list[w].visited=1;push(S,w); // w入栈}else pop(S); // 否则，v的所有邻接点已访问或无邻接点则v出栈}}void depth_first_search(graph G) // 整个图的遍历{ for(int i=0; i<G.vexnum; i++) G.list[i].visited=0; // 被访标记复位 for(int i=0; i<G.vexnum; i++)if(G.list[i].visited==0) dfs(G,i);}。
算法与数据结构课程设计报告系（院）：计算机科学学院专业班级：教技1001姓名：李##学号： ******### 指导教师：***设计时间：2012.6.16 - 2012.6.24设计地点：4号楼2号机房目录一、设计方案 (1)二、实现过程以及代码 (2)三、测试 (20)四、结论和分析 (23)五、难点和收获 (23)一、 设计方案1.程序设计基本过程：拿到课程设计任务书，按照要求，需要设计有向图、有向网、无向图 、无向网四种图，以及邻接矩阵、邻接表两种数据存储结构，三层以上的显示菜单。
图的操作中又包含了有关线性表、栈和队列的基本操作。
由于显示菜单已给出，剩下的任务就是把函数写入其中。
2.程序流程图：预定义 定义结构体 定义变量 各种函数3.程序设计的原理：图的操作都是以两种存储结构为基础的：邻接矩阵存储结构和邻接表存储结构，如有向图，有向网，无向图，无向网的创建，其他的操作都是在四种图创建后才开始进行的。
所以，首先必须理解两种存储结构的定义。
图的邻接矩阵存储结构即图的数组表示法。
用两个数组分别存储数据元素（如顶点）的信息和数据元素之间的关系（如边或弧）的信息。
用邻接矩阵存储结构的图具有以下几点特征：（一）：顶点数：vexnum ，边（弧）数：arcnum ，图的种类：kind ；（二）：邻接矩阵：arcs(1顶点关系类型:adj 2相关信息:*info)；（三）：顶点向量（顶点名）：vexs[]；其优点是以二维数组表示有n 个顶点的图时，需存放n 个顶点的信息和n*n 条弧的信息存储量。
借助邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求出各个顶点的度。
缺点是时间复杂度是O （n*n ）,例如，构造一个具有n 个顶点和e 条边的无向网的时间复杂度为O （n*n+e*n ）。
图的邻接表存储结构是图的一种链式存储结构。
对图中的每个顶点建立一个单链表，每个结点由三个域组成，邻接点域adjvex （弧尾在邻接表链表中的位序），链域nextarc （下一条弧），数据域info(权值)。
网络的矩阵分析方法
网络的矩阵分析方法是一种用矩阵来描述和分析网络结构、特性和行为的方法。
这种方法将网络表示为矩阵，并利用矩阵运算来研究网络的各种属性。
常见的网络矩阵分析方法包括：
1. 邻接矩阵（Adjacency Matrix）：将网络表示为一个二维矩阵，其中矩阵的行和列分别代表网络中的节点，矩阵的元素表示节点之间的连接关系。
邻接矩阵可以用于描述网络的结构和拓扑关系。
2. 关联矩阵（Incidence Matrix）：将网络表示为一个二维矩阵，其中矩阵的行代表网络中的节点，列代表网络中的边，矩阵的元素表示该节点与该边的关联关系。
关联矩阵可以用于描述网络的连接方式和路径。
3. 度矩阵（Degree Matrix）：将网络表示为一个对角矩阵，其中矩阵的对角线元素表示节点的度，即节点的连接数。
度矩阵可以用于描述节点的中心性和重要性。
4. 邻接矩阵的幂次计算：通过对邻接矩阵进行幂次计算，可以得到节点之间的路径数量和长度信息，可以用于计算网络的连通性和可达性。
5. 特征值和特征向量分析：通过计算网络矩阵的特征值和特征向量，可以得到
网络的特征信息，如网络的谱半径、特征中心性等。
6. Laplacian矩阵（拉普拉斯矩阵）：通过对邻接矩阵和度矩阵进行运算得到的矩阵，可以用于研究网络的连通性、划分和传播等问题。
通过上述矩阵分析方法，可以揭示网络的结构、功能和行为特征，对于网络科学、社交网络分析、复杂网络研究等领域具有重要的应用价值。
邻接矩阵的实验原理及应用实验原理邻接矩阵是一种图的表示方法，通过矩阵的形式记录图中各个顶点之间的连接关系。
邻接矩阵可以用于描述有向图和无向图。
无向图的邻接矩阵无向图的邻接矩阵是一个方阵，其中的每个元素表示图中两个顶点之间是否存在边。
如果顶点i和顶点j之间存在边，则邻接矩阵的第i行第j列和第j行第i列的元素值都为1；否则，为0。
邻接矩阵的对角线上的元素表示各个顶点的度数。
有向图的邻接矩阵有向图的邻接矩阵同样是一个方阵，其中的每个元素表示从顶点i到顶点j是否存在边。
如果顶点i到顶点j存在边，则邻接矩阵的第i行第j列的元素值为1；否则，为0。
邻接矩阵的表示方法邻接矩阵可以用二维数组来表示，数组的大小为n×n，其中n为图中顶点的个数。
数组的下标表示顶点的编号，而数组中的元素表示邻接关系。
应用邻接矩阵在图的算法和应用领域有重要的应用。
图的遍历使用邻接矩阵可以进行图的遍历操作，包括深度优先遍历和广度优先遍历。
通过对邻接矩阵的遍历，可以访问图中所有的顶点和边。
最短路径算法邻接矩阵可以作为最短路径算法的基本数据结构。
通过邻接矩阵，可以方便地计算两个顶点之间的最短路径。
最小生成树算法最小生成树算法可以使用邻接矩阵作为数据结构。
通过构建邻接矩阵，并使用Prim算法或Kruskal算法，可以生成图的最小生成树。
图的连通性判断邻接矩阵可以用来判断图的连通性。
通过对邻接矩阵进行深度优先搜索或广度优先搜索，可以确定图中的连通分量。
图的可达性分析邻接矩阵可以用于分析图中顶点之间的可达性。
通过对邻接矩阵进行矩阵运算，可以得到图中任意两个顶点之间的可达性。
总结邻接矩阵是一种表示图的方法，通过矩阵的形式记录图中各个顶点之间的连接关系。
邻接矩阵具有简单、直观、易于操作等优点，在图的算法和应用中有广泛的应用。
通过对邻接矩阵的遍历、最短路径算法、最小生成树算法、连通性判断和可达性分析等操作，可以解决各种与图相关的问题。
以上就是邻接矩阵的实验原理及应用，希望对你有所帮助。
邻接矩阵与关联矩阵的计算与应用矩阵作为一种重要的数学工具，广泛应用于多个学科和领域。
在图论中，邻接矩阵和关联矩阵是两个常用的矩阵表示方法，用于描述图的结构和关系。
本文将介绍邻接矩阵和关联矩阵的计算方法以及它们在实际应用中的使用。
一、邻接矩阵的计算与应用邻接矩阵是一种常用的图表示方法，用于描述图中节点之间的连接关系。
对于一个无向图，邻接矩阵是一个对称的矩阵，而对于有向图，邻接矩阵则不一定对称。
邻接矩阵的计算可以通过以下步骤进行：1. 创建一个n×n的矩阵，其中n是图中节点的个数。
2. 将矩阵的所有元素初始化为0。
3. 对于图中的每一条边(i,j)，将矩阵的第i行第j列和第j行第i列的元素置为1，表示节点i与节点j之间存在边。
通过邻接矩阵可以方便地判断图中任意两个节点之间是否存在边，以及获取节点的度数等信息。
同时，在图的遍历、连通性检测等算法中，邻接矩阵也发挥着重要的作用。
二、关联矩阵的计算与应用关联矩阵是另一种常见的图表示方法，用于描述图中节点与边之间的连接关系。
在关联矩阵中，行表示节点，列表示边，矩阵的元素表示节点与边之间的连接关系。
关联矩阵的计算可以通过以下步骤进行：1. 创建一个n×m的矩阵，其中n是图中节点的个数，m是图中边的个数。
2. 将矩阵的所有元素初始化为0。
3. 对于图中的每一条边(i,j)，将矩阵的第i行第k列和第j行第k列的元素置为1，表示边k连接了节点i和节点j。
通过关联矩阵可以方便地获取节点和边的信息，如节点的度数、边的权重等。
同时，关联矩阵也可以用于图的聚类、社区发现等算法中，对于图的结构进行分析与推断。
三、邻接矩阵与关联矩阵的应用举例1. 社交网络分析：邻接矩阵和关联矩阵可以用于分析社交网络中的节点间关系，如好友关系、兴趣关联等。
通过计算节点间的邻居关系和路径长度，可以进行社区发现、重要节点挖掘等任务。
2. 交通网络规划：邻接矩阵和关联矩阵可以用于描述交通网络中的路段与交叉口之间的连接关系。
离散数学有向图的路径表示方法有向图是离散数学中的一个重要概念，它由一组顶点和一组有向边组成。
在有向图中，每条边都有一个方向，表示从一个顶点指向另一个顶点。
有向图可以用于表示不同实际问题中的关系和流程，因此了解有向图的路径表示方法对于解决问题至关重要。
在离散数学中，有向图的路径表示方法有多种，以下将介绍三种常见的方法，分别是邻接矩阵表示法、邻接表表示法和关联矩阵表示法。
1. 邻接矩阵表示法：邻接矩阵是一个二维矩阵，用于表示有向图中各顶点之间的关系。
矩阵的行和列代表图中的顶点，矩阵中的元素表示对应顶点之间是否存在直接连接的边。
如果两个顶点之间存在边，则对应的矩阵元素为1；如果两个顶点之间不存在边，则对应的矩阵元素为0。
例如，对于一个有向图G，如果存在一条从顶点A到顶点B的边，则在邻接矩阵中的第A行第B列的元素为1。
邻接矩阵表示法可以通过矩阵的行、列索引来表示有向图中的路径，路径上的顺序即为顶点在矩阵中的索引顺序。
2. 邻接表表示法：邻接表是一种更加紧凑的表示有向图的方法。
它由一个顶点数组和一个边链表组成。
顶点数组中的每个元素表示图中的一个顶点，边链表中的每个节点表示从该顶点出发的边。
邻接表使用链表的方式记录每个顶点所连接的边，其中链表的节点保存了边的终点以及指向下一条边的指针。
在邻接表表示法中，可以通过遍历链表来获取某个顶点的所有直接连接的顶点，从而表示有向图中的路径。
遍历链表的顺序即为顶点与顶点之间路径的顺序。
3. 关联矩阵表示法：关联矩阵是一个二维矩阵，用于表示有向图中顶点和边之间的关系。
矩阵的行代表顶点，矩阵的列代表边，矩阵中的元素表示对应顶点与边之间的连接关系。
关联矩阵表示法可以将有向图中的路径转化为矩阵中的非零元素组成的向量。
矩阵中的每一列表示一条边，矩阵中的每一行表示一个顶点。
如果某个顶点在路径上通过某条边，则对应的矩阵元素为-1；如果某个顶点是路径的起点，则对应的矩阵元素为1；如果某个顶点是路径的终点，则对应的矩阵元素为-1。
一．简要介绍：哈密顿回路：哈密顿图是一个无向图，由指定的起点前往指定的终点，途径过所有的其他节点且只经过一次。
哈密顿回路即从一指定顶点出发，经历所有点后回到起点。
最短哈密顿回路：在一个有向网中，分别计算每条哈密顿回路上的权值之和，找出其中最小的权值之和。
二．算法：（1）.列出有向网中的所有边，并按权值建立邻接矩阵。
（2）取前n条边，判断它是否构成哈密顿回路。
（条件：1.n个顶点全出现；2.定点出现的次数等于2并且每一个顶点在弧头和弧尾各出现一次；3.不存在小于n个顶点的回路即小回路。
）三．描述：（1）.用邻接矩阵存放有向网；（2）用队列存放结点；（3）用指针指向要访问的点。
四．算法流程：分析：本题是一个典型的哈密顿环算法题。
主要思想是用回溯法求所有的方法数，再通过所有方法数的比较得到相应于题目的最优解。
（1）.首先有十一个城市，为十一个城市分别标号，以便方便准确索引和准确定位，建立了三个邻接矩阵分别用来是一个bool 型和两个double型。
Bool 型用1来表示两个城市之间相通，0表示不相通。
Double型分别用来存放与bool型相对应的经过两个城市的时间和价格。
（2）列出有向网中所有的边，为了简化题目，在遇到两点间既可以走水路又可以走陆路的情况时，据已知条件可以分别算出价钱较低和时间较短的路径，这样就保证了任意两个点之间只存在一条路径，也就符合了哈密顿环的算法成立的要求。
（3）统计不同顶点出现的个数和顶点出现的次数，联系上述描述中所说的条件添加限制条件。
、（4）输出最后所求的最优解。
五．复杂度：（1）因为没有实现路径的权值的有序排列，所以每次都要等遍历完所有的方法数，通过不断与min值比较替换，才能得出最终的min 值，（m+1）*m*(m-1)*^1=(m+1)!,即时间复杂度为n!;六：说明：（1）本题中所有可行的两做城市之间的连线是双向的，即既可以从A城市到B城市，又从B城市到A城市，所以最后的结论最短路该有两个方向的走法，可以忽略方向，这样可以大大节省空间。
第2讲图的存储结构——教学讲义本讲介绍4种较常用的存储表示法：①邻接矩阵表示法；②邻接表；③邻接多重表；④十字链表。
由于每种方法各有利弊，因此可以根据实际应用问题来选择合适的存储表示方法。
①邻接矩阵表示法图的邻接矩阵表示法（Adjacency Matrix）也称作数组表示法。
它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。
若G是一具有n个顶点的无权图，G的邻接矩阵是具有如下性质的n×n矩阵A：上图所示G1和G2的邻接矩阵如下所示。
若图G是一个有n个顶点的网，则它的邻接矩阵是具有如下性质的n×n矩阵AA1=图G1,G2的邻接矩阵(a) G1是有向图(b) G2是无向图例如：下图就是一个有向网及其邻接矩阵的示例。
邻接矩阵表示法的C 语言描述如下：#define MAX_VERTEX_NUM 20 /*最多顶点个数*/#define INFINITY 32768 /*表示极大值，即∞*//* 图的种类：DG 表示有向图, DN 表示有向网, UDG 表示无向图, UDN 表示无向网 */typedef enum{DG, DN, UDG, UDN} GraphKind;typedef char VertexData; /*假设顶点数据为字符型*/ typedef struct ArcNode{AdjType adj; /* 对于无权图，用1或0表示是否相邻；对带权图，则为权值类型 */OtherInfo info; } ArcNode;typedef struct{VertexData vertex[MAX_VERTEX_NUM]; /*顶点向量*/ArcNode arcs [MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /*邻接矩阵*/ int vexnum, arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类标志*/ } AdjMatrix; /*（Adjacency Matrix Graph ）*/邻接矩阵法的特点如下：● 存储空间: 对于无向图而言，它的邻接矩阵是对称矩阵（因为若（v i ，v j ）∈E （G ），则（v j ，v i ）∈E （G ）），因此可以采用特殊矩阵的压缩存储法，即只存储其下三角即可，这样，一个具有n 个顶点的无向图G ，它的邻接矩阵需要n （n -1）/2个存储空间即可。
