【数据结构】图

基本概念

• 顶点(vertex)
• 边(edge)
• 有向图(directed graph)
• 无向图(undirected graph)
• 有向边(directed edge)
• 无向边(undirected edge)
• 顶点的度(degree)
• 入度(in-degree)
• 出度(out-degree)
• 路径(path)
• 简单路径(simple path)
• 环(cycle)
• 简单环(simple cycle)
• 连通图(connected graph)：任意两个顶点之间都存在路径的无向图称为连通图。
• 连通分量(connected component)
• 强连通图(strongly connected graph)：任意两个顶点之间都存在路径的有向图称为强连通图。
• 强连通分量(strongly connected component)
• 简单图与多重图：没有重复边和自环的图称为简单图，有重复边和自环的图称为多重图。
• 简单路径与简单回路：路径上的顶点不重复出现的路径称为简单路径。回路上的顶点不重复出现的回路称为简单回路。

  连通图、强连通图

• 若无向图中任意两个顶点之间都存在路径(不是边)，则称该图为连通图，否则称为非连通图。
• 若有向图中任何一对顶点都是强连通的（都存在有向路径），则称该图为强连通图。

常见考点：

无向图

• 对于有n个顶点的无向图G，如果是连通图最少有n-1条边，如果E>n-1则一定有回路。
• 如果是非连通图最多有C(n-1,2)条边。
• 所有顶点的度之和为2E。
• 无向完全图共有C(n,2)条边。

  有向图

• 如果是强连通图，最少有n条边，形成回路。
• 所有顶点的出度之和=入度之和=E
• 所有顶点的度之和为2E
• 有向完全图有2C(n,2)条边。

子图

如果图G’的顶点集V’和边集E’分别是图G的顶点集V和边集E的子集，则称图G’=(V’,E’)为图G的子图。

生成子图

一个包含图G的所有顶点的子图称为生成子图。也就是说顶点一样、边可以少一些。

连通分量

无向图的极大连通子图称为连通分量。极大意思是每一块连通的子图都没有其他可以再加入其他的顶点或边了。

强连通分量

有向图的极大强连通子图称为强连通分量。分量中的每个顶点都可以到达其他的顶点。

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。生成树中不能有回路。

生成森林

生成森林是非连通图的连通分量的生成树的集合。

完整图（完全图）

完整图是指图中任意两个顶点之间都有边的图。

稀疏图、稠密图

稀疏图指的是边数相对于顶点数较少的图，稠密图指的是边数相对于顶点数较多的图。

树、森林、有向树

• 树是n个顶点n-1条边的连通图。
• 森林是n个顶点m条边的非连通图。
• 有向树是n个顶点n-1条边的有向连通图。

图的存储结构

邻接矩阵

邻接矩阵是用两个数组来表示图。一个一维数组存储图中顶点信息（顶点表），一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

#define MaxVertexNum 100//顶点数目的最大值
typedef struct{
    char Vex[MaxVertexNum];
    int Edge[MaxVertexNum][MaxVertexNum];
    int vexnum,arcnum;
}MGraph;

邻接矩阵法的性质

• $A^k[i][j]$表示从顶点i到顶点j的长度为k的路径数目。
  $A^k[i][j]=a{i1}a{1j}+a{i2}a{2j}+…+a{ik}a{kj}$
  矩阵乘法
• 空间复杂度$O(|V|^2)$，之和顶点数有关
• 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上/下三角区）
• 适合存储稠密图
• 计算度/出度/入度需要遍历对应的行/列

  邻接表（顺序+链式存储）

  无向图的邻接表空间复杂度$O(|V|+2|E|)$，有向图的邻接表空间复杂度$O(|V|+|E|)$

邻接表法的性质

• 无向图的邻接表是单链表，有向图的邻接表是双链表
• 适合存储稀疏图
• 计算入度不方便
• 表示方式不唯一

十字链表（存储有向图）

空间复杂度$O(|V|+|E|)$

邻接多重表（存储无向图）

图的遍历

深度优先搜索dfs

