subgraph[subgraph函数]

最近有一位之前找过币牛牛的用户问了我们小编的一个问题，我相信这也是很多币圈朋友经常会疑惑的问题：subgraph相关问题，subgraph函数相关问题，带着这一个问题，让专业的小编告诉您原因。

图G的一个支撑子图(spanning

subgraph)是一个含有G的所有节点的子图。如果图G的支撑子图是一棵树，则称为G的支撑树(spanning

Tree)，或者称为生成树。我们通常说的最小生成树(minimal

spanning

tree)就是指图G的所有支撑树中边权之和最小的支撑树。

remarks: 从bear导入的，不可见图为草稿，重点部分都有写。

连通图(connected graph)：如果从任意一个顶点都存在一条路径到达另一个任意顶点（undirected graph）

树：是一幅无环无向连通图

森林：1个or几个树

简单路径(simple path)：一条没有重复顶点的路径

简单环(simple cycle)：一条（除了起点和终点必须相同之外）不含有重复顶点和边的环

adjacent: when 2 v are connected by a single edge

biconnectivity/ biconnected graph: 移除一条边也不会使graph成为unconnected的graph

subgraph(of graph G)：只取G中的几个顶点构成的图

spanning subgraph：取G中所有顶点构成的图

spanning tree：是G的subgraph+是tree=由G中所有顶点构成的无环无向连通图（spanning tree不唯一）

directed edge: 有箭头的边，eg. flight(从A点到B点)

undirected edge: 无箭头的边，eg. flight route(A和B的距离)

directed graph

undirected graph

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WUgPCDy8-1605523062295)(Graph/24905163-e121bc7bba6f78d1.png)]

space: O(V^2)

add edge: O(1)

check if adjacent: O(1)

iteration: O(V)

eg: [ [0,1], [0, 2], [0, 5], [1, 2], [2, 3], [2, 4], [3, 4], [3, 5] ]

Edge里含两个int变量

space: O(E)

add edge: O(1)

check if adjacent: O(E)

iteration: O(E)

0: 6—5—2—1

1: 3—0

2: 0

3: 5—1

4: 6—5

5: 4—3—0

6: 7—4—0

7: 8—6

8: 10—7

9: 11—10

10: 12—9—8

11: 9

12: 10

a) 使用的空间和V+E成正比

b) 添加一条边所需的时间为常数

c) 遍历顶点v的所有相邻顶点所需的时间和v的度数成正比

d) 每条边会出现两次

space: O(V+E)

add edge: O(1)

check adjacent: deg(v) – vertex v

iteration: deg(v)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4Z4nziuk-1605523062297)(Graph/Photo%20Nov%2013,%202020%20at%20105929%20PM.jpg)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yShOuTgS-1605523062298)(Graph/bear_sketch@2x.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OFy3SB4e-1605523062299)(Graph/bear_sketch@2x.png)]

O(V+E)

dfs遍历整个图的顺序和最短路径无关，而bfs搜索的是最短路径

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rfnh5z5r-1605523062302)(Graph/20190329164255150.png)]

共三个

可利用 深度优先 来找出图中所有的连通分量

*深度优先搜索的预处理使用的时间和空间与V+E成正比且可以在常数时间内处理关于图的连通性查询。

有向图：由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点

indegree（入度）：point to

outdegree（出度）：point away

simple：没有重复的E / V

simple digraph的定律：E = V(V-1)

strongly connected: every V is reachable from every other V

判断strongly connectivity的时间复杂度：O(V+E)

在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比

用途：解决优先级限制下的调度问题

有向无环图（DAG）：不含有向环的有向图

顶点的强连通：如果两个顶点v和w是互相可达的，那么它们是强连通的

图的强连通：如果一幅有向图中的任意两个顶点都是强连通的，则称这幅有向图也是强连通的

三个for loop

space: O(V^2)

runtime: O(V^3)

必须是DAG – directed graph that has no cycle

见笔记

O(V+E)

适用于 加权有向图

重点解决“找到从一个顶点到达另一个顶点的权重最小的 有向路径 ”

（只写了要注意的）

