十二、图与网络

  图是用以理解元组（tuple）最好的知识；
  元组就是数学模型；

12.1 有向图

图12.1 有向图例

Definition 12.1 A directed graph is a tuple $\mathrm{G}=(\mathbf{V},\mathbf{E})$, where $\mathbf{V}$ is the set of nodes,$\mathbf{E}\subseteq \mathbf{V}\times \mathbf{V}$ is the set of arcs.

• 节点集合 V = { v 1 , … , v n } \mathbf{V} = \{ v_{1}, \dots, v_{n} \} V={v1​,…,vn​}；
• 弧（有向边）的集合 $\mathbf{E}$ 本质上是 $\mathbf{V}$ 上的关系。因此，节点比边更本质；
• 弧记为 $⟨v_i,v_j⟩$，有角度的括号表示有向；
• 元组（tuple）可以把不同类型的数据融合到一起，对应与Java程序设计中的对象；

12.2 元组与对象

  图的Java代码如下：

public class Graph{
    /**
     * 节点数. 表示节点 v_0 至 v_{n-1}.
     */
    int n;
     
    /**
     * 相应弧是否存在. 1 表示是，0 表示否. 最多有 n*n 条弧.
     */
    int[][] arcs;
    
    /**
     * 构造一个包括 n 个节点的图，没有边.
     */
    public Graph(int paraN) {
        n = paraN;
        arcs = new int[n][n];
    }// Of the constructor

    /**
     * 设置边，paraValue = 1 表示添加, 0 表示删除.
     */
    public void setArc(int paraI, int paraJ, int paraValue) {
        arcs[paraI][paraJ] = paraValue;
    }// Of setArc
}// Of Graph

• 元组为对象的成员变量部分.
• 邻接矩阵表示：
  $$\mathbf{E}=\left[\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 0\\ 1& 0& 1& 0\end{array}\right]$$
  源码展示：\mathbf{E} = \left[ \begin{matrix} 0&1&1&0 \ 0&0&0&0 \ 0&1&0&0 \ 1&0&1&0 \end{matrix} \right]

12.3 二元关系与有向图

• 有向图的边集合可以看做一个关系.
• 课堂练习：
  • 根据二元关系的知识，计算${\mathbf{E}}^2=\mathbf{E}\circ \mathbf{E},{\mathbf{E}}^3={\mathbf{E}}^2\circ \mathbf{E}$ 与 ${\mathbf{E}}^0$，源码为\mathbf{E}^{2}=\mathbf{E} \circ \mathbf{E}, \mathbf{E}^{{3}=\mathbf{E}}{2} \circ \mathbf{E}：.
  • 根据矩阵知识，计算 ${\mathbf{E}}^2,{\mathbf{E}}^3,{\mathbf{E}}^0$.
  • 对照分析.
• 回到图上，分析可行性.
  • 不但表达了可达性，而且表达了路径数量.

12.4 无向图

图12.2 无向图例.

Defination 12.2 An undirected graph is a tuple $\mathrm{G}=(\mathbf{V},\mathbf{E})$, where $\mathbf{V}$ is the set of nodes, $\mathbf{E}\subseteq \mathbf{V}\times \mathbf{V}$ where $(v_i,v_j)\in \mathbf{E}\iff (v_j,v_i)\in \mathbf{E}$ is the set of edges.
源码为：( v_{i}, v_{j}) \in \mathbf{E} \Leftrightarrow ( v_{j}, v_{i}) \in \mathbf{E}

• 无向边用小括号，$(v_i,v_j)$.
• 问题：有向图和无向图，哪个更特殊？
    在无向图中，边没有方向，常用于表达节点之间无特殊方向性关系的场景，如地图上城市与城市的连接。在有向图中，边是有方向的，常用于表达具有明确方向性关系的场景，如食物链中的捕食关系。因此，我认为有向图更特殊一些，它引入了方向性这一特点，使有向图在表达复杂关系时更具体。
• 练习：写出该无向图的邻接矩阵.
    邻接矩阵表示如下：
  $$\mathbf{E}=\left[\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 0\\ 1& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right]$$

12.5 有向网络

  有向网络的Java代码如下：

public class Net{
    /**
     * 节点数. 表示节点 v_0 至 v_{n-1}.
     */
    int n;
     
    /**
     * 权重.
     */
    double[][] weights;
    
    /**
     * 构造一个包括 n 个节点的网，权值均为0.
     */
    public Net(int paraN) {
        n = paraN;
        weights = new double[n][n];
    }// Of the constructor

    /**
     * 设置边权重.
     */
    public void setWeight(int paraI, int paraJ, double paraWeight) {
        weights[paraI][paraJ] = paraWeight;
    }// Of setWeight
}// Of Net