用堆栈递归实现dfs。

#include <stdbool.h>
#include <stdio.h>

#define MaxVertexNum 100 // 假设图的最大顶点数为100

// 定义顶点的数据结构
typedef int Vertex;

// 定义图的数据结构
typedef struct Graph {
    int Nv; // 顶点数
    int G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
} *Graph;

// 标记顶点是否已访问的数组
bool visited[MaxVertexNum];

// 初始化visited数组
void InitializeVisited() {
    for (int i = 0; i < MaxVertexNum; i++) {
        visited[i] = false;
    }
}

// 访问顶点的操作，这里你可以根据具体需求进行操作
void Visit(Vertex V) {
    printf("%d ", V);
}

// 获取顶点V的第一个邻居顶点
Vertex FirstNeighbor(Graph G, Vertex V) {
    for (int W = 0; W < G->Nv; W++) {
        if (G->G[V][W] != 0) {
            return W;
        }
    }
    return -1; // 没有邻居顶点
}

// 获取顶点V的下一个邻居顶点
Vertex NextNeighbor(Graph G, Vertex V, Vertex W) {
    for (int nextW = W + 1; nextW < G->Nv; nextW++) {
        if (G->G[V][nextW] != 0) {
            return nextW;
        }
    }
    return -1; // 没有下一个邻居顶点
}

// DFS遍历函数
void DFS(Graph G, Vertex V) {
    visited[V] = true;
    Visit(V); // 访问顶点V，这里可以根据需求进行其他操作

    // 遍历V的邻居顶点
    for (Vertex W = FirstNeighbor(G, V); W >= 0; W = NextNeighbor(G, V, W)) {
        if (!visited[W]) {
            DFS(G, W); // 递归调用DFS来访问未访问的邻居顶点
        }
    }
}

int main() {
    // 创建一个示例图并调用DFS遍历
    Graph G = (Graph)malloc(sizeof(struct Graph));
    G->Nv = 6; // 假设有6个顶点

    // 初始化邻接矩阵，这里可以根据具体图的情况进行修改
    int adjMatrix[6][6] = {
        {0, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1, 0},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };

    for (int i = 0; i < G->Nv; i++) {
        for (int j = 0; j < G->Nv; j++) {
            G->G[i][j] = adjMatrix[i][j];
        }
    }

    InitializeVisited(); // 初始化visited数组
    DFS(G, 0); // 从顶点0开始进行DFS遍历

    return 0;
}

dfs的应用：spanning tree(生成树/支撑树)

dfs算法表现

• 时间复杂度：o(n+m)
• 空间复杂度：o(n+m)

广度优先搜索bfs

用队列递归实现bfs。

#include <stdbool.h>
#include <stdio.h>

#define MaxVertexNum 100 // 假设图的最大顶点数为100

// 定义顶点的数据结构
typedef int Vertex;

// 定义一个队列数据结构，用于BFS遍历
typedef struct Queue {
    Vertex data[MaxVertexNum];
    int front, rear;
} *Queue;

// 创建一个空队列
Queue CreateQueue(int maxSize) {
    Queue Q = (Queue)malloc(sizeof(struct Queue));
    Q->front = Q->rear = 0;
    return Q;
}

// 判断队列是否为空
bool IsEmpty(Queue Q) {
    return Q->front == Q->rear;
}

// 入队操作
void Enqueue(Vertex V, Queue Q) {
    Q->data[Q->rear++] = V;
}

// 出队操作
Vertex Dequeue(Queue Q) {
    return Q->data[Q->front++];
}

// 定义图的数据结构
typedef struct Graph {
    int Nv; // 顶点数
    int G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
} *Graph;

// 标记顶点是否已访问的数组
bool visited[MaxVertexNum];

// 初始化visited数组
void InitializeVisited() {
    for (int i = 0; i < MaxVertexNum; i++) {
        visited[i] = false;
    }
}

// 访问顶点的操作，这里你可以根据具体需求进行操作
void Visit(Vertex V) {
    printf("%d ", V);
}

