SciPy 稀疏矩阵（4）：LIL（下）

上回说到，LIL 通过把稀疏矩阵看成是有序稀疏向量组，通过对稀疏向量组中的稀疏向量进行压缩存储来达到压缩存储稀疏矩阵的目的。这一回从图数据结构开始！

图数据结构

图数据结构是一种非线性的数据结构，用于表示对象之间的复杂关系。在图数据结构中，每个对象都被表示为一个节点（或顶点），而对象之间的关系则被表示为连接这些节点的边。图数据结构具有广泛的应用领域，例如社交网络、搜索引擎、网络路由等。在社交网络中，图数据结构用于表示用户之间的关系，例如朋友关系、关注关系等。每个用户可以被表示为一个节点，而用户之间的关系则可以被表示为连接这些节点的边。通过图数据结构，可以轻松地查询用户之间的关系，例如查找某个用户的所有朋友或者查找两个用户之间的共同好友等。搜索引擎也广泛使用图数据结构。在搜索引擎中，网页之间的关系可以被表示为一个图，其中每个网页都是一个节点，而网页之间的链接关系则可以被表示为连接这些节点的边。通过图数据结构，搜索引擎可以快速地找到与用户查询相关的网页，并按照相关度进行排序，从而为用户提供更加准确的搜索结果。除了社交网络和搜索引擎之外，图数据结构还在许多其他领域得到了广泛的应用，例如网络路由、电路设计、化学分析等。随着技术的不断发展，图数据结构将会在更多的领域中发挥其重要作用。

同质图是一种图数据结构，在这种结构中，所有的节点代表相同的实体类型，所有的边代表相同的相互作用或关系类型。这种图形结构的统一性使得所有节点和边都可以用相同的方法进行处理，它简化了对网络的分析，因为它假设了网络中的所有交互都是相似的。同质图由于其简单性，在许多领域都有广泛的应用。例如，在社交网络分析中，它可以用来研究人们之间的社交联系；在通信网络中，它可以用来分析通信模式；在合作网络中，它可以用来研究科学家、研究人员或演员之间的合作关系；在交通运输网络中，它可以用来理解交通流动；在生物信息学中，它可以用来探索生物分子之间的相互作用。在同质图的分析中，常用的技术和算法包括图论的基本概念，如度、路径、连通性等，以及社区检测、中心性度量、网络扩散模型等。这些工具和技术可以帮助研究者从同质图中提取出有意义的模式和洞察，以解决网络科学、社会物理学、复杂系统分析等领域的问题。

异质图是一种复杂的关系网络，它在数据结构中包含了多种类型的节点和边。这种图形结构能够真实地模拟现实世界中的各种复杂系统，因为它允许节点和边代表不同的事物和关系。例如，在社交网络分析中，异质图可以同时表示用户、内容和互动等多种元素，而在推荐系统中，它能够同时考虑用户偏好、商品属性和评分数据。在知识图谱领域，异质图被用来表达实体、概念和它们之间的各种关系，从而支持知识查询和推理。在生物信息学中，异质图可以用来建模蛋白质、基因和它们之间的相互作用。在交通网络分析中，异质图能够同时考虑道路、交通信号和车辆等多种因素，以优化交通流量。为了处理异质图，研究者们开发了多种特定的算法和技术，如图嵌入、图神经网络和元路径分析等，以应对节点和关系的多样性带来的挑战。

无向图和有向图

无向图，作为一种基础的图论概念，在数学、计算机科学以及众多实际应用领域中都发挥着关键作用。与有向图相比，无向图中的边不具有方向性，这意味着边连接的两个顶点之间是相互可达的。因此，无向图在描述对称性、连通性以及网络结构等方面具有独特的优势。在现实世界中，许多场景都可以抽象为无向图的形式。例如，社交网络中的用户之间的关系可以视作无向图中的边，每个用户是图中的一个顶点。在这种表示下，研究人员可以分析用户间的互动模式、信息传播路径以及社区结构等。此外，无向图还在电路设计、物流优化、生物信息学等领域有着广泛的应用。无向图的研究不仅涉及基础图论知识，还包括了复杂网络分析、图算法设计等多个方面。对于无向图的研究不仅有助于我们深入理解复杂系统的结构和行为，还能为实际问题的解决提供有力的理论支持和实践指导。随着图计算技术的发展，无向图将在更多领域展现出其强大的应用潜力。

