数据结构-图(6)

4FGR2026-05-122026-05-14

6.1 图的基本概念

图 \(G\) 由顶点集 \(V\) 和边集 \(E\) 组成，记为 \(G=(V,E)\) 。其中，\(V(G)\) 表示图 \(G\) 中顶点的有限非空集。

存疑，这也许是考研标准，但一般空图也是图

用 \(|V|\) 表示图中 \(G\) 中点的数量。，用 \(|E|\) 表示图中 \(G\) 中边的数量。

无向图中的极大连通子图称为连通分量

极大连通子图：子图是连通的，而且不存在包含它的连通子图，也就是边和点尽可能多的。

有向图中的极大强连通子图成为有向图的强连通分量

连通图的生成树是包含图中全部顶点的一个极小连通子图

极小连通子图：子图是连通的，而且在相同顶点集，不存在边比它的少连通子图，也就是边尽可能少，但点要尽可能多。

无向完全图：无向图中任意两个顶点之间都存在边
有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧
边数很少的图称为稀疏图，反之称为稠密图
没有绝对的界限，一般来说 \(|E| < |V|\log|V|\) 时，可以将 \(G\) 视为稀疏图
树：不存在回路，且连通的无向图
有向树：一个顶点的入度为 \(0\) 、其余顶点的入度均为 \(1\) 的有向图，称为有向树
- \(n\) 个顶点的树，必有 \(n-1\) 条边。
- \(n\) 个顶点的图，若 \(|E|>n-1\) ，则一定有回路

图的存储与基本操作

邻接矩阵

使用二维数组存边，其中 \(adj[u][v]=1\) 表示存在 \(u\) 到 \(v\) 的边，为 \(0\) 表示不存在，在带权图中值为边权。

#define MaxVeertexNum 100
typedef struct{
    char vex[MaxVertexNum]; // 顶点表
    ine adj[MaxVertexNum][MaxVertexNum]; //邻接矩阵
    int vexnum,arcnum; // 图的当前顶点和边数/弧数
}MGragh;

复杂度

查询是否存在某条边：\(O(1)\)。

遍历一个点的所有出边：\(O(n)\)。

遍历整张图：\(O(n^2)\)。

空间复杂度：\(O(n^2)\)。

性质

邻接表

如果要存无向图，注意双向建边。

复杂度

查询是否存在某条边：\(O(d^+(u))\) (如果事先进行了排序可以使用二分查找)

遍历一个点的所有出边：\(O(d^+(u))\)。

遍历整张图：\(O(n+m)\)。

空间复杂度：\(O(m)\)。

十字链表

理解即可

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

顺着绿线找顶点的出边

顺着橙线找顶点的入边

十字链表仅用于存储有向图

邻接多重表

理解即可

只能存无向图

图的基本操作

用 \(<x,y>\) 表示有向边，\((x,y)\) 表示无向边

6.3 图的遍历

广度优先遍历

进行 \(BFS\) 的过程建树，即为广度优先生成树，同时，在无向图和有向图中，若权值为1（距离仅是边数），可以用 \(BFS\) 求单源最短路.

bool visited[N]; // 访问标记遍历
int d[N]; // 对无向图进行
Queue Q;
void BFS_Search(Gragh g){
    for(int i=0;i<G.vexnum;i++) visited[i] = false; // 初始化数组
    InitQueue(Q); // 初始化队列
    for(int i=0;i<G.vexnum;i++){ // 遍历每个点（假设编号从0出发）
        if(!visited[i]){
            bfs(G,i);
        }
    }
}

// 邻接表法
void bfs(Gragh G,int i){ // 顺便求第i个点出发的单源最短路(无权)
    visit(i);
    visit[i] = true;
    d[i] = 0; // 自己到自己为0（或者无穷大）
    EnQueue(Q,i);
    while(!isEmpty(Q)){
        int u;
        DeQueue(Q,u); // 获取队首元素
        for(ArcNode *p=G.vertices[v].firstacrc;p!=NULL;p=p->nextarc){
            int v = p->adjvex; // 有边(u,v)
            if(!visited[v]){ // 未被访问过
                visit(v); // 访问结点
                d[v] = d[u]+1; // 距离是前驱节点u到i的距离加1
                visited[v] = true;
                EnQueue(Q,w);
            }
        }
    }
}

// 邻接矩阵法
void bfs(MGragh G,int i){
    visit(i);
    visited[i] = true;
    EnQueue(i);
    while(!isEmpty(Q)){
        int u;
        Dequeue(Q,u);
        for(int p=0;p<G.vexnum;p++){
            if(!visited[p]&&G.edge[i][j]=1){
                visit(p);
                visited[p] = true;
                EnQueue(Q,p);
            }
        }
    }
}

深度优先遍历

对一个结点进行DFS对应的序列就是一颗深度优先生成树，如果图不止一个连通分量，DFS就是深度优先生成森林。

bool visited[N];
void DFS_Search(Gragh G){
    for(int i=0;i<G.vexnum;i++) visited[i] = false; // 初始化数组
    for(int i=0;i<G.vexnum;i++){ // 遍历每个点（假设编号从0出发）
        if(!visited[i]){
            dfs(G,i);
        }
    }
}

// 邻接表法
void dfs(Gragh G,int u){
    visit(u);
    visited[u] = true;
    for(ArcNode *p=G.vertices[u].firstarc;p!=NULL;p=p->nextarc){
        int v = p->adjvex;
        if(!visited[v]){
            dfs(G,v); // 递归访问v
        }
    }
}

