例如，在社交网络分析中，异质图可以同时表示用户、内容和互动等多种元素，而在推荐系统中，它能够同时考虑用户偏好、商品属性和评分数据。...因此，无向图在描述对称性、连通性以及网络结构等方面具有独特的优势。在现实世界中，许多场景都可以抽象为无向图的形式。例如，社交网络中的用户之间的关系可以视作无向图中的边，每个用户是图中的一个顶点。...在邻接表中，每个顶点都通过一个链表来表示与之相邻的顶点，这使得添加、删除和查找边变得非常简单和快速。此外，邻接表还可以实现动态图结构，即在运行时可以轻松地添加和删除顶点和边。...邻接矩阵是一种用于表示图的矩阵形式，对于图中的每一个顶点，邻接矩阵中的对应行和列表示了该顶点与其他所有顶点的连接关系。...如果两个顶点之间存在一条边，那么邻接矩阵中对应位置的值就是 1；如果两个顶点之间不存在边，那么对应位置的值就是 0。由于同质图是无向图，所以它的邻接矩阵是一个方阵，即行数和列数相等的矩阵。
例如，一个网的节点信息和邻接矩阵如下图所示。在该网中，从节点a 到节点b 有边，且该边的权值为2，节点a 、b 在一维数组中的存储位置分别为0、1，因此 M [0][1]=2。...• 如果是无向图，则输入a b ，查询节点a、b 在节点数组Vex[]中的存储下标i 、j ，令Edge[i ][j ]=Edge[j ][i ]=1。...在实际应用中，也可以先输入节点信息并将其存入数组Vex[]。在输入边时直接输入节点的存储下标序号，这样可以节省查询节点下标所需的时间，从而提高效率。 4. 邻接矩阵的优缺点 （1）优点如下。...在实际应用中，如果在一个程序中只用到一个图，就可以用一个二维数组表示邻接矩阵，直接输入节点的下标，省去节点信息查询步骤。有时如果图无变化，则为了方便，可以省去输入操作，直接在程序头部定义邻接矩阵。... //邻接矩阵创建无向图 #include using namespace std; #define MaxVnum 100 //顶点数最大值 typedef char
就比如，上图中存储的是无向图，顶点A的第一个边表结点中邻接点域存放的编号为1，那么，我们通过查询顶点表中的编号即可得到该顶点为B，因此我们就得到了依附于顶点 A, B 的边 (A, B) ； 当存储的是有向图时...在邻接矩阵中，我们只要知道了两个顶点的信息，我们就能通过点 a_{ij} 的值来判断这两个点之间是否存在边，查找效率为 O(1)； 但是在邻接表中，不管是存储的有向图还是无向图，我们至少都要遍历一个顶点的边表...这个特点我们需要理解什么是唯一，在邻接矩阵中，矩阵中的信息是无法改变的，即我不管如何存储边的信息，它所对应的邻接矩阵是唯一的，有变化的无非就是矩阵中存储的值的变化； 但是在邻接表中，顶点表是不会改变，边表则是会变的...： 空间高效：存储复杂度仅 (O(V+E))，尤其适合边数较少的稀疏图； 动态灵活：快速增删边，适应图结构频繁变化的场景； 邻居遍历高效：直接访问边表，时间复杂度与顶点的实际度数相关，避免邻接矩阵的全行扫描...实际应用中，邻接表与邻接矩阵的取舍需基于图密度与操作需求：稀疏图优先邻接表，稠密图或频繁边查询场景倾向邻接矩阵。
邻接矩阵的优点是查询两个节点之间是否有连接的时间复杂度为 O(1)，但是缺点是当图中节点的数量很大时，矩阵的存储空间会非常庞大。...对于有边连接的两个顶点u和v，设定数组中的元素au和av为1，表示顶点u和v之间有边。如果图是带权重的，可以将数组中的元素au和av设为边的权重值。...在使用邻接矩阵存储图时，需要考虑到数组的大小限制和边的存储方式。通常可以使用二维数组、动态数组或稀疏矩阵等数据结构来实现邻接矩阵的存储。...4.图的最小生成树最小生成树是一个连通无向图的生成树中，边的权值和最小的生成树。图的最小生成树算法有普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。...普里姆算法：选择一个起始顶点，将起始顶点标记为已访问；在已访问的顶点集合中，选择一条与未访问顶点相连的最小权值边，并将该边的另外一个顶点标记为已访问；重复步骤2，直到所有顶点都标记为已访问，最小生成树构建完成
图分为： 有向图和无向图 有权图和无权图 而这种场景中，用户选择规格的时候，是没有先后顺序的，假设我们现在把每种规格看作是无向图的一个顶点的话，我们可以根据这些单项规格的组合规格，就可以画出一个像上图一样的无向图...[WechatIMG149.png] 有了图，那如何用代码描述图的结构呢，这就用到==邻接矩阵==的概念 邻接矩阵 线性代数里的知识，邻接矩阵，在代码中，表示它的方法是用一个 n x n 的二维数组来抽象描述邻接矩阵...把上面这个无向图用邻接矩阵(二维数组)表示出来就是： [WechatIMG150.png] 如果两个顶点互通（有连线），那么它们对应下标的值则为 1，否则为 0 假设现在我们有如下规格列表： specList...（specCombinationList）填写顶点的值 获得所有可选顶点，然后根据可选顶点填写同级顶点的值 sku 数据 先把规格数据写入，创建==specList==、==specCombinationList...，它继承于==AdjoinMatrix== 创建多规格选择邻接矩阵 我们这个多规格选择的邻接矩阵，需要提供一个查询可选顶点的方法：==getSpecscOptions== import AdjoinMatrix
输入：graph 是一个布尔值的二维数组，表示图的邻接矩阵。graph[i][j] 为 true 表示从节点 i 到节点 j 有一条直接的边。 2....智谱清言： 在离散数学中，传递闭包是关系的一个概念，它表示关系中的所有传递的二元组。给定一个关系R，其传递闭包是包含R中所有元素的最小关系，同时也是一个传递关系。...我们用逻辑或运算符更新闭包矩阵中的每一个值。 4. 打印结果：以适当的格式输出传递闭包的结果。...混元： 在计算机科学中，传递闭包（transitive closure）是一个有向图的属性，它告诉我们在图中从一个节点到另一个节点是否存在路径。...然后，我们使用一个类似 Floyd-Warshall 的动态规划算法来计算传递闭包。最后，我们打印出传递闭包矩阵。 请注意，这个示例假设图是无权的，并且所有的边都是无向的。
另外，假如存储的是稀疏图，也就是顶点很多，但是每个顶点的边不多的一种图。那么使用邻接矩阵存储将更浪费存储空间，因为很多位置的值都是 0，这些 0 其实都是没有用的。...对于无向图来说是类似的，每个节点对应的链表中存储的是该节点所相连的顶点。 ? 邻接表相比邻接矩阵的一个优点就是节省空间，但是使用起来比较耗时间（时间换空间的设计思想）。...而且链表的方式对于缓存来说不太友好。所以，综上来说在邻接表中查询两个顶点的关系没有邻接矩阵那么高效了。 但是，为了让查询变得更加高效。...但是想要查看有哪些节点指向了 4 这个顶点，那么就需要逆邻接表了。 ? 2.3. 总结 综上来说，邻接矩阵的缺点是比较浪费空间，但是优点是查询效率高，还方便矩阵运算。...邻接表的优点是节省存储空间，但是不方便查找（查找效率肯定没邻接矩阵高）。对于此，我们可以将链表替换成查询效率较高的动态数据结构，比如平衡二叉树（红黑树）、跳表、散列表等。 3.
Floyd算法则通过动态规划求解所有节点之间的最短路径。1.1 图常见类型与术语☀️1.1.1 无向图和有向图无向图和有向图是两种常见的图形结构，都是由节点和边构成的。...具体地，数组中每个元素的值为1表示存在边；为0表示不存在边。当图是有向图时，邻接矩阵是一个方阵，且只需要考虑一条边的方向。...基于邻接矩阵实现的无向图类 */class GraphAdjMat { List vertices; // 顶点列表，元素代表“顶点值”，索引代表“顶点索引” List顶点列表中添加新顶点的值 vertices.Add(val); // 在邻接矩阵中添加一行...在图中，节点表示键，边表示值，可以查询和更新数据。这些都是图在生活中的一些应用场景，图还有很多其他的应用，比如机器学习中的决策树、数据挖掘中的聚类等。
将要查找的数据与根节点的值进行比较，如果相等就返回，如果小于就到左子树中递归查找，如果大于就到右子树中递归查找。 5.4.实现 结构 ? ? 插入 ? ? 删除 ? ? 查询 ?...7.1.无向图 从顶点 Vi到 Vj的边没有方向，则称这条边为无向边。顶点和无向边组成的图为无向图 ?...设图 G 有n个顶点，则邻接矩阵是一个n×n的方阵 ? 1. 无向图的邻接矩阵 在无向图的邻接矩阵中，如果 的交点为 1，则表示两个顶点连通，为 0 则不连通。...在无向图的邻接矩阵中，主对角元素都为 0，也就是说顶点自身没有连通关系 ?...带权重图的邻接矩阵 有些图的每条边上都带有权重，如果要将这些权值保存下来，则可以采用权值代替矩阵中的 0、1，在权值不存在的元素之间用 ∞ 表示 ?
(邻接矩阵) 导读 大家好，很高兴又和大家见面啦！！！ 在上一篇中，我们探讨了图的基本概念与术语，如顶点、边、有向图与无向图的区别等。...2.1 邻接矩阵 在邻接矩阵中，我们可以用0和1来表示顶点之间的邻接关系： 在邻接矩阵中，行坐标和列坐标所代表的结点与一维数组中结点对应的下标一致，矩阵的值就是依附于该顶点的边。...比如上图中的边 (A, B) 对应到矩阵 A 中，那就是点a_{01} 与点 a_{10} 这两个点的值均为1； 如果上图为无向图，且我们要表示弧 a_{01} = 1 与点 a_{10}...对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非预设值元素如 \infty）的个数正好是顶点 i 的度 TD(v_i) 。...拓展思考：若图的顶点动态增减，邻接矩阵如何优化？权值无穷大（∞）在代码中应如何合理表示？欢迎在评论区探讨你的见解，或继续阅读本系列的下一篇——《邻接表：稀疏图的存储利器》。
顶点的入度，表示有多少条边指向这个顶点； 顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。 ? 2. 存储方法 2.1 邻接矩阵 Adjacency Matrix ?...存储比较浪费，有的顶点很多，但是边很少（微信用户很多，每个用户的好友只百个），用邻接矩阵存储，其中大部分都是0，浪费。 邻接矩阵优点。...首先，邻接矩阵的存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。 其次，用邻接矩阵存储图的另外一个好处是方便计算（矩阵运算）。...3.5 BFS代码（基于邻接矩阵） /** * @description: 基于邻接矩阵的无向图 * @author: michael ming * @date: 2019/6/11 21:50...//顶点信息 int GType; //图的类型（0无向图，1有向图） int v; //顶点个数 int e;
不仅如此，我们还希望这些边和点的集合可以被更高效地发现，比如举出一个顶点，就可以很快地找到它的邻居们。所以直接存储所有的边和顶点查询效率不够高，因此计算机工作者们选取了邻接矩阵和邻接表。...相应的，如果有一条有向边BA，它的权值为4，我们就将G[1][0]填充为4。 ? 邻接矩阵的例子 小可：那么如何表示无向边呢？ Mr. 王：在邻接矩阵的表示中，一般不去区分有向图和无向图。...无向图的表示方法和有向图是一致的，只不过在无向图中，对于长度为3的无向边AB，我们将G[1][0]和G[0][1]的值都改为3即可。...在这里，其实一条无向边可以看作，两条方向相反、权值相等、连接相同两个顶点的有向边。 ? 无向图的邻接矩阵 小可：那些没有边的数据域呢？ Mr. 王：一般来说，我们会用权值来表示两个顶点的距离。...另外，对于无权的图，我们将边的权值视作1，这样方便计算无权图中路径的长度，也就是经过边的数量。 小可：可是邻接矩阵占用空间很大啊，不论两个顶点之间是不是真的有一条边，我们都要用一个数来存储。
下图中的a和b分别为无向图和有向图的邻接矩阵的样例，对于不存在的边可以赋值为无穷或0。 ?...性能分析 时间和空间性能分析 时间性能： 依据上面的代码分析，当进行静态操作时由于向量“循秩访问”的特长与优势，操作均需O(1)时间。然而在顶点的动态操作上面却很耗时。...当然对于无相图，无向图的邻接矩阵必为对称矩阵。每条边都被储存了两篇，接近一半的空间被浪费了，因此可以通过压缩储存的方法来提高空间性能。...复杂度分析 可见，邻接表所含列表数等于顶点总数n，每条边在其中仅存放一次（有向图）或两次（无向图），故空间总量为O(n + e)，与图自身的规模相当，较之邻接矩阵有很大改进。...当然，空间性能的这一改进，需以某些方面时间性能的降低为代价。例如查询两点之间是否存在边时共需O(n)时间。
PS：邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。...图的邻接表储存方式相对于邻接矩阵比较节约空间，对于邻接矩阵需要分别把顶点和边（顶点之间的关系）用一维数组和二维数组储存起来。...而邻接表则是把顶点按照顺序储存到一维数组中，然后再通过链式方式，把有关系的顶点下标链接到后方，咱们先不考虑权重问题，结构体定义简单一点，当然加上权值也不难。下方看图解释。...邻接表 有向图 无向图 逆邻接表 有向图 邻接表实现步骤 结构体 创建图 顶点和边数，顶点需要用一维数组保存 获取顶点的下标，因为链接结点中的index域是顶点的下标值。...邻接矩阵 一维数组（顶点） 二维数组（邻接关系） 1：易于判定顶点是否邻接，查顶点的邻接点 2：插入、删除顶点复杂 邻接表 头结点（顶点） 表结点（邻接关系） 1：易于：查询某顶点的邻接点，边或弧的插入
带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度 几种特殊形态的图： 无向完全图：无向图中任意两个顶点之间都存在边 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧...： 邻接矩阵法的性能分析： 空间复杂度：O(|V|^2) ——只和顶点数相关，和实际的边数无关 适合用于存储稠密图 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）...邻接矩阵法的性质： 邻接表法 #define MaxVertexNum 100 //顶点数目的最大值 #define INFINITY 最大的int值 //宏定义常量"无穷" typedef char...）也可能不同 设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree, MST） 最小生成树可能有多个，但边的权值之和总是唯一且最小的...最短路径问题之Floyd算法 ——邻接矩阵表示 算法思想： Floyd算法：求出每一对顶点之间的最短路径 使用动态规划思想，将问题的求解分为多个阶段 对于n个顶点的图G，求任意一对顶点 Vi
； ilink 指向的时依附于顶点 i 的下一条边 jlink 指向的时依附于顶点 j 的下一条边 info 中存放的时该边的相关信息，如边的权值 每个顶点也用一个结点表示，它由两个域组成： data...在邻接矩阵中，行数与列数都是图的顶点数 |V| ，因此对应的时间复杂度为 O(|V|) ； 在邻接表中，当我们要查找一个顶点的相邻边时，对于有向图与无向图而言，其查找邻边的时间复杂度也是有所区别： 无向图中...5.3 删除边或结点 在邻接矩阵中： 当我们要删除一条边时，只需要修改对应边在矩阵中的值即可 当我们要删除一个顶点时，需要移动大量的数据 在邻接表中： 有向图： 删除边：只需要删除对应的边结点即可...只能够存储有向图 在邻接多重表中，只能够存储无向图 5.5 表示方式 邻接矩阵是由各个顶点组成的矩阵，因此，其表示方式是唯一的； 在邻接表、十字链表以及邻接多重表中，由于边表的信息是通过链表进行的存储，...从邻接矩阵的刚性布局到链式结构的动态灵动，每一种存储方案都是空间与时间的精妙权衡，而邻接多重表无疑是高频删边场景的无向图终极答案。
： 按照索引查询元素的时候速度很快 存储大两的数据 按照索引去遍历数组 定义方便，访问灵活 数组的缺点： 根据内容查找会很慢 数组的大小一经确定是不能改变的，不适合动态存储 数组只能存储相同类型数据 增加删除元素效率慢...11.png 插入删除：链表的性能好undefined链表没有大小限制，支持动态扩容，因为链表的每个节点都需要存储前驱/后驱节点的指针，内存消耗会翻倍 查询修改：数组性能好 class Node {...prototype属性 当试图得到一个对象的属性时，如果这个对象的本身不存在这个属性，那么就会去它的 proto 属性中找(去它的构造函数的prototype属性中去寻找) 当调用这个对象本身并不存在的属性或者方法时...树的度：树中节点度的最大值 叶子(终端结点): 度为0的结点 分支结点(非终端结点)：度不为0的结点。...45.png 自环：即一条链接一个顶点和自身的边 平行边：连接同一对顶点的两条边 52.png 图的分类 无向图: 边没有方向的图称为无向图，边的作用仅仅是连接两个顶点，没有其他含义 有向图: 边不仅连接两个顶点
无向完全图： 有向完全图： 含有n个顶点的无向完全图有多少条边？ n×(n-1)/2条边 含有n个顶点的有向完全图有多少条弧？...数据关系R：R={VR}；VR={|v,w∈V 且 P(v,w), 表示从v到w的弧， 谓词P(v,w)...操作结果：在图G中添加新顶点。 ………………（参见P156-257） } 2.图的存储结构 a.邻接矩阵(数组)表示 是否可以采用顺序存储结构存储图?...算法) b.Dijkstra（迪杰斯特拉）算法 Dijkstra算法描述： （1）设A[n][n]为有向网的带权邻接矩阵， A[i][j]表示弧（vi，vj )的权值， S为已找到从源点...辅助数组dist[n]为各终点当前找到的最短路径的长度，初始值为： dist[i]＝A[v0 ,i] //即邻接矩阵中第v0行的权值 （2）选择u，使得
对于加权图而言，数组中存储就是对应的权值。...邻接矩阵的特点： 优点：实现简单，可以直接查询顶点 Vi 与 Vj 之间是否存在边（或者直接查询其边的权值），因此增删查改操作的效率很高，时间复杂度均为 O(1)。...2.1.2 添加/删除边 直接修改邻接矩阵指定的边的值即可，如果是无向图，因此需要同时更新两个方向的边。 2.1.3 添加顶点 在邻接矩阵的尾部添加一行一列，并全部填充为 0。...缺点：邻接表需要遍历链表来查找边，因此其时间效率不如邻接矩阵。 2.2.1 初始化 假设无向图的顶点总数为 、边总数为 ，在邻接表中创建 个顶点和 2 条边。...2.2.2 添加边 在顶点对应链表的末尾添加边即可，因为是无向图，所以需要同时添加两个方向的边。 2.2.3 删除边 在顶点对应链表中查找并删除指定边，在无向图中，需要同时删除两个方向的边。
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM
