时间戳

首页 > 技术文章 > 数据结构笔记——图

数据结构笔记——图

robod 2022-04-14 17:18 原文

好好学习，天天向上

本文已收录至我的Github仓库DayDayUP：github.com/RobodLee/DayDayUP，欢迎Star

⭐⭐⭐⭐⭐转载请注明出处：https://blog.csdn.net/weixin_43461520/article/details/124176292

6.1 图的基本概念

图的定义

图G由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。若V = {v1, v2, … , vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E = {(u, v) | u∈V, v∈V}，用|E|表示图G中边的条数。

V一定是非空集，E可以是空集。

无向图、有向图

若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w, v)，因为(v, w) = (w, v)，其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v, w>，其中v、w是顶点，v称为弧尾（无箭头的定点），w称为弧头（箭头指向的顶点），<v, w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。 <v, w> ≠ <w, v>。

简单图、多重图

简单图：
①不存在重复边；
② 不存在顶点到自身的边。

图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。

顶点的度、入度、出度

对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。
例如，图中A的度为1。
无向图全部顶点的度之和为边数的2倍。

对于有向图：入度是以顶点v为终点的有向边的数目，记为ID(v)；出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。
例如，图中A的入度为1，出度为4。
有向图中所有顶点的 入度之和=出度之和=边数。

顶点-顶点的关系描述

  • 路径：一个顶点到另一个顶点之间的一条路径是指其经过的顶点序列。例如左图中A到C的路径就是ABDC或者ABEC等。
  • 回路：第一个顶点和最后一个顶点相同的路径称为回路或环。例如右图中ABCDA。
  • 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
  • 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
  • 路径长度：路径上边的数目。
  • 点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
  • 连通：无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。
  • 强连通：有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。

连通图、强联通图

若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。

若图中任何一对顶点都是强连通的，则称此图为强连通图。

图的局部——子图

对于有向图和无向图而言，设有两个图G = (V , E)和G' = (V', E')，若 V' 是V的子集，且E'是E的子集，则称 G' 是G的子图。

若有满足V(G')=V(G)的子图G'，则称其为G的生成子图。

连通分量和强连通分量

无向图中的极大连通子图称为连通分量。其中，子图必须连通，且包含尽可能多的顶点和边。

有向图中的极大强连通子图称为有向图的强连通分量。其中，子图必须强连通，同时保留尽可能多的边。

生成树和生成森林

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

若图中顶点数为n，则它的生成树含有n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

边的权、带权图/网

  • 边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
  • 带权图/网：边上带有权值的图称为带权图，也称网。
  • 带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

几种特殊形态的图

  • 无向完全图：图中任意两个顶点之间都存在边
  • 有向完全图：图中任意两个顶点之间都存在方向相反的两条弧
  • 稀疏图：边数很少的图
  • 稠密图：边数很多的图
  • 树：不存在回路，且连通的无向图，必有n-1条边。
  • 有向树：一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

6.2图的存储及基本操作

邻接矩阵法

领接矩阵存储是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各个顶点之间的关系），存储顶点之间的邻接关系的二维数组称为邻接矩阵。

#define MaxVertexNum 100        //顶点的数目的最大值
typedef char VertexType;        //顶点的数据类型
typedef int EdgeType;           //带权图中边上权值的数据类型

typedef struct {
    VertexType Vex[MaxVertexNum];               //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表
    int vexNum, arcNum;                         //图的当前顶点数和弧数
} MGraph;

  • 无向图中，第i个结点的度=第i行（或第i列）的非零元素个数。例如结点A的度=1+1+1=3。
  • 有向图中，第i个结点的出度 = 第i行的非零元素个数。第i个结点的入度 =第i列的非零元素个数。第i个结点的度 = 第i行、第i列的非零元素个数之和。
  • 邻接矩阵法求顶点的 度/出度/入度 的时间复杂度为 O(|V|)。
  • 空间复杂度：O(|V|²)，只和顶点数相关，和实际的边数无关。
  • 适合用于存储稠密图
  • 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）

设图G的邻接矩阵为A（矩阵元素为0/1），则A^n的元素A^n[i][j]等于由顶点i到顶点j的长度为n的路径的数目。

领接表法

对图中的每个顶点 Vi 都建立一个单链表，第 i 个单链表中的结点表示依附于顶点 Vi 的边（有向图则是以顶点Vi为尾的弧），这个单链表就称为顶点的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以领接表中包括顶点表结点和边表结点。

#define MaxVertexNum 100    //图中顶点的数目的最大值
typedef char VertexType;    //顶点的数据类型
typedef int InfoType;       //边权值类型

typedef struct ArcNode {    //边表节点
    int adjVex;             //该弧所指向的顶点的位置
    struct ArcNode *next;   //指向下一条弧的指针
    InfoType info;          //网的边权值
} ArcNode;

typedef struct VNode {      //顶点表节点
    VertexType data;        //顶点信息
    ArcNode *first;         //指向第一条依附该顶点的弧的指针

} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vertices;       //邻接表
    int vexNum, arcNum;     //图的顶点数和弧数
} ALGraph;                  //以邻接表存储的图类型

  • 边结点的数量是2|E|，整体空间复杂度为O(|V| + 2|E|)。
  • 求无向图的度：遍历结点的边链表，比如图中顶点A的边链表数为3，即A的度为3。
  • 有向图的出度：遍历对应结点的边链表即可。
  • 有向图的入度：遍历所有结点的边链表，找到对应结点的入度信息。