有向图是一种广泛应用于计算机科学、运筹学、社会学等领域的重要数据结构。与无向图相比，有向图更加复杂，因为它不仅包含了节点之间的连接关系，还指明了连接的方向。这种有向性使得有向图在表达某些特定问题时更加直观和有效。在有向图中，每个节点都表示一个实体或对象，而连接节点的有向边则表示实体之间的特定关系或交互。例如，在社交网络中，节点可以代表个人，有向边则可以表示一个人对另一个人的关注或信任关系。在交通网络中，节点可以代表路口或站点，有向边则可以表示交通流向的方向。有向图的另一个重要特性是它的可达性。由于有向边具有方向性，因此从一个节点出发，不一定能够到达图中的所有其他节点。这种可达性分析在许多应用场景中都非常重要。例如，在搜索引擎中，有向图可以用于表示网页之间的链接关系，并通过可达性分析来确定哪些网页是互相连接的，从而优化搜索算法。在项目管理中，有向图可以用于表示任务之间的依赖关系，并通过可达性分析来确定任务的执行顺序。总之，有向图作为一种重要的数据结构，具有广泛的应用价值和深远的研究意义。它不仅可以帮助我们更好地理解和描述现实世界中的各种关系，还可以为各种复杂问题的求解提供有力的工具和方法。

带权图和无权图

带权图是一种在数据分析和可视化中常用的工具，它通过对节点和边的权重进行量化表示，帮助我们更好地理解和呈现数据的复杂性和关联性。在实际应用中，带权图常被用于社交网络、交通网络、物流管理等领域。在社交网络中，带权图可以帮助我们分析用户之间的关系强度。例如，可以将每个用户视为一个节点，将用户之间的关系视为带权边，边的权重可以根据用户之间的互动频率、互动内容等因素进行量化。通过对带权图的分析，可以发现用户之间的社交圈子、影响力传播路径等信息，为社交网络的优化和推广提供有力支持。在交通网络中，带权图则可以帮助我们分析道路拥堵情况、交通流量等信息。可以将每个路口或路段视为一个节点，将路口之间的道路视为带权边，边的权重可以根据道路的交通流量、路况等因素进行量化。通过对带权图的分析，可以发现交通瓶颈、优化交通流线等，为城市交通规划和管理提供决策依据。除了以上应用外，带权图在物流管理中也具有重要作用。例如，在物流配送中，可以将每个物流节点视为一个节点，将节点之间的物流路径视为带权边，边的权重可以根据物流成本、运输时间等因素进行量化。通过对带权图的分析，可以优化物流路径、提高物流效率，为企业的物流管理提供有力支持。总之，带权图作为一种强大的数据可视化工具，能够帮助我们更好地理解和呈现数据的复杂性和关联性。在实际应用中，我们可以根据具体需求选择合适的带权图模型和分析方法，为各个领域的数据分析和决策提供有力支持。

无权图，也被称为非加权图，是图论中一个重要的概念，表示图中的边不具有权重的图。在无权图中，边仅仅表示两个顶点之间存在某种关系，而不涉及这种关系的强度或重要性。这种简化的表示方式使得无权图在许多领域都有着广泛的应用。无权图常常用于描述那些只关心节点之间是否存在连接，而不关心连接强度的问题。例如，在社交网络分析中，无权图可以用于表示用户之间的好友关系，其中边表示两个用户是好友，而不考虑他们之间的亲密程度或互动频率。此外，无权图还广泛应用于地图的简化表示、电路设计、生物信息学中的蛋白质相互作用网络等领域。无权图的另一个重要特点是其简洁性和易于分析性。由于没有权重的干扰，无权图的分析方法相对简单，许多经典的图论算法都可以直接应用于无权图。这些算法包括图的遍历算法（如深度优先搜索、广度优先搜索等）、图的连通性算法（如 Floyd 算法、Warshall 算法等）、以及图的匹配算法（如匈牙利算法、KM 算法等）。这些算法在无权图上的高效实现，为解决实际问题提供了有力的支持。总之，无权图作为一种特殊的图论模型，以其简洁性和易于分析性在各个领域得到了广泛的应用。随着图论研究的不断深入和应用场景的不断扩展，无权图将在更多领域发挥其重要作用。

图数据结构的存储方式

在信息技术的世界中，数据结构是构成软件系统的基础，其中图数据结构尤为重要。图数据结构由节点（或顶点）和边组成，用于表示实体间的关系。对于图数据结构的存储，主要有两种常见方式：邻接矩阵和邻接表。 邻接矩阵和邻接表

邻接表是一种用于表示图结构的数据结构，其中每个顶点都有一个与之相关联的链表，表示与该顶点相邻的顶点。邻接表是一种非常实用的数据结构，因为它可以高效地存储和访问图中的边和顶点。在邻接表中，每个顶点都通过一个链表来表示与之相邻的顶点，这使得添加、删除和查找边变得非常简单和快速。此外，邻接表还可以实现动态图结构，即在运行时可以轻松地添加和删除顶点和边。因此，邻接表在图论算法和许多实际应用中都有着广泛的应用，例如社交网络分析、最短路径算法和路径规划等。在实际应用中，邻接表的实现通常需要考虑一些细节问题，例如如何存储和访问链表、如何有效地处理内存和时间复杂度等。然而，通过合理的优化和设计，邻接表可以成为一种非常高效和实用的数据结构，为许多领域的研究和应用提供了强有力的支持。

