文章目录
有向图的拓扑序列关于拓扑序列的必要知识例题小结
朴素Dijkstra算法流程分析例题小结
总结
有向图的拓扑序列
关于拓扑序列的必要知识
定义：图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。拓扑序列存在的充要条件是图是一个有向无环图（DAG）DAG一定至少存在一个入度为0的点求拓扑序列的思路（BFS）：
记录入度为0的节点，将其插入队列 对于队列中的节点进行遍历，并弹出，遍历所有出边，对出边对应节点的入度相减 重复第一步
例题
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
输入格式 第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式 共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 −1。
数据范围 1≤n,m≤10^5 输入样例： 3 3 1 2 2 3 1 3 输出样例： 1 2 3
import collections
N = 100010
h = [-1] * N
e = [-1] * N
ne = [-1] * N
idx = 0
d = [0] * N #用于统计入度
res = []
def add(a, b) :
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
def topsort() :
que = collections.deque()
for i in range(1, n + 1) :
if not d[i] :
que.appendleft(i)
while len(que) != 0 :
t = que.pop()
res.append(t)
i = h[t]
while i != -1 :
j = e[i]
d[j] -= 1
if d[j] == 0 :
que.appendleft(j)
i = ne[i]
return len(res) == n
n, m = map(int, input().split())
for i in range(m) :
a, b = map(int, input().split())
add(a, b)
d[b] += 1
if topsort() :
for i in res :
print(i, end = " ")
print()
else :
print(-1)
小结
add(a, b)方法写错了捏，还debug好长时间捏，太丢人了捏，注意细节捏
朴素Dijkstra算法
用于权值为正的稠密图最短路算法，用邻接矩阵来存，矩阵的值是权值
流程分析
将起始点到起始点的距离设为0，其他节点到起始结点的距离设为无穷大遍历n - 1遍，为选取剩下n - 1个节点，每次选取一个到起始点最近节点的节点选取过程是，先判断是否被选过，再比较每个点到起始点的距离纳入节点后，通过纳入的节点更新其他点到起始点的距离，并且最后将纳入节点状态设为已纳入
例题
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式 第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式 输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围 1≤n≤500, 1≤m≤10^5, 图中涉及边长均不超过10000。
输入样例： 3 3 1 2 2 2 3 1 1 3 4 输出样例： 3
g = [[10010] * 510 for _ in range(510)]
dist = [10010] * 510
st = [False] * 510
n, m = map(int, input().split())
def dijkstra() :
dist[1] = 0
for i in range(n - 1) :
t = -1
for j in range(1, n + 1) :
if (not st[j]) and (t == -1 or dist[t] > dist[j]) :
t = j
for j in range(1, n + 1) :
if dist[j] > dist[t] + g[t][j]
dist[j] = dist[t] + g[t][j]
st[t] = True
if dist[n] >= 10010 :
return -1
else :
return dist[n]
for i in range(m) :
x, y, z = map(int, input().split())
g[x][y] = min(g[x][y], z)
print(dijkstra())
小结
图中可能存在重边和自环，重边建图时取最短变即可，自环即将g[i][i]设为无穷大即可。 注意节点状态要在最后更新
总结
今天浅学了这两个图论的基本算法，感觉对于基本的思路已经掌握。 碰到的问题
拓扑序列为何不会因为环的存在而无穷无尽： 因为只能是记录的入度为0的点才能进入队列，所以环中的节点根本不可能进入队列。dijkstra算法为何不在开始选起始点时更新起始点状态： 因为需要后面用起始点更新其他点到起始点的距离