图形:深度(加权、矩阵、SCC)

Содержание и основные понятия

返回目录
第24章 第24.1页
图形:深度(加权、矩阵、SCC)
重量矩阵,可实现的矩阵, 高度连接组件的塔里安算法。
第17章是方框的导言,这里是11年级的延长:加权图表、可实现的矩阵、塔里安算法和准备EEG第1号和奥林匹克运动会。
全环基金 11 ppm
PLF 进口。
第1号EGE E GE No.1
奥林匹克奥林匹克奥林匹克运动奥林匹克
01
重量矩阵
用于
加权图表
重量矩阵W是一个表格,其中W[i][j] = rib i~j的重量。如果肋骨不在场,则根据任务写下 ~ (持续) 或 0。
用于
未加权
该图是矩阵(0/1)的巨石。
计数
- 顶部之间的肋骨数。
实例:4个有加权的顶顶
A
B
C
D
A
0
5
∞
10
B
∞
0
3
∞
C
∞
∞
0
1
D
∞
∞
∞
0
肋骨表示缺乏肋骨。对角值=0(距离自我距离)。
0
1
2
3
4
图:环形方向图(DAG),5个顶点。
与EEEG的关系
EGR 3 以距离表或图表的形式给出图表。 您必须找到两个顶点之间的最短路径。 矩阵是设置图形的一种方法 。
02
交互式:建立一个加权矩阵
按 SVG 肋骨来添加/加载重量。 矩阵会自动更新 。
0
1
2
3
4
示例DAG:5个顶脊,肋0、1、0、2、3、3和4
🔧
矩阵设计器
点击 rib - 要求重量
03
可行性矩阵
可行性矩阵表D
:D[i][j] = 1,如果从i的顶部可以达到j(也许通过中间峰值)和0不同。
如何构建 :
让我们采取A相关的矩阵。
计算中途电路:D=A~A2A3...~A
n
在实践中,Warschel-Foldd算法
O(V³)
或每个顶点的 BFS
O(V·(V+E))
.
适用范围 :
要确定连接的峰值, 要检查图形的连接, 要找到连接的组件 。
A
B
C
D
例如,图表:A.B.,B.C.,
示例:4个顶点的方框
分节:AB、BC、CD、AD(直接)。
A
B
C
D
A
0
1
0
1
B
0
0
1
0
C
0
0
0
1
D
0
0
0
0
逐步建设D=A * A2 * A3 * A4 ( ⁇ 逻辑OR):
步骤1 - A1(直接路径):
A.B.、A.D.、B.C.、C.D.1. 各自单元格中的单位
A1显示:从A到B和D,从B到C,从C到D
步骤2 - A2(行距2):
A.B.C.,A.D.(否),B. C. 2.D., a.D.1...
A2:A ⁇ C(通过B)、B ⁇ D(通过C)
步骤3是D=A1A2的组合
构建 D : D[A][C] = 1 (通过 B), D[B][D]= 1(通过 C)
因为 A\C\D( 第 3 段): 另一个协会给 D[ A][ D]=1
结果:D[A][B]=1,D[ A][C]= 1,D [A][D]=1、2,D][B][C)=1、D[B][D] =1;D[C][D][]=11;D [C][d]=1.D[D][D)=1.(对等)
A
B
C
D
A
1
1
1
1
B
0
1
1
1
C
0
0
1
1
D
0
0
0
1
阅读:
A
可实现的B、C、D;
B
- C、D;发自
C
- D;D只是可以实现的。
Python:弗洛伊德-沃塞尔
def floyd_warshall(adj):
# adj — матрица смежности, adj[i][j]=1 если есть ребро i→j
n = len(adj)
d = [row[:] for row in adj] # копируем A¹
for k in range(n): # промежуточная вершина
for i in range(n):
for j in range(n):
d[i][j] = d[i][j] or (d[i][k] and d[k][j])
return d # матрица достижимости
# Пример:
adj = [
[0,1,0,1], # A → B, D
[0,0,1,0], # B → C
[0,0,0,1], # C → D
[0,0,0,0] # D → никуда
]
D = floyd_warshall(adj)
# D[0][2]=1: из A можно попасть в C
print("Достижимость из A:", [j for j in range(4) if D[0][j]])
O(V3) 是 V 的问题 ⁇ 300- 500。 对于大图, 使用每个顶点的 BFS : O( V) (V) ( V+E) 。
🔢
弗洛伊德-沃塞尔:一步一步
04
紧密连接的部件(SCC)
紧密连接的构成部分(SCC)
是脊椎动物的最大数组,其顶部有一条通往其他动物的通道(考虑到肋骨的方向)。
关键事实:
如果你把所有的SCC 挤到一个顶部, 你会得到
单环箱(DAG)
- 这叫
图表加插图
.
Taryan的算法
复杂性:O(V+E)。
想法是找到"角"SCC, 这些都是你无法进入 先前访问的组件。
示例:搜索SCC
图:A、B、C、A、D、E、D(周期)、C、F. 两个SCC:{A、 B、C}和{D、 E}。
A
B
C
D
E
F
Tarian 如何运作 :
每一顶上,都有所分配的,
数目数量数量数量
(进入时间)和
lowlink
(可达到的最低限度数字)。
上半部是 SSCC 根根, 如果
lowlink[v] = num[v]
.
当从外勤部返回时,排水管的顶部都形成一个SCC。
def tarjan_scc(n, adj):
num = [-1]*n; low = [0]*n; stack = []; on_stack = [False]*n
timer = [0]; result = []
def dfs(v):
num[v] = low[v] = timer[0]; timer[0] += 1
stack.append(v); on_stack[v] = True
for u in adj[v]:
if num[u] == -1:
dfs(u); low[v] = min(low[v], low[u])
elif on_stack[u]:
low[v] = min(low[v], num[u])
if low[v] == num[v]: # корень SCC
comp = []
while True:
w = stack.pop(); on_stack[w] = False
comp.append(w)
if w == v: break
result.append(comp)
for v in range(n):
if num[v] == -1: dfs(v)
return result # список SCC
🔗
Tarjana算法:SSC搜索
示例结果 :
[A,B,C]
,
[D,E]
,
[F]
浓缩:每个短链氯化石蜡压缩成一个顶部。
DAG 标记
.
你为什么要这么做?
依赖分析(图书馆、包件)
系统部署(电动)
在方向图形中搜索周期
EGE 第1期:《图表分析任务》
05
地形分类
地形顺序
- 脊椎动物序列,所有肋骨都从左向右。
DAG
(directed acyclic graph).
卡恩的算法
计数
in-degree
每一个脊椎。
将所有顶盘都与
in-degree = 0
.
重复: 从线顶上删除顶部, 添加结果, 降低邻居的度 。 如果室友的腿上是0, 将其加入线上 。
当线条为空时, 秩序会建立 。
复杂性:
O(V + E)
结果不是唯一一个—— 任何带有0度的脊椎, 可能是下一个。
你为何非得:
Macefile( 制造文件)
依赖规划
电子表格中公式的分辨率
课程时间表(先决条件)
示例:
"B"的意思是"B取决于A" 如果有一个周期 地形顺序是不可能的
from collections import deque
def topological_sort(n, adj):
in_deg = [0]*n
for v in range(n):
for u in adj[v]:
in_deg[u] += 1
q = deque([v for v in range(n) if in_deg[v]==0])
order = []
while q:
v = q.popleft()
order.append(v)
for u in adj[v]:
in_deg[u] -= 1
if in_deg[u]==0:
q.append(u)
return order # если len(order)!=n — есть цикл!
📋
Kahn: 一步一步的表层分类
06
公式目录
重量矩阵
W[i][j] = 肋排重量i~j
如果肋骨缺失,或0
可行性
D = A ∨ A² ∨ … ∨ Aⁿ
O(V3) - 战争 -- -- 付款
SCC (Taryan)
O(V+E)、外勤部+墙墙
DAG 冷凝
矩阵表大小
V x V( V 顶脊)
内存:O(V2)
07
图形绘画:时间表
绘画任务
- 设置顶部颜色( 时间) ,使相邻顶部的颜色不同。
色数
χ(G).
练习: 考试时间表。 每次考试都是顶级的, 肋骨, 学生通过两个科目。 您不能同时参加相互冲突的考试 。
📅
图表颜色:考试
向上方尖叫以选择颜色( 时间) , 冲突会发红 。
油漆应用
附表附表附表
- 考试、班级、定线
登记登记
- 登记册在汇编者中的分发
经常规划
- 无无线网络通道、信号塔
数独
- 每个数字 = 3x3区块的颜色
🎯
小型试验:5个问题
🧩
主题的快速测试
5个来自银行的随机问题 50个工作 每个20个XP