跳转至

7. 并查集和图

阅读信息

约 1010 个字  4 分钟  本页总访问量：加载中... 次

:cloud_with_lightning_and_rain:Class Seven

考试题型

选择题,函数填空,函数编程题(1 题)

等价类问题

给定集合,给定谁和谁等价,根据此等价划分集合. e.g.谁和谁是一组,图中最小生成树(城市之间连通道路的最小长度) 最小生成树的一种方法:

将所有边从小到大排序,一个一个放入生成的图检验. 当放入边后形成回路时,该边不正确. 核心是给定一条边,判定这条边的两个点分别属于什么集合.如果在同一组,放入;在不同组,不放入. 用find函数实现,同一组的点用union连接.

  • 用树表示:这样的树不需要找儿子,只需要找父亲.因此所有节点都只有一个指针指向父亲.
  • 用数组表示:索引代表当前节点,数值代表上一个父亲.如果s[i]==0,表示是根. 集合的并:s[rt1]=rt2.

找到 parent 的代码:

Text Only
1
2
3
4
  while (s[i]>0) {
    i=s[i];
  }
  return i;
  • 合并方法:union by height,union by size(可推导树的高度不超过\(log_2 N\)),每次调整较小的树
  • 怎么判断树的大小?之前树根用 0 表示,可以用负数表示树根,数值的绝对值表示树的大小.s[root]=-size.
  • 路径压缩:找到树根时,这一条路上所有节点都经过.将这条路上的节点都直接指向树根.
Text Only
1
2
3
4
5
6
数值 find(位置x,数组s) {
  if (s[x]<=0)               // 是树根
    return
  else
    return s[x]=find(s[x],s) // 找x上一个父亲的根,并用根更新s[x]
}

或使用两层循环:

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
数值 find(位置x,数组s) {
  for (root=x;s[root]>0;root=s[root]); // 不断更新root,先找到根

  for (trail=x;trail!=root;trail=lead) {
    lead=s[trail]; // 用于保存路径上的值
    s[trail]=root; // 将路径上的值更新为根
  }

  return root;
}

使用该方法时近似常量.

图

人工智能原理

用简答的模型实现复杂的映射.其中的变量是权重. 设计评估函数判断设计的模型和训练数据之间的差距,成为误差函数\(L(w_i)\).该函数是权重\(w_i\)的函数.不断调整权重使该函数的值最小. 相当于求函数的极小值.向导数为零的方向调整.利用的方法为梯度递降法. 神经网络的本质是图.大模型训练的本质是将能量转化为结构.

图的描述

  • G(V,E)分别表示点,边
  • 一般考虑:没有自环,没有重边
  • 完全图:所有能连的边都连接.无向图边的条数为\(C_n^2\).
  • 子图:点和边都是子集
  • 路径:点的序列,任何前后两点之间都有边连接
  • 路径长度:路径上有多少条边
  • 简单路径:路径上的点没有重叠
  • 环:简单路径,且头尾连接
  • 连通图:无向图:任何两个点都是连通的;有向图:任何两个点之间都有路径能走到.
  • 连通子图(component):最大的连通的子图
  • 树:连通的,没有回路的图
  • DAG(directed acyclic graph):有向无环图,节点前后有依赖关系
  • 强连通图(strong connected directed graph):任何两个点之间都有路径连接的有向图
  • 弱连通图(weakly connected directed graph):任何两个点之间都有路径连接的无向图
  • 强连通分量(strongly connected component)
  • 度(degree):每个点有几个点和它连通
  • 入度(in-degree):有向图中,对于一个点,有多少其他点指向它
  • 出度(out-degree):有向图中,对于一个点,它指向几个其他点

图的表示(有向图)

邻接表:把所有该点出去的边都用链表串在一起 逆邻接表:将指向该点的点串在一起. 邻接表和逆邻接表完整地表示整个图

十字链表(只用于有向图):用节点表示边,每个节点有 4 个分量,分别为 2 个数据和 2 个指针.用数组表示所有节点.数组中 vi 指向 vi 开头的节点. 前面的指针表示第一个数据指向谁,第二个指针表示什么数据指向第二个数据.

多重链表 multilist(只用于无向图):数组出发的每个点将含有该点的节点串在一起.

图的作用

  1. 社群挖掘:将不同人之间的联系表示成图.根据每条边的权重划分社群.
  2. 一种判断社群是否紧密的方法:里面的边和外面直接相连的边的比值
  3. 可以根据点的入度,出度的权重判断点的性质