• 思考：关系只能表示是否有边（弧），如何表示权重？

Definition 12.3 A directed net is a tuple $\mathrm{G}=(\mathbf{V},\mathbf{w})$, where $\mathbf{V}$ is the set of nodes, and $\mathbf{w}$: $\mathbf{V}\times \mathbf{V}\to \mathbb{R}$ is the weight function where $\mathbf{w}(v_i,v_j)$ is the weight of the arc $⟨v_i,v_j⟩$.

• 注意：也可以写作$\mathbf{w}(⟨v_i,v_j⟩)$. 同理，函数$z=f(x,y)$ 也可以写作 $z=f(⟨x,y⟩)$ 或 $z=f((x,y))$ ，但是最后一个表达式实在是太啰嗦了.

12.6 作业

• 定义无向网络.
• Definition 12.4 An unfirected net is the tuple $\mathbf{G}=(\mathbf{V},\mathbf{w})$, where $\mathbf{V}$ is the set of nodes, and $\mathbf{w}:\mathbf{V}\times \mathbf{V}\to \mathbb{R}$ is the weight function where $\mathbf{w}(v_i,v_j)$ is the weight of the edges $(v_i,v_j)$, satisfying $v_i,v_j\in \mathbf{V}$（且 i ≠ j）, $\mathbf{w}(v_i,v_j)=\mathbf{w}(v_j,v_i)$ .

十三、树

• 树反映了一种层级关系：一个学校有若干学院、一个学院有若干专业、一个专业有若干老师.

13.1 例子

图13.1 树

  观察可知：

• 树是一种特殊的图；
• 有一个树根；
• 除了树根之外，其它节点均有父节点；
• 没有子节点的节点称为叶节点；
• 从任意节点到树根都只有一条唯一的路径；

  思考：树的边有向还是无向？
  我认为没有特殊情况说明时，树指的是无向树。

13.2 定义

  Let $\varphi$ be the empty node, a tree is a triple $\mathrm{T}=(\mathbf{V},\text{ r, p})$ where：

• $\mathbf{V}\ne \varphi$ is the set of node;
• $\text{r}\in \mathbf{V}$ is the root node;
• p : V ∪ { ϕ } → V ∪ { ϕ } \textrm{p} : \mathbf{V} \cup \{ \phi \} \rightarrow \mathbf{V} \cup \{ \phi \} p:V∪{ϕ}→V∪{ϕ} is the parent mapping satisfying
  • $\text{p}(r)=\varphi$;
  • $\forall v\in \mathbf{V},\exists !n\ge 0,st.p^{(n)}(v)=r$

  源码为：\forall v \in \mathbf{V}, \exist ! n \ge 0,st. p^{(n)}(v) = r
  分析：

• $\varphi$ 可以看作是常量，对任意树都有效，因此可以不出现在元组里面；
• 不同元组可以有不同特性，甚至这里的元组 $\text{r}$ 是 $\mathbf{V}$ 的元素；
• $p^{(2)}(v)=p(p(v))$ . 可以理解为： $v$ 的2阶父节点；
• 最后一行读作：对于任意的节点 $v$ ，存在唯一的自然数 $n$，使得（满足）$v$ 的第 $n$ 阶父节点为 $r$；
• 唯一性表示既可达又没有环；
• $p^{(0)}(v)\equiv v$，因此该条件考虑了 $r$ 到 $r$；
• $n$ 可以看做是节点所在的层，$n=0$ 时只有根节点；

13.3 Java代码

public class Tree {
    /**
     * 节点数. 表示节点 v_0 z至 v_{n-1}.
     */
     int n;

    /**
     * 根节点. 0 至 n-1.
     */
     int root;
     
    /**
     * 父节点.
     */
     int[] parent;

    /**
     * 构造一棵树，第一个节点为根节点，其余节点均为其直接子节点，也均为叶节点.
     */
     public Tree(int paraN) {
         n = paraN;
         parent = new int[n];
         parent[0] = -1; // -1 即 \phi
     }// Of the constructor
}// Of class Tree

  分析：

• 代码与定义的统一：3 -元组与 3 个成员变量. 写完程序又回去整理定义；
• parent 函数可以用一维数组表示；
• -1 表示 $\varphi$；
• 程序里面，数据本身没有保障可达性、唯一性，这和无向图的情况一致（连接矩阵对称）；

13.4 作业

• 自己画一棵树，将其元组各部分写出来（特别是函数 $p$）；
  

  Let $\varphi$ be the empty node, a tree is a triple $\mathrm{T}=(\mathbf{V},\text{ r, p})$ where：

• V = { v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 , v 8 , v 9 } \mathbf{V} = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8,v_9\} V={v1​,v2​,v3​,v4​,v5​,v6​,v7​,v8​,v9​} is the set of node;