// 获取顶点V的第一个邻居顶点
Vertex FirstNeighbor(Graph G, Vertex V) {
    for (int W = 0; W < G->Nv; W++) {
        if (G->G[V][W] != 0) {
            return W;
        }
    }
    return -1; // 没有邻居顶点
}

// 获取顶点V的下一个邻居顶点
Vertex NextNeighbor(Graph G, Vertex V, Vertex W) {
    for (int nextW = W + 1; nextW < G->Nv; nextW++) {
        if (G->G[V][nextW] != 0) {
            return nextW;
        }
    }
    return -1; // 没有下一个邻居顶点
}

// BFS遍历函数
void BFS(Graph G, Vertex V) {
    Queue Q = CreateQueue(MaxVertexNum); // 创建队列用于BFS
    visited[V] = true;
    Enqueue(V, Q);

    while (!IsEmpty(Q)) {
        V = Dequeue(Q);
        Visit(V); // 访问顶点V，这里可以根据需求进行其他操作

        // 遍历V的邻居顶点
        for (Vertex W = FirstNeighbor(G, V); W >= 0; W = NextNeighbor(G, V, W)) {
            if (!visited[W]) {
                visited[W] = true;
                Enqueue(W, Q);
            }
        }
    }
}

int main() {
    // 创建一个示例图并调用BFS遍历
    Graph G = (Graph)malloc(sizeof(struct Graph));
    G->Nv = 6; // 假设有6个顶点

    // 初始化邻接矩阵，这里可以根据具体图的情况进行修改
    int adjMatrix[6][6] = {
        {0, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1, 0},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };

    for (int i = 0; i < G->Nv; i++) {
        for (int j = 0; j < G->Nv; j++) {
            G->G[i][j] = adjMatrix[i][j];
        }
    }

    InitializeVisited(); // 初始化visited数组
    BFS(G, 0); // 从顶点0开始进行BFS遍历

    return 0;
}

拓扑排序

• 有环的连通图不可能进行拓扑排序
• 所有箭头都向右的任何线性排序都是有效的解决方案
• 在不违反先决条件（依赖关系）的前提下把任务组织成一个线性顺序，使得他们能一口气被完成
• 找一个没有入度的点开始

DAG(有限无环图)

AOV网（Activity On Vertex NetWork，用顶点表示事件的网）有向边（Vi,Vj）表示Vi活动必须先于Vj活动执行，即Vi活动是Vj活动的先决条件。AOV网中不允许有回路，因为回路意味着某个活动的先决条件是它自己，这是不可能的。

算法步骤：

1. 找到一个没有入度的顶点
2. 输出该顶点
3. 删除该顶点和所有以它为起点的有向边（删除直接进行marked即可，只有入度为0而且unmarked的点才能进入队列，如果不存在说明图是有环的）
4. 重复1-3直到所有顶点都被输出，图为空

算法性能分析