不同类型的图对应的邻接矩阵

同质图的邻接矩阵是方阵，这是图论中一个重要的基本概念。同质图，也称为简单图，是一种无向图，其中没有环（即没有连接一个顶点到自身的边）也没有重边（即没有连接同一对顶点的两条或多条边）。邻接矩阵是一种用于表示图的矩阵形式，对于图中的每一个顶点，邻接矩阵中的对应行和列表示了该顶点与其他所有顶点的连接关系。如果两个顶点之间存在一条边，那么邻接矩阵中对应位置的值就是 1；如果两个顶点之间不存在边，那么对应位置的值就是 0。由于同质图是无向图，所以它的邻接矩阵是一个方阵，即行数和列数相等的矩阵。这是因为每一个顶点都只能与图中的其他顶点建立连接，所以邻接矩阵的每一行和每一列都对应图中的一个顶点。

不同于同质图，异质图的邻接关系一般不能通过矩阵来表示，但有一类特殊的异质图其邻接关系可以用矩阵来表示，它就是只有两种类型的节点，同类型节点之间没有边相连，我们把这种特殊的异质图叫做二分图。因为二分图有两种类型的节点，而且不要求两种类型的节点数相同，所以二分图的邻接矩阵形状是任意的。

无向图的邻接矩阵是对称矩阵，这一性质源于无向图的一个重要特性：无向图中的边没有方向性。也就是说，如果无向图中存在一条从节点 A 到节点 B 的边，那么从节点 B 到节点 A 的边也同样存在。邻接矩阵是一种用于表示图结构的矩阵形式。在邻接矩阵中，矩阵的行和列都对应图中的节点，而矩阵中的元素则表示节点之间的关系。对于无向图来说，如果节点 A 和节点 B 之间存在一条边，则邻接矩阵中 A 行 B 列和 B 行 A 列的元素都应为 1，表示这两个节点是相邻的。由于无向图中的边没有方向性，所以 A 到 B 的边和 B 到 A 的边是等价的，这就导致了邻接矩阵的对称性。换句话说，如果 A 和 B 是相邻的，那么 B 和 A 也一定是相邻的，因此在邻接矩阵中，A 行 B 列的元素和 B 行 A 列的元素必须相同。这种对称性使得我们在处理无向图的邻接矩阵时可以节省一些计算资源。例如，我们只需要计算矩阵的上三角或下三角部分，因为另一半可以通过对称性得到。同时，这种对称性也是无向图的一个重要特征，它反映了无向图中节点之间关系的平等性和无方向性。总的来说，无向图的邻接矩阵是对称矩阵，这一性质是由无向图本身的特性决定的。这一性质不仅简化了我们对无向图的处理，也帮助我们更深入地理解无向图的结构和特性。

不同于无向图，因为在有向图中，如果存在节点 A 指向节点 B 的边，那么不一定存在节点 B 指向节点 A 的边，所以有向图的邻接矩阵不一定是对称矩阵（不能理解成：有向图的邻接矩阵一定不是对称矩阵！）。

因为带权图的边是有权重的，那么其邻接矩阵不仅可以表示边是否存在，还要把边的权重进行表示，那么如果两个节点之间没有边，邻接矩阵的对应位置该写什么要具体问题具体分析，如果权重总是正数，并且我要找最小生成树和最短路径，对应位置应该写正无穷。

无权图的邻接矩阵就简单多了，用 1 表示两节点之间有边，0 表示两节点之间没边。

稀疏矩阵的邻接表存储

不失一般性，我们假设有这么一个图，第一，它是一个二分图；第二，它是一个有向图；第三，在其中只有从一种类别的节点指向另一种类别的节点的边（不能反过来）；第四，它是一个带权图，其中边的权重是任意非零实数（如果两节点之间无边相连，邻接矩阵的对应位置为 0，否则为对应权重）。举个例子，有一个满足上述条件的图如下图所示。

显然，该图的邻接矩阵为

显然，我们可以假设该图对应的邻接表如下图所示。

其中红框表示图中方框节点的信息，橙框是指针域（没有箭头出来表示空指针），绿框是圆节点的信息，蓝框是边的权重。

接下来我们就尝试把它往 LIL 格式的稀疏矩阵上面凑！首先把每一个链表按照绿框中的关键字升序排序，显然这里已经排好序了。我们完全可以直接跳到下一步，分离绿框和蓝框得到 2 个邻接表（顺序按照上面排好序的顺序来，不能随意地打乱顺序），如图所示。

到目前为止，显然可以发现距离 LIL 只差最后一步了，我们把这 2 个邻接表的格式改成其元素是动态数组的数组而不是其元素是链表的数组（顺序依旧不变），如图所示。

显然，我们可以轻而易举的看出蓝色粗分界线的上方就是 rows 属性，下方则是 data 属性。

至此，我们成功的通过图数据结构凑出了 LIL 格式的稀疏矩阵