十字链表

十字链表是有向图的一种链式存储结构。有向图中每条弧对应一个弧结点，每个顶点也对应一个顶点结点。

  • 空间复杂度：O(|V|+|E|)
  • 顺着绿色的线路找，可以找到指定顶点的出边。
  • 顺着橙色的线路找，可以找到指定顶点的入边。
  • 顶点与顶点之间是顺序存储。
  • 图的十字链表不是唯一的，但一个十字链表表示确定一个图。

邻接多重表

邻接多重表是无向图的一种存储方式。每条边对应一个边结点，每个顶点对应一个顶点结点。

  • 空间复杂度：O(|V|+|E|)
  • 寻找指定顶点的边：以B为例，通过firstedge找到AB边，由于B是绿色，沿着绿色找，找到CB边，B还是绿色，再沿着绿色找到EB边。
  • 删除边：将与边相连接的两个顶点的firstedge分别指向删除边的下一条边。如删除AB边结点，A是橙色，所以A的firstedge指向橙色ILink所指的AD边，B是绿色，B的firstedge指向绿色jLink所指的CB边。
  • 删除顶点：如删除顶点E，将顶点E和与其相连的EB边、CE边与随之删除。由于CB边结点的jLink指向了EB边结点，所以将CB边的jLink置为null，同理，将CD边结点的iLink也置为null。