• 如果使用邻接表，时间复杂度：O(|V|+|E|)
• 如果使用邻接矩阵，时间复杂度为O(|V|^2)

  算法实现

  （基于邻接矩阵）

  #include <stdio.h>
  
  #define MaxVertexNum 100 // 假设图的最大顶点数为100
  
  // 定义顶点的数据结构
  typedef int Vertex;
  
  // 定义一个队列数据结构，用于辅助拓扑排序
  typedef struct Queue {
      Vertex data[MaxVertexNum];
      int front, rear;
  } *Queue;
  
  // 创建一个空队列
  Queue CreateQueue(int maxSize) {
      Queue Q = (Queue)malloc(sizeof(struct Queue));
      Q->front = Q->rear = 0;
      return Q;
  }
  
  // 判断队列是否为空
  int IsEmpty(Queue Q) {
      return Q->front == Q->rear;
  }
  
  // 入队操作
  void Enqueue(Vertex V, Queue Q) {
      Q->data[Q->rear++] = V;
  }
  
  // 出队操作
  Vertex Dequeue(Queue Q) {
      return Q->data[Q->front++];
  }
  
  // 定义图的数据结构
  typedef struct Graph {
      int Nv; // 顶点数
      int G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
  } *Graph;
  
  // 拓扑排序函数
  void TopSort(Graph G) {
      int Indegree[MaxVertexNum], cnt;
      Vertex V, W;
      Queue Q = CreateQueue(MaxVertexNum);
  
      // 初始化顶点的入度为0
      for (V = 0; V < G->Nv; V++) {
          Indegree[V] = 0;
      }
  
      // 计算每个顶点的入度
      for (V = 0; V < G->Nv; V++) {
          for (W = 0; W < G->Nv; W++) {
              if (G->G[V][W] != 0) {
                  Indegree[W]++;
              }
          }
      }
  
      // 将入度为0的顶点入队
      for (V = 0; V < G->Nv; V++) {
          if (Indegree[V] == 0) {
              Enqueue(V, Q);
          }
      }
  
      cnt = 0;
  
      // 开始拓扑排序
      while (!IsEmpty(Q)) {
          V = Dequeue(Q);
          printf("%d ", V);
          cnt++;
  
          // 更新与V相邻的顶点的入度
          for (W = 0; W < G->Nv; W++) {
              if (G->G[V][W] != 0) {
                  if (--Indegree[W] == 0) {
                      Enqueue(W, Q);
                  }
              }
          }
      }
  
      // 如果排序后的顶点数不等于总顶点数，说明图中存在环路
      if (cnt != G->Nv) {
          printf("Graph has a cycle\n");
      }
  }
  
  int main() {
      // 创建一个示例图并调用拓扑排序
      Graph G = (Graph)malloc(sizeof(struct Graph));
      G->Nv = 6; // 假设有6个顶点
  
      // 初始化邻接矩阵，这里可以根据具体图的情况进行修改
      int adjMatrix[6][6] = {
          {0, 1, 1, 0, 0, 0},
          {0, 0, 0, 1, 0, 0},
          {0, 0, 0, 1, 1, 0},
          {0, 0, 0, 0, 0, 1},
          {0, 0, 0, 0, 0, 1},
          {0, 0, 0, 0, 0, 0}
      };
  
      for (int i = 0; i < G->Nv; i++) {
          for (int j = 0; j < G->Nv; j++) {
              G->G[i][j] = adjMatrix[i][j];
          }
      }
  
      TopSort(G);
  
      return 0;
  }

  （基于邻接表（王道））

注意，indegree是记录当前顶点的入度，print是记录输出的拓扑序列。S是栈，用于存储入度为0的顶点。

bool Topplogy=icalSort(){
    InitStack(S);//初始化栈S
    for(i=0;i<G.vexnum;i++){
        if(indegree[i]==0){
            Push(S,i);//入度为0的顶点入栈
        }
    }
    int count=0;//对输出顶点计数初始化
    while(!StackEmpty(S)){
        Pop(S,i);//栈顶元素出栈
        print[count++]=i;//输出i号顶点并计数
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){
            v=p->adjvex;//对i号顶点的每个邻接的入度减1
            if(!(--indegree[v])){
                Push(S,v);//若入度减为0，则入栈
            }
        }
    }//while
    if(count<G.vexnum){
        return false;//该有向图有回路
    }else{
        return true;//该有向图无回路
    }
}

逆拓扑排序

原理类似，但是不好用邻接表，可以用邻接矩阵或者逆邻接表。

也可以用DFS实现逆拓扑排序。

AOE网（Activity On Edge NetWork，用边表示活动的网）顶点表示事件，边表示活动，边上的权值表示活动持续的时间。AOE网中不允许有回路，因为回路意味着某个活动的先决条件是它自己，这是不可能的。

最短路径

单源最短路径：求一个顶点到其他顶点的最短路径。

• bfs无权图
• dijkstra算法（有权图、无权图）
  各顶点之间的最短路径：求任意两个顶点之间的最短路径。
• floyd算法（有权图、无权图）

  bfs