// 邻接矩阵法
void dfs(Gragh G,int u){
    visit(u);
    visited[u] = true;
    for(int v=0;v<G.vexnum;v++){
        if(!visited[v]&&G.edge[i][j]=1){
            dfs(G,v); // 递归访问v
        }
    }
}

6.4 图的应用

最小生成树

**Prim（普里姆）**算法的思想是，从一个顶点出发，加入集合 \(U\) ，从集合 \(U\) 中的所有顶点中，找出其中离集合最近的顶点 \(v\) ，并将边和顶点均加入集合中，知道所有顶点都被加入集合 \(U\) 为止。

算法简单实现如下：

void Prim(G,T){
    T = ∅; // 初始化空树
    U = {w}; // 任意添加一个顶点
    while(U!=V){ // 直到集合涵盖所有顶点
        // 找到权值最小的边(u,v)
        T=T∪{(u,v)}; // 边归入树
        U=U∪{(v)}; // 顶点归入树
    }
}

**Kruskal（克鲁斯卡尔）**算法与 Prim 的方式不同，Kruskal 按照边的权值的递增次序选择合适的边构造最小生成树。

每次考察边的权值，选出最小的，并且当前边连接的两个顶点属于生成树 \(T\) 中不同的连通分量（可通过并查集判断），则将该边加入 \(T\) ；否则，舍弃，直到重复过程满足条件。最后结束时，所有顶点应该同属于一个连通分量。

void Kruskal(V,T){
    T=V; // 初始化树，仅含顶点
    nums = n; // 连通分量数
    while(nums>1){
        if(find(u)!=find(v)){ // 各自属于不同的连通分量,dsu为并查集
            T=T∪{(u,v)}; // 将边加入生成树中
            nums--;
        }
    }
}

若有兴趣，以上的具体代码可见最小生成树 - OI Wiki

最短路径

最短路径可以分为两类

单源最短路径：从某个顶点 \(v\) 出发，到所有顶点的最短路径
- 可用 Dijkstra（迪杰斯特拉）
所有点对间的最短路径，可用**Floyd（弗洛伊德）**求解

拓展：还可了解Bellman-Ford和其优化SPFA（单源）与Johnson（全源）最短路 - OI Wiki

Dijkstra

打过算竟的朋友应该都知道，其能用优先队列优化至 \(O(n\log n)\) ，不过考研不建议炫技

注意：无法用于负权图

从 \(v_0\) 出发，初始所有顶点到 \(v_0\) 的距离 \(dis\) 为无穷大，仅 \(dis[v_0]=0\) ，逐步选择到 \(v_0\) 最短的顶点 \(u\) （第一次显然是 \(v_0\) 本身），这意味着 \(dis[u]\) 的权值是最终最小的，标记 \(vis[u]=1\) ，避免再次选中，并更新 \(v_0\) 到所有**未确定最短路径的顶点(!vis[v])**的最短路径长度 \(dis[v] = min(dis[v],dis[u]+w)\) 。跑完 \(n\) 轮，此时 \(dis[i]\) 一定是到 \(v_0\) 的最短路距离，算法结束。

和王道的不同，但大同小异

struct edge {
  int v, w;
};

vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int)); // 初始化无穷大
  dis[s] = 0;
  for (int i = 1; i <= n; i++) {
    int u = 0, mind = 0x3f3f3f3f;
    for (int j = 1; j <= n; j++) // 搜索dis最小的顶点
      if (!vis[j] && dis[j] < mind) u = j, mind = dis[j];
    vis[u] = true;
    for (auto ed : e[u]) { // 更新其余点的最短路
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
    }
  }
}

Floyd-Warshall

使用动态规划思想，将问题分解为多个阶段，一般用邻接矩阵。

对第 \(i\) 到 \(j\) 的最短路径 \(f[i][j]\)，能否用 \(f[i][k]+f[k][j]\) 求得，即在允许 \(k\) 作为中转站的情况下，更新能被更新的最短路，一般地，\(k\) 应该从 \(1\) 出发遍历至 \(n\) 。

for (k = 0; k < n; k++) {
  for (x = 0; x < n; x++) { // 遍历点对
    for (y = 0; y < n; y++) {
        if(f[x][y]>f[x][k] + f[k][y]){
            f[x][y]=f[x][k]+f[k][y];
            path[x][y] = k; // (x,y)的最短路中转需要k
        }
    }
  }
}

有向无环图描述表达式

一个不存在环的有向图，称为有向无环图（DAG）

拓扑排序

DAG的拓扑排序序列包含所有顶点

拓扑排序：找到一个顺序，满足

选择入度为 \(0\) （没有前驱）的结点，输出
删除出该点的有向边
重复上述步骤，直到不存在入度为 \(0\) 的结点为止。

这里给出bfs的实现，dfs的非递归形式可见王道书

int n, m;
vector<int> G[MAXN];
int in[MAXN];  // 存储每个结点的入度

bool toposort() {
  vector<int> L;
  queue<int> S;
  for (int i = 1; i <= n; i++)
    if (in[i] == 0) S.push(i);
  while (!S.empty()) {
    int u = S.front();
    S.pop();
    L.push_back(u);
    for (auto v : G[u]) {
      if (--in[v] == 0) {
        S.push(v);
      }
    }
  }
  if (L.size() == n) {
    for (auto i : L) cout << i << ' ';
    return true;
  }
  return false;
}