基本操作

  • Adjacent(G , x , y)：判断图G是否存在边<x, y>或(x, y)

    在邻接矩阵中，比如判断是否存在CE边，只需要判断G[2][4]或G[4][2]的值是否为1即可，所以时间复杂度是O(1)。
    在邻接表中，遍历顶点C或者顶点E的边链表，即可判断出是否存在对应的边。最好的情况是边链表的第一个结点就是要找的，最坏的情况是遍历完都没有找到，由于一个顶点最多可以连接n-1个顶点，所以遍历的结点数为1(n-1)，时间复杂度就是O(1)O(|V|)。
    有向图也是如此。

  • Get_edge_value(G , x , y)：获取图G中边(x, y)或<x, y>对应的权值。与Adjacent(G , x , y)操作雷同，核心在于找到边。

  • Set_edge_value(G , x , y , v)：设置图G中边(x, y)或<x, y>对应的权值为v。与Adjacent(G , x , y)操作雷同，核心在于找到边。

  • Neighbors(G , x)：列出图G中与结点x邻接的边

    无向图邻接矩阵：遍历结点X所在的那一行或者那一列即可找到与X邻接的边；
    无向图邻接表：遍历结点X所对应的边链表，即可找到与X邻接的边。
    有向图邻接矩阵：遍历结点X所在的那一行和那一列，即可找到X的入边和出边；
    有向图邻接表：遍历结点X的边链表，即可找到X的出边，遍历所有的边链表可以找到X的入边。

  • InsertVertex(G , x)：在图G中插入顶点x

    邻接矩阵插入顶点时，在二维数组中添加一行和一列。
    邻接表插入顶点时，在顶点表中添加一个元素即可。

  • DeleteVertex(G , x)：从图G中删除顶点x

    无向图邻接矩阵：在边表中将顶点所在的行和列元素都置为0，再将顶点表中的对应元素置为null。
    无向图邻接表：将对应顶点的边链表清空，再遍历其余的边链表，将元素X删除。

  • AddEdge(G , x , y)：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边

    比如添加CF边。在邻接矩阵中，将G[2][5]和G[5][2]的值置为1；在邻接表中，在顶点C和F的边链表中，采用头插法添加对应结点。

  • RemoveEdge(G , x , y)：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。与AddEdge(G , x , y) 操作类似。

  • FirstNeighbor(G , x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1

    邻接矩阵中，遍历顶点X 对应的那一行或者那一列，找到第一个值为1的顶点。
    邻接表中，遍历顶点X对应的边链表，找到第一个链表元素。
    有向图邻接表找入边结点时，需要遍历处顶点X外所有的边链表，时间复杂度 O(1)~O(|E|)

  • NextNeighbor(G , x , y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。与FirstNeighbor(G , x) 操作类似。

6.3 图的遍历

广度优先遍历（BFS）

广度优先遍历（Breadth-First-Search，BFS）类似于二叉树的层序遍历算法。首先访问起始结点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1，w2...，然后依次访问w1，w2...的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直到图中所有顶点都被访问过为止。

#include <iostream>

using namespace std;

#define MaxVertexNum 100        //顶点的数目的最大值
typedef int VertexType;        //顶点的数据类型
typedef int EdgeType;           //带权图中边上权值的数据类型

typedef struct {
    VertexType Vex[MaxVertexNum];               //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表
    int vexNum, arcNum;                         //图的当前顶点数和弧数
} MGraph;

//求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
VertexType FirstNeighbor(MGraph graph, int x) {
    for (int j = 1; j <= graph.vexNum; ++j) {
        if (graph.Edge[x][j] == 1) {
            return j;
        }
    }
    return -1;
}

//假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
VertexType NextNeighbor(MGraph graph, int x, int y) {
    for (int j = y + 1; j <= graph.vexNum; ++j) {
        if (graph.Edge[x][j] == 1) {
            return j;
        }
    }
    return -1;
}

bool visited[MaxVertexNum]; //访问标记数组
SqQueue queue;  //辅助队列，队列相关代码省略，参考队列那一章

//从顶点编号为v的结点开始 广度优先遍历
void BFS(MGraph graph, int v) {
    EnQueue(queue, v);               //入队
    visited[v] = true;                  //将访问过的结点标记为true
    //队列元素依次出队并输出结点信息
    while (!QueueEmpty(queue)) {
        DeQueue(queue, v);            //出队
        cout << graph.Vex[v] << endl;       //输出结点信息
        //将队头结点的未被访问过的邻接结点依次入队
        for (VertexType w = FirstNeighbor(graph, v); w > 0; w = NextNeighbor(graph, v, w)) {
            if (!visited[w]) {
                EnQueue(queue, w);
                visited[w] = true;
            }
        }
    }
}

//对图graph进行广度优先遍历
void BFSTraverse(MGraph graph) {
    //初始化标记数组
    for (int i = 1; i < MaxVertexNum; ++i) {
        visited[i] = false;
    }
    InitQueue(queue);
    //遍历访问数组，将对访问的结点开始BFS，
    //非连通图以及有向图从一个顶点出发不一定能对所有的顶点都进行遍历，所以需要多次BFS
    //为了方便说明，顶点从1开始
    for (int j = 1; j <= graph.vexNum; ++j) {
        if (!visited[j]) {
            BFS(graph, j);
        }
    }
}

与二叉树的BFS类似，借助辅助队列实现。从顶点1开始，1出队时与其相邻的2、5入队；2出队时与其相邻的6入队；5出队；6出队时与其相邻的3、7入队；3出队时与其相邻的4入队；7出队时与其相邻的8入队；4出队；8出队。

从不同的顶点开始，所得到的遍历序列不同。

同⼀个图的邻接矩阵表示方式唯⼀，因此从一个顶点出发，⼴度优先遍历序列唯⼀。

同⼀个图邻接表表示方式不唯⼀，因此从一个顶点出发，⼴度优先遍历序列不唯⼀。

广度优先生成树

由于图的广度优先遍历和树的层序遍历类似，所以在基于连通图的广度优先遍历过程中，可以得到一棵遍历树，这棵树就是广度优先生成树。而基于非连通图的广度优先遍历，得到的就是广度优先遍历森林。

⼴度优先⽣成树由⼴度优先遍历过程确定。图的邻接矩阵存储表示是唯一的，所以基于邻接矩阵的广度优先生成树是唯一的。由于邻接表的表示⽅式不唯⼀，因此基于邻接表的⼴度优先⽣成树也不唯⼀。

深度优先遍历（DFS）

深度优先遍历（Depth-First-Search，DFS）类似于树的先根遍历。首先访问图中某一起始点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2...重复以上过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

#include <iostream>

using namespace std;

#define MaxVertexNum 100        //顶点的数目的最大值
typedef int VertexType;        //顶点的数据类型
typedef int EdgeType;           //带权图中边上权值的数据类型

typedef struct {
    VertexType Vex[MaxVertexNum];               //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表
    int vexNum, arcNum;                         //图的当前顶点数和弧数
} MGraph;

//求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
VertexType FirstNeighbor(MGraph graph, int x) {
    for (int j = 1; j <= graph.vexNum; ++j) {
        if (graph.Edge[x][j] == 1) {
            return j;
        }
    }
    return -1;
}

//假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
VertexType NextNeighbor(MGraph graph, int x, int y) {
    for (int j = y + 1; j <= graph.vexNum; ++j) {
        if (graph.Edge[x][j] == 1) {
            return j;
        }
    }
    return -1;
}

bool visited[MaxVertexNum]; //访问标记数组

//从顶点编号为v的结点开始 深度优先遍历
void DFS(MGraph graph, int v) {
    cout << graph.Vex[v] << endl;       //输出结点信息
    visited[v] = true;                  //将访问过的结点标记为true
    //递归调用DFS，对顶点的未被访问过的邻接结点依次进行DFS
    for (VertexType w = FirstNeighbor(graph, v); w > 0; w = NextNeighbor(graph, v, w)) {
        if (!visited[w]) {
            DFS(graph, w);
        }
    }
}

//对图graph进行深度优先遍历
void DFSTraverse(MGraph graph) {
    //初始化标记数组
    for (int i = 1; i < MaxVertexNum; ++i) {
        visited[i] = false;
    }
    //遍历访问数组，将对访问的结点开始DFS
    //非连通图以及有向图从一个顶点出发不一定能对所有的顶点都进行遍历，所以需要多次DFS
    //为了方便说明，顶点从1开始
    for (int j = 1; j <= graph.vexNum; ++j) {
        if (!visited[j]) {
            DFS(graph, j);
        }
    }
}

从顶点1开始，1邻接有2，访问2；2邻接有6，访问6；6邻接有3，访问3；3邻接有4，访问4；4邻接有7，访问7；7邻接有8，访问8；调用栈退回到1，1还邻接有未被访问过的5，访问5。得到深度优先遍历序列12634785。

深度优先生成树

与广度优先遍历一样，深度优先遍历也会产生一棵深度优先生成树。即对连通图调用 DFS 才能产生深度优先生成树，否则产生的将是深度优先生成森林，与 BFS 类似，基于邻接表存储的深度优先生成树是不唯一的。

图的遍历与图的连通性

6.4 图的应用

最小生成树

对于⼀个带权连通⽆向图G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有⽣成树的集合，若T为R中边的权值之和最小的⽣成树，则T称为G的最⼩⽣成树（Minimum-Spanning-Tree, MST）。

  • 最⼩⽣成树可能有多个，但边的权值之和总是唯⼀且最小的
  • 最⼩⽣成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路
  • 如果⼀个连通图本身就是⼀棵树，则其最⼩⽣成树就是它本身
  • 只有连通图才有⽣成树，⾮连通图只有⽣成森林

Prim算法

从某⼀个顶点开始构建生成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。

时间复杂度：O(|V|²)，适合⽤于边稠密图。

Kruskal算法

每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通。

时间复杂度：O( |E| log₂|E| )，适合⽤于边稀疏图。

最短路径问题——BFS算法（无权图）

前面提到，图的BFS和树的先根遍历类似，所以从起始顶点出发到达某一顶点的单源最短路径，可以看做是将图转换为广度优先生成树，路径长度为顶点的深度。代码实现方式就是在BFS算法的基础上加以改进。

#include <iostream>
#include <climits>

using namespace std;

/**
* 图和队列的定义及相关操作的代码省略，参考前面章节
* 顶点从1开始
**/

bool visited[MaxVertexNum]; //访问标记数组
SqQueue queue;  //辅助队列
int d[MaxVertexNum];    //起始顶点到各个顶点的路径长度
int path[MaxVertexNum]; //记录各个顶点的前驱结点

//从顶点编号为v的结点开始 广度优先遍历 求最短路径
void BFS_MIN_Distance(MGraph graph, int u) {
    EnQueue(queue, u);               //入队
    visited[u] = true;                  //将访问过的结点标记为true
    d[u] = 0;                           //起始顶点，路径为0
    //队列元素依次出队并输出结点信息
    while (!QueueEmpty(queue)) {
        DeQueue(queue, u);            //出队
        //将队头结点的未被访问过的邻接结点依次入队
        for (VertexType w = FirstNeighbor(graph, u); w > 0; w = NextNeighbor(graph, u, w)) {
            if (!visited[w]) {
                path[w] = u;        //将w的前驱结点设为u
                d[w] = d[u] + 1;    //u是w的前驱结点，将w的路径置为前驱结点的路径+1
                EnQueue(queue, w);  //出队
                visited[w] = true;      //设为已访问
            }
        }
    }
}

//对图graph进行广度优先遍历
void BFSTraverse(MGraph graph) {
    //初始化标记数组
    for (int i = 1; i < MaxVertexNum; ++i) {
        visited[i] = false;
        d[i] = INT_MAX;
        path[i] = -1;
    }
    InitQueue(queue);
    //遍历访问数组，将对访问的结点开始BFS
    for (int j = 1; j <= graph.vexNum; ++j) {
        if (!visited[j]) {
            BFS_MIN_Distance(graph, j);
        }
    }
}

添加了两个数组d和path，在访问顶点时，修改其最短路径⻓度 d[ ] 并在 path[ ]中 记录前驱结点。

最短路径问题——Dijkstra算法（带权图，无权图）

Dijkstra算法借助三个辅助数组：

  • final[]：标记各顶点是否已找到最短路径
  • dist[]：记录从起始顶点到达各顶点的最短路径长度
  • path[]：记录各顶点的前驱结点

每一轮都循环遍历所有结点，找到还没确定最短路径，且dist 最⼩的顶点Vi，令final[i]=ture。并检查所有邻接⾃ Vi 的顶点，若其 final 值为false，则更新 dist 和 path 信息。

推荐阅读