• d[]:记录源点s到各个顶点的最短路径长度。
• path[]:记录路径上的前驱。初始化为-1。
• visited[]:记录顶点是否已经访问过。

void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示从u到i的最短路径
    for(int i=0;i<G.vexnum;i++){
        d[i]=INT_MAX;//初始化为无穷大
        path[i]=-1;//初始化为-1
    }
    d[u]=0;
    visited[u]=true;
    EnQueue(Q,u);
    while(!QueueEmpty(Q)){
        DeQueue(Q,u);//队头元素u出队
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
            if(!visited[w]){//w为u的尚未访问的邻接顶点
                visited[w]=true;//标记w已访问
                d[w]=d[u]+1;//路径长度加1
                path[w]=u;//最短路径应该从u到w
                EnQueue(Q,v);//顶点w入队
            }//if
        }
    }//while
}
#### Dijsktra算法
- **final数组**：标记已经找到最短路径的顶点，true表示已经找到最短路径。
- **dist数组**：记录源点s到各个顶点的最短路径长度。
- **path数组**：记录路径上的前驱。
初始化：final[s]=true，dist[s]=0，path[s]=-1。其他顶点的final都为false，dist都为无穷大，path都为-1。

循环遍历所有节点，找到还没确定最短路径而且dist最小的顶点$V_i$，令其final[i]=true。

然后重新检查所有和$V_i$相邻的顶点$V_j$，如果$V_i$到$V_j$的距离比$V_j$当前的最短路径还要短，就更新$V_j$的最短路径和前驱。

时间复杂度：$O(|V|^2)$。算法实现和复杂度都和prim类似。

dijsktra不适用于有负权边的图。

#### Floyd算法
有|v|个顶点，构建|v|*|v|的**A矩阵**、**path矩阵**。A[i][j]表示**从i到j的最短路径长度**，path[i][j]表示从i到j的最短路径上的第一个**中间顶点**。

path矩阵初始化为-1，意为没有中间顶点，直接相连。

A矩阵初始化为邻接矩阵，如果两个顶点之间没有边，就初始化为无穷大。

核心coding内容：
```C++
for(k=0;k<n;k++){//考虑以vk为中转点的情况
    for(i=0;i<n;i++){//遍历所有顶点
        for(j=0;j<n;j++){
            if(A[i][k]+A[k][j]<A[i][j]){//以vk为中转点的路径更短
                A[i][j]=A[i][k]+A[k][j];//更新最短路径
                path[i][j]=k;//更新路径上的中转点
            }
        }
    }
}

时间复杂度：$O(|V|^3)$

Floyd算法可以用于有负权边的图。但是如果图中存在负权回路，Floyd算法就不适用了。这种图可能没有最短路径，因为可以无限循环下去。

最小生成树

Prim算法（普利姆）

Prim算法:从一个顶点出发，每次找到当前生成树中各个节点外延的距离最小的顶点，加入到生成树中，直到所有顶点都纳入为止。

复杂度

• 时间复杂度：$O(|V|^2)$,只和顶点数有关，适合用于边稠密图

  算法核心实现

  维护两个数组，一个isjoin数组，用来记录顶点是否已经加入生成树，一个lowcast数组，用来记录顶点到生成树的最小距离。

从起始顶点开始，遍历lowcast数组，找到最小的lowcast值，将对应的顶点加入到生成树中，然后更新lowcast数组。

一共需要进行n-1次循环，每次循环需要遍历lowcast数组，时间复杂度为$O(|V|^2)$。

Kruskal算法（克鲁斯卡尔）

Kruskal算法:把所有权重边排序，每次找到一条最小而且不会导致现有的生成树成环的边，加入到生成树中。

复杂度

• 时间复杂度：$O(|E|log_2|E|)$,只和边数有关，适合用于边稀疏图

  算法核心实现

  将所有边按照权重排序，使用并查集进行辅助判断两个顶点是否连通（属于同一集合）。这个过程的时间复杂度为$O(log_2|E|)$。共执行e轮，所以时间复杂度为$O(|E|log_2|E|)$。