• $\text{r}=v_1$ is the root node;

• p : V ∪ { ϕ } → V ∪ { ϕ } \textrm{p} : \mathbf{V} \cup \{ \phi \} \rightarrow \mathbf{V} \cup \{ \phi \} p:V∪{ϕ}→V∪{ϕ} is the parent mapping satisfying

  • $\text{p}(v_1)=\varphi$;
  • ${\text{p}}^{(0)}(v1)=r,{\text{p}}^{(1)}(v_1)=r,{\text{p}}^{(1)}(v_2)=r,{\text{p}}^{(2)}(v_3)=r,{\text{p}}^{(2)}(v_4)=r,{\text{p}}^{(2)}(v_5)=r,{\text{p}}^{(3)}(v_6)=r,{\text{p}}^{(3)}(v_7)=r,{\text{p}}^{(3)}(v_8)=r$
  • $\text{p}=\varphi ,\text{p}(v_2)=v_1,\text{p}(v_3)=v_1,\text{p}(v_4)=v_2,\text{p}(v_5)=v_2,\text{p}(v_6)=v_3,\text{p}(v_7)=v_5,\text{p}(v_8)=v_6,\text{p}(v_9)=v_6$

• 针对该树，将代码中的变量值写出来（特别是 parent 数组）；

  • n = 9；
  • parent[] = [-1,0,1,1,2,2,3,5,6,6]；
  • -1表示根节点无父节点；
  • parent[4] = 2：因为节点4的父节点是2。

十四、$\mathbf{m}$叉树

  我们来定义 $\mathbf{m}$ 叉树，并将二叉树作为其特例来分析.

14.1 预备知识：字符串

• 字母表记作 $\Sigma$，源码为：\Sigma；
• 英文字母表 Σ = { a , b , … , z } \Sigma = \{ \mathrm{a},\mathrm{b},\dots,\mathrm{z} \} Σ={a,b,…,z}，我们故意写成 \mathrm{a} 以表示它为常量；
• 阿拉伯数字字母表 Σ = { 0 , 1 , … , 9 } \Sigma=\{0,1,\dots,9\} Σ={0,1,…,9}；
• 二进制数字字母表 Σ = { 0 , 1 } \Sigma=\{0,1\} Σ={0,1}；
• 字母表的乘积 { 0 , 1 } × { 0 , 1 } = { { 0 , 0 } , { 0 , 1 } , { 1 , 0 } , { 1 , 1 } } = { 00 , 01 , 10 , 11 } \{0,1\} \times \{0,1\} = \{\{0,0\},\{0,1\},\{1,0\},\{1,1\}\}=\{00,01,10,11\} {0,1}×{0,1}={{0,0},{0,1},{1,0},{1,1}}={00,01,10,11}，我们通常使用简记；
• 字母表的正闭包： ∑ + = { 0 , 1 } + \sum^{+}=\{0,1\}^{+} ∑+={0,1}+表示长度至少为1的字符串（0,1串）；
• 字母表的克林闭包： ∑ ∗ = ∑ + ∪ { ε } \sum^{*}=\sum^{+} \cup \{ \varepsilon \} ∑∗=∑+∪{ε}，其中表示空串，源码为\varepsilon；

14.2 $\mathbf{m}$-叉树的定义

  Let $\varphi$ be the empty node, an $\mathbf{m}$-tree is a quadruple $\mathrm{MT}=(\mathbf{V},r,\Sigma ,c)$ where:

• $\mathbf{V}$ is the set of nodes;
• $r\in \mathbf{V}$ is the root node;
• $\Sigma$ is the alphabet;
• c : ( V ∪ { ∅ } ) × Σ ∗ → V ∪ { ϕ } c:(\mathbf{V} \cup\{\emptyset\}) \times \Sigma^{*} \rightarrow \mathbf{V} \cup \{ \phi \} c:(V∪{∅})×Σ∗→V∪{ϕ} satisfying（源码为：c:(\mathbf{V} \cup{\emptyset}) \times \Sigma^{*} \rightarrow \mathbf{V} \cup { \emptyset }）
  • $\forall v\in \mathbf{V},c(v,\epsilon )=v$，源码为：\forall v \in \mathbf{V},c(v,\varepsilon)=v;
  • $\forall v\in \mathbf{V},s={\mathrm{a}}_1{\mathrm{a}}_2\dots {\mathrm{a}}_n,c(v,s)=((v,{\mathrm{a}}_1),{\mathrm{a}}_2{\mathrm{a}}_3\dots {\mathrm{a}}_n)$;
  • $\forall v\in \mathbf{V},\exists !s\in {\Sigma }^{\ast }st.c(r,s)=v$.

  说明：

