图：基础概念

1. 图的定义

图是一种用于建模对象之间关系的基本数据结构。本节介绍图的关键术语和性质。

1.1 基本图的表示

• 图的表示：图 \( G(V, E) \) 由以下部分组成：
  • \( V(G) \)：有限非空的顶点集。
  • \( E(G) \)：有限的边集，表示顶点之间的连接。
• 图的类型：
  • 无向图：边没有方向，因此 \( (v_i, v_j) = (v_j, v_i) \)，表示边是双向的。
  • 有向图（Digraph）：边有方向，记为 \( \langle v_i, v_j \rangle \)，其中 \( v_i \) 为尾，\( v_j \) 为头。
• 限制条件：
  • 不允许自环（顶点到自身的边）。
  • 不考虑多重图（同一对顶点间有多条边的情况）。

1.2 完全图

• 定义：完全图是给定顶点数下具有最大可能边数的图。

• 完全图的边数计算：

  • 对于具有 \( n \) 个顶点的无向图，边数为：

    \[ E = C_n^2 = \frac{n(n-1)}{2} \]

  • 对于具有 \( n \) 个顶点的有向图，边数为：

    \[ E = P_n^2 = n(n-1) \]

1.3 邻接与关联

• 无向图：
  • 如果存在边 \( (v_i, v_j) \)，则顶点 \( v_i \) 和 \( v_j \) 是邻接的。
  • 边 \( (v_i, v_j) \) 关联于顶点 \( v_i \) 和 \( v_j \)。
• 有向图：
  • 如果存在边 \( \langle v_i, v_j \rangle \)，则称顶点 \( v_i \) 邻接到 \( v_j \)，顶点 \( v_j \) 是从 \( v_i \) 邻接而来的。
  • 边 \( \langle v_i, v_j \rangle \) 关联于 \( v_i \) 和 \( v_j \)。

1.4 子图（subgraph）