放松边v – w意味着检查从s到w的最短路径是否是先从s – v – w的，如果是，那么更新数据结构的内容

采用了类似Prim的类似方法来计算最短路径树

Dijkstra可以解决边 权重非负 的加权 有向图 的 单起点 最短路径问题。

也可以在加权无向图中找到最短路径

graph需要时connected的

使用Dijkstra计算根结点为给定起点的最短路径树所需的空间与V成正比，时间与ElogV成正比 – O(ElogV)

用处：

当且仅当加权有向图中至少 存在一条从s到v的有向路径 且所有从s到v的有向路径上的任意顶点都 不存在于任何负权重环中 时，s到v的最短路径才是存在的

Bellman-Ford算法所需的时间和EV成正比，空间和V成正比

一幅加权图的最小生成树（MST）是它的一棵权值（树中所有边的权值之和）最小的生成树

最小生成树仅存在于加权无向图

每幅连通图都只有一棵唯一的最小生成树（所有边权重不同）

无cycle=a tree+weight minimize

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AgJkoBgj-1605523062304)(Graph/Photo%20Nov%2013,%202020%20at%20102515%20PM.jpg)]

只有一个顶点，会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权值最小的边加入树中

最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili 4:00

把所有边和weight按大小 排序 ，但保证不能有cycle

最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili 2:09

所需的空间和E成正比，所需的时间和 ElogE 成正比

分块然后选最短的路径连接

O(ElogV)

对于每一种切分，权重最小的横切边必然属于最小生成树。

Remarks：Prim和Kruskal不能处理有向图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iYd98l3e-1605523062305)(Graph/Photo%20Nov%2013,%202020%20at%20102448%20PM.jpg)]

图的邻接矩阵的实现

无向图1——图的邻接表数组表示以及DFS、BFS搜索算法实现_大魔王-CSDN博客

【数据结构】图的连通分量 HaYa-CSDN博客 数据结构 连通分量

连通图和连通分量 weixin_30569153的博客-CSDN博客 连通分量

应该是“支撑子图”的意思，也就是子图包含了所有顶点。

不过一般来讲应该说成“spanning subgraph”，或者说“subgraph spanned on vertices…”。

无向图G连通并且无环则是树。

没说连通无向，错。

去掉对连通性的要求，就是森林。每个分支都是树的无向图是森林。

部署了子图后，访问 Graph Explorer 以打开 GraphiQL 接口，您可以在其中通过发出查询和查看模式来探索为子图部署的GraphQL API。

下面提供了一个示例，但是请参阅 Query API ，以获取上述文章内容就是如何查询子图的实体的完整参考。

例

该查询列出了我们的映射已创建的所有计数器。由于我们只创建一个，因此结果将只包含一个

default-counter：

{counters{idvalue}}

使用图形浏览器

Graph Explorer及其GraphQL游乐场是探索和查询托管服务上已部署子图的有用方法。

以下是一些主要功能：

阶（Order）：图G中顶集V的大小称作图G的阶。

子图（Sub-Graph）：当图G’=(V’,E’)其中V‘包含于V，E’包含于E，则G’称作图G=(V,E)的子图。每个图都是本身的子图。

生成子图（Spanning Sub-Graph）：指满足条件V(G’) = V(G)的G的子图G。

导出子图（Induced Subgraph）：以图G的顶点集V的非空子集V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图；以图G的边集E的非空子集E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。

度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。

入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。

自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。

路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,…ek,vk，其中ei的顶点为vi及vi – 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。

行迹（Trace）：如果路径P(u,v)中的边各不相同，则该路径称为u到v的一条行迹。

轨道（Track）：如果路径P(u,v)中的顶点各不相同，则该路径称为u到v的一条轨道。

闭的行迹称作回路（Circuit），闭的轨称作圈（Cycle）。

（另一种定义是：walk对应上述的path，path对应上述的track。Trail对应trace。）

桥（Bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。

都看完了嘛？相信现在您对subgraph有一个初级的认识了吧！也可以收藏币牛牛页面获取更多subgraph函数知识哟！区块链、虚拟币，我们是认真的！