• 一般只给定 c : V × Σ → V ∪ { ϕ } c:\mathbf{V} \times \Sigma \rightarrow \mathbf{V} \cup \{\phi\} c:V×Σ→V∪{ϕ} 即可推导出： c : V × Σ ∗ → V ∪ { ϕ } c:\mathbf{V} \times \Sigma^{*} \rightarrow \mathbf{V} \cup \{\phi\} c:V×Σ∗→V∪{ϕ}. 前者简洁，后者完备.
• 从有限状态自动机的角度，$c$ 被称为状态转换函数，即从一个状态读入一个字符，转换下一个状态.
• 令 Σ = { l , r } \Sigma = \{\textrm{l} , \textrm{r} \} Σ={l,r}，即获得我们熟悉的二叉树，源码为：\Sigma = {\textrm{l} , \textrm{r} }.
• 叶节点读入任何串，都转移到空状态.
• 空状态读入任何串，都转移到自己.
  

图14.1 二叉树

图14.2 带空节点的二叉树

14.3 Java代码

public class MTree {
    /**
     * 节点数. 表示节点 v_0 至 v_{n-1}.
     */
    int n;

    /**
     * 根节点. 0 至 n-1.
     */
     int root;
 
    /**
     * 字母表大小. 字母表为 {1,2,...,m}.
     */
     int m;
     
    /**
     * 子节点. child[i][j] 表示在节点 i 读入字母 j 后转移到的状态.
     */
    int[][] child;

    /**
     * 初始化一颗 m-树，但现在它还无法表示一颗真正的 m-树.
     */
    public MTree(int paraN, int paraM) {
        n = paraN;
        child = new int[n][m];
    }// Of the constructor

    /**
     * 从当前节点读入一系列字符（其实是整数）,转到相应的节点.
     */
    public int getChild(int paraNode, int[] paraString){
        int resultNode = paraNode;
        for (int i = 0; i < paraString.length; i++){
            resultNode = child[resultNode][paraString[i]];
            if (resultNode == -1) {
                break;
            }// Of if
        }// Of for i
        return resultNode;
    }// Of getChild
}// Of class MTree

说明：

• 为了广泛适用性，字母表并未写成 { l,r } \{\textrm{l,r}\} {l,r} 的形式，而是直接定义了字母表大小. 这样，可以认为字母表为 { 1 , … , m } \{1,\dots,\textrm{m}\} {1,…,m} ，二叉树的字母表则为 { 1 , 2 } \{1,2\} {1,2} .
• 二维数组 child 确定了 $\mathbf{m}$-叉树的结构.
• 需要根据数据初始化 $\mathbf{m}$-叉树.
• 一般使用 -1 表示$\varphi$.
• 课堂练习：写出图 1 二叉树所对应的 child 数组.
  • $$child[4][2]=\left[\begin{array}{cc}1& -1\\ 2& 3\\ -1& -1\\ -1& -1\end{array}\right]$$

14.4 作业

• 画一颗三叉树，并写出它的 child 数组；
• 以13章作业的图为例：
  
  • $$child[9][3]=\left[\begin{array}{ccc}2& -1& 3\\ 4& -1& 5\\ -1& -1& 6\\ -1& -1& -1\\ 7& -1& -1\\ 8& -1& 9\\ -1& -1& -1\\ -1& -1& -1\\ -1& -1& -1\end{array}\right]$$
• 按照本帖风格，重新定义树. 提示：还是应该定义 parent 函数，字母表里面只有一个元素.
  • Let $\varphi$ be the empty node, a tree is a quadruple $\mathrm{T}=(\mathbf{V},r,\Sigma ,\text{p})$ where:
  • $\mathbf{V}$ is the set of nodes;
  • $r\in \mathbf{V}$ is the root node;
  • $\Sigma$ is the alphabet, Σ = { 1 } \Sigma = \{1\} Σ={1};
  • p : V × Σ ∗ → V ∪ { ϕ } \textrm{p}:\mathbf{V} \times \Sigma^{*} \rightarrow \mathbf{V} \cup \{ \phi \} p:V×Σ∗→V∪{ϕ} is the parent mapping, satisfying $\forall v\in \mathbf{V},\exists !s\in {\Sigma }^{\ast }st.\text{p}(v,s)=r$.
• 根据图、树、$\mathbf{m}$-叉树的学习，谈谈你对元组的理解；
  • 元组是一个有序的元素集合，每个元素都有固定的位置（索引）。被创建后，元组内的内容不能被修改。它是理解和实现复杂数据结构的重要工具，如：树、$\mathbf{m}-$叉树等。元组简化了数据结构的表示，提高了数据的客房问下和可维护性。