• 定义：图 \( G' \) 是图 \( G \) 的子图，满足：

  • \( V(G') \subseteq V(G) \)：\( G' \) 的顶点是 \( G \) 顶点的子集。
  • \( E(G') \subseteq E(G) \)：\( G' \) 的边是 \( G \) 边的子集。

• 生成子图：如果上述两个图的顶点数（\(V\)）相等，那么\(G_0\)称为\(G\)的生成子图。

1.5 路径与环

• 路径：顶点序列 \( \{v_p, v_{i1}, v_{i2}, \ldots, v_{in}, v_q\} \)，其中连续顶点通过 \( E(G) \) 中的边连接。
  • 无向图：\( (v_p, v_{i1}), (v_{i1}, v_{i2}), \ldots, (v_{in}, v_q) \)。
  • 有向图：\( \langle v_p, v_{i1} \rangle, \langle v_{i1}, v_{i2} \rangle, \ldots, \langle v_{in}, v_q \rangle \)。
• 路径长度：路径中的边数。
• 简单路径：所有中间顶点 \( v_{i1}, v_{i2}, \ldots, v_{in} \) 均不同，即：从顶点\(v_i\)到\(v_j\)的路径，顶点不能重复出现（distinct）。
• 环（回路）：起点和终点相同的简单路径（即 \( v_p = v_q \)）。

1.6 连通性

1. 无向图：

• 顶点的连通：如果存在从 \( v_i \) 到 \( v_j \) 的路径（因边是双向的，反之亦然），则顶点 \( v_i \) 和 \( v_j \) 是连通的。
• 连通图：如果每对不同顶点都连通，则图是连通图。
• 连通分量(component of an undirected G)：无向图\(G\)中最大的连通子图（相当于把图分成几个部分，取其中最大的连通图）。

2. 有向图：

• 顶点的强连通：如果对于每对顶点 \( v_i \) 和 \( v_j \)，存在从 \( v_i \) 到 \( v_j \) 和从 \( v_j \) 到 \( v_i \) 的有向路径，则图是强连通的，我们称这个图为强连通图。
• 顶点的弱连通：如果忽略边方向后图是连通的，则图是弱连通的，我们称这个图为弱连通图
• 强连通分量(strongly connected component)：最大的强连通子图。

这里你也可以看出来，强/弱连通是基于有向图讨论的。

1.7 树与有向无环图

• 树：连通且无环的无向图。
• 有向无环图（DAG）：没有环的有向图。

1.8 度数

• 无向图：顶点 \( v \) 的度数，记为 \( \text{degree}(v) \)，是关联于 \( v \) 的边数。
• 有向图：
  • 入度(in-degree)：指向顶点 \( v \) 的边数。
  • 出度(out-degree)：从顶点 \( v \) 发出的边数。
  • 度数：入度和出度之和，例如，若 \( \text{in-degree}(v) = 3 \)，\( \text{out-degree}(v) = 1 \)，则 \( \text{degree}(v) = 4 \)。

• 握手定理：对于具有 \( n \) 个顶点和 \( e \) 条边的图，顶点度数之和等于边数的两倍：

  \[ e = \frac{\sum_{i=0}^{n-1} \text{degree}(v_i)}{2} \]

1.9 图的表示

图可以通过多种数据结构在内存中表示，每种方式在空间和时间复杂度上各有优劣。

1.9.1 邻接矩阵

• 定义：对于具有 \( n \) 个顶点的图，邻接矩阵是一个 \( n \times n \) 矩阵 \( \text{adj_mat} \)，其中：

  \[ \text{adj_mat}[i][j] = \begin{cases} 1 & \text{如果 } (v_i, v_j) \in E(G) \text{ 或 } \langle v_i, v_j \rangle \in E(G), \\ 0 & \text{否则}. \end{cases} \]

• 性质：

  • 空间复杂度：\( O(n^2) \)。
  • 检查边存在性的时间复杂度：\( O(1) \)。
  • 遍历邻接顶点的时间复杂度：\( O(n) \)。

• 无向图中：

  • 性质1：对角线上全为0，且邻接矩阵关于矩阵对角线对称(symmetric)。

  这代表着储存无向图的数据可以只存储一半左右（做成一个三角形），节省了空间。

  • 性质2：\(v_i\)构成端点所连接的边的数目可以从第\(i\)列或第\(i\)行读出，即有多少个1，就连接了多少条边。
  • 性质3：\(v_i\)构成端点的邻接点可以从第\(i\)列或第\(i\)行读出，即读出结果为1的列，就为对应的邻接点下标。

• 有向图中：

  • 性质1：对角线上全为0，但不一定对称。
  • 性质2：“竖入横出“，即寻找顶点\(v_i\)的入度，可以将其所对应的列（列是竖着排放数据的）的各项求和；寻找顶点\(v_i\)的出度，可以将其所对应的行（行是横着排放数据的）的各项求和。其中为1的项代表\(v_i\)与该顶点连通。

• 代码实现 首先我们要知道这个结构要记录的东西：顶点数目\(|V|\)、边数目\(|E|\)、顶点名称、邻接矩阵。

缺点就是当顶点多而边少的情况下很浪费空间。

#define maxsize 1007
typedef struct {
    //v和e分别代表顶点数目和边数目
    //有向图中会把边数目记作弧数，也可以用a(arcnum)代替e
    int v, e;
    char V[maxsize];//存储顶点V
    int E[maxsize][maxsize];//存储E的邻接矩阵
} amgraph;

1.9.2 邻接表

• 定义：每个顶点 \( v_i \) 关联一个链表，包含所有顶点 \( v_j \)，使得 \( (v_i, v_j) \in E(G) \) 或 \( \langle v_i, v_j \rangle \in E(G) \)。

有点复杂抽象，我将其简单理解为多个链表的头指针”放“在一个数组里，而这个数组和其他要素一同组成了邻接表结构。更适用于稀疏图的存储，也就是上述”顶点多边少“的情况

"放"的对象是链表而非数组的原因是方便后续添加新的边。

• 空间复杂度：

  • 对于无向图：\( n \) 个头指针 + \( 2e \) 个节点（每条边在两个链表中出现）。
  • 总计：\( (n + 2e) \) 个指针 + \( 2e \) 个整数。

• 时间复杂度：

  • 顶点 \( v_i \) 的度数：\( O(\text{链表 } i \text{ 的节点数}) \)。
  • 检查所有边：\( O(n + e) \)。

• 有向图：

  • 计算入度需要：
    • 逆邻接表：存储指向每个顶点的顶点链表。
    • 多重表表示：将正向和逆向边合并为单一结构（见 1.9.3）。

• 代码实现：

  • 结构表示：

    //邻接表每个节点存储表示
    struct edgenode {
        int index;//顶点的位置（理解成标记，所以不一定是int）
        struct node* next;//指向下一节点的指针
    } edgenode;
    
    //邻接表的存储结构
    struct algraph {
        int v, e;//顶点和边的数量
        struct node **adjlist;//二维指针
    } algraph;
    

  • 相关操作：

    // 创建一个新节点
    struct node *create_node(int newindex) {
        //要创建一个新节点，为其分配空间
        struct node* temp = (struct node*) malloc(sizeof(struct node));
        //赋予节点数据
        temp->index = newindex;
        temp->next = NULL;
        return temp;
    }
    

    // 对邻接表初始化
    struct algraph *create_adjlist(int new_v, int new_e) {
        //为邻接表分配空间
        struct algraph *temp = malloc(sizeof(struct algraph));
        //为这个二维指针指向分配了数目为new_v（即顶点数）个空间，
        //而每个空间都是struct node*的大小。
        //此处使用calloc函数让其初始化。
        temp->adjlist = calloc(new_v, sizeof(struct node*));
        //其他数据
        temp->v = new_v;
        temp->e = new_e;
        //初始化结束，返回邻接表的指针
        return temp;
    }
    

1.9.3 邻接多重表

• 动机：在邻接表中，每条边 \( (i, j) \) 出现两次（在 \( i \) 和 \( j \) 的链表中），可能导致边标记复杂化。
• 定义：将边 \( (i, j) \) 的两个节点合并为一个节点，添加额外字段（如标记位）。
• 优点：
  • 简化遍历过程中的边标记。
  • 空间：与邻接表相同，\( (n + 2e) \) 个指针 + \( 2e \) 个整数，不包括标记位。
• 扩展：可为加权图添加权重字段。
• 代码示例：

typedef struct EdgeNode {
    int vertex1;          // 边的第一个顶点
    int vertex2;          // 边的第二个顶点
    int marked;           // 标记位（0 未访问，1 已访问）
    struct EdgeNode* next1; // 与 vertex1 相关的下一条边
    struct EdgeNode* next2; // 与 vertex2 相关的下一条边
} EdgeNode;

1.9.4 加权图(weighed edges)

加权图相当于给边加了一个值，边的值就不再是清一色的”1“。

• 对于邻接矩阵而言，相当于将矩阵中的1改为相应的权。
• 对于邻接表和临界多重表而言，相当于在结构体中加入了权(weight)数据，代码如下：

struct edgenode {
    int index;//顶点的位置（理解成标记，所以不一定是int）
    struct node* next;//指向下一节点的指针
} edgenode;

2. 拓扑排序

拓扑排序是一种对有向无环图（DAG）的顶点进行线性排序的算法，基于优先约束。本节探讨其应用与实现。

2.1 AOV 网络

• 定义：一个工程中的有向图，其顶点代表一些活动，而弧代表一些关系，这种有向图就叫顶点活动网络(AOV network = Activity on Vertex Network)，其中：
  • 顶点 \( V(G) \) 表示活动（例如课程）。
  • 边 \( E(G) \) 表示优先关系（例如，\( \langle C_i, C_j \rangle \) 表示 \( C_i \) 是 \( C_j \) 的先修课程）。
• 优先关系：
  • 前驱&后继：存在从 \( i \) 到 \( j \) 的有向路径， \( i \) 就是 \( j \) 的前驱，\( j \) 是 \( i \) 的后继。
  • 直接前驱&直接后继： \( i \) 和 \( j \) 之间存在弧\(\langle i, j\rangle\)，那么 \( i \) 就是 \( j \) 的直接前驱， \( j \) 是 \( i \) 的直接后继。
• 偏序：
  • 优先关系是偏序，需满足：
    • 传递性：若 \( i \rightarrow k \)，\( k \rightarrow j \)，则 \( i \rightarrow j \)。
    • 非自反性：没有顶点 \( i \) 是其自身的优先（即无环且不会指向自己）。

这在离散数学中已经学过

可行的 AOV 网络必须是 DAG，因为环会导致优先矛盾（例如，\( i \) 必须先于 \( i \)）。

2.2 拓扑顺序

• 定义：拓扑序列是顶点的线性排序，使得若 \( i \) 是 \( j \) 的前驱，则 \( i \) 在排序中位于 \( j \) 之前。更具体到图论中，如果对于一个图\(G(V, E)\)，如果对于顶点\(V_i\)与\(V_j\)，存在从\(V_i\)到\(V_j\)的路径，那么在顶点序列中，\(V_i\)一定在\(V_j\)之前，这就叫拓扑序列；而将一个有向图构成拓扑序列，就叫拓扑排序。
• 非唯一性：对于同一个 DAG，可能存在多个有效的拓扑顺序。

2.3 拓扑排序算法

• 目标：测试 AOV 网络是否可行（即是否为 DAG），并在可能时生成拓扑顺序。
• 基本算法：

  void Topsort(Graph G) {
      int Counter;
      Vertex V, W;
      for (Counter = 0; Counter < NumVertex; Counter++) {
          V = FindNewVertexOfDegreeZero(); /* O(|V|) */
          if (V == NotAVertex) {
              Error("图中存在环");
              break;
          }
          TopNum[V] = Counter; /* 或输出 V */
          for (each W adjacent from V) {
              indegree[W]--;
          }
      }
  }
  

• 解释：
  • 反复寻找入度为 0 的顶点 \( V \)（无先修条件）。
  • 将其分配到拓扑顺序的下一个位置。
  • 减少所有从 \( V \) 邻接的顶点 \( W \) 的入度（模拟完成 \( V \)）。
  • 如果在处理所有顶点之前找不到入度为 0 的顶点，则图中存在环，不是 DAG。
• 时间复杂度：
  • 寻找入度为 0 的顶点：\( O(|V|) \)。
  • 总计：\( O(|V|^2) \)。

2.4 改进的拓扑排序

• 优化：使用队列存储所有入度为 0 的顶点，避免重复扫描。
• 改进算法：

  void Topsort( Graph G ) {
      //定义一个队列Q，储存若干轮次筛选后入度为0的顶点
      Queue  Q;
      int  Counter = 0;
      Vertex  V, W;
      //创建Q的大小（顶点数目）
      Q = CreateQueue( NumVertex );
      //初始化Q
      MakeEmpty( Q );
      //这个循环是为了将入度为0的顶点筛入队列
      //显然,这个循环的时间复杂度为O(|V|)
      for ( each vertex V ) {
          if ( Indegree[ V ] == 0 ){
              Enqueue( V, Q );
          }
      }
      //直到顶点排完，有多少条弧就循环多少次，
      //说明这个循环的时间复杂度为O(|E|)
      while ( !IsEmpty( Q ) ) {
          //从Q中取出一个顶点V
          V = Dequeue( Q );
          //为顶点V分配拓扑排序的序列，counter会逐渐从0递增
          //counter赋给这个TopNum，实际上也代表了序列
          TopNum[ V ] = ++ Counter; /* assign next */
          //分析V的后继W，若W入度为1，则减为0，入队列中
          for ( each W adjacent from V ) {
              if ( ––Indegree[ W ] == 0 ) {
                  Enqueue( W, Q );
              }
          }
      }  /* end-while */
      //如果counter和Numvertex不等，说明不是DAG
      if ( Counter != NumVertex ) {
          Error( “Graph has a cycle” );
      }
      //释放Q
      DisposeQueue( Q ); /* free memory */
  }
  

• 解释：
  • 初始化一个队列，包含所有入度为 0 的顶点。
  • 从队列中取出一个顶点 \( V \)，分配到下一个位置，并减少其后继的入度。
  • 将入度变为 0 的后继入队。
  • 如果处理的顶点数少于 \( |V| \)，则存在环。
• 时间复杂度：
  • 初始化：\( O(|V|) \)。
  • 处理边：每条边在更新入度时处理一次，因此为 \( O(|E|) \)。
  • 总计：\( O(|V| + |E|) \)。