第六章：图（上）

一、基本概念

1.图G相关概念：

1
2
3
4
Graph = (Vertex, Edge)
G = (V, E)
//V:顶点（数据元素）的有穷非空集合
//E:边的有穷集合
  1. 无向图：每条边都是无方向的
  2. 有向图：每条边都是有方向的
  3. 完全图：任意两个点都有一条边相连
  4. 稀疏图：有很少边/弧的图
  5. 稠密图：有较多边/弧的图
  6. 网：边/弧带有权重的图

image-20221129104309288

2.顶点V相关概念：

  1. 邻接：边/弧相连的两个顶点之间的关系，例如：(vi, vj)称为vi和vj互为邻接点、<vi, vj>称vi邻接到vj，vj邻接于vi
  2. 关联/依附：边/弧与顶点之间的关系，例如：(vi, vj)/<vi, vj>称为该边/弧关联于vi和vj
  3. 顶点的度：与该顶点相关联的边的数目，记为TD(v)，在有向图中顶点的度等于该顶点的入度与出度之和。
  4. 顶点的入度：以v为终点的有向边的条数，记作ID(v)
  5. 顶点的出度：以v为始点的有向边的条数，记作OD(v)

3.边E相关的概念：

  1. 路径：接续的边构成的顶点序列
  2. 路径长度：路径上边/弧的数目/权值之和
  3. 回路：第一个顶点和最后一个顶点相同的路径。
  4. 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。
  5. 简单回路：除路径起点和终点相同外，其余顶点均不相同的路径。
  6. 连通：无向图中两个顶点间有路径存在，则称为连通。
  7. 强连通：有向图中两个顶点间有正向、逆向的路径，则称为强连通。
  8. 连通图：无向图中任意两个顶点之间都是连通的，则称为连通图
  9. 强连通图：有向图中任意两个顶点之间都是强连通的，则称为强连通图

==补充：有向图无向图边数问题==

  • 对于n个顶点的无向图G，若G是连通图则最少有n-1条边，若G是非连通图则最多可能有$C_{n-1}^2$条边
  • 对于n个顶点的有向图G，若G是强连通图则最少有n条边（即形成一条回路）

4.子图G相关概念：

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

  2. 强连通分量：有向图中的极大强连通子图称为强连通分量（子图必须强连通，同时保留尽可能多的边）

    image-20221130070416074

  3. 生成树：是一个连通图中，包含全部顶点的一个极小连通子图（边尽可能的少，但要保持连通）。

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

    image-20221130085552087

  4. 生成森林：是一个非连通图中，连通分量的生成树构成了非连通图的生成森林。

    image-20221130093933281

二、图的存储结构

1.数组表示法AdjacencyMatrix

顶点表是一个一维数组Vexs[n]用于存放各个顶点的信息：

邻接矩阵是一个二维数组A.arcs[n][n]用于存放各个顶点之间边的关系：
$$
A.arc[i][j]=\begin{cases}
1,~~~~~if~(Vi, Vj)∈E ~~或<Vi,Vj>∈E \
\
\
0,~~~~~else
\end{cases}
$$

（1）无向图邻接矩阵表示

image-20220609102834944

  1. 只要确定了顶点编号，图的邻接矩阵表示方式唯一
  2. 顶点i的度 = 第i行/列中1的个数
  3. 无向图的邻接矩阵是对称的
  4. 完全图的邻接矩阵中，对角元素为0其余全为1
  5. 设图G的邻接矩阵为A（矩阵元素为0/1），则An的元素$A^n[i][j]$等于由顶点i到顶点j的长度为n的路径的数目。
（2）有向图邻接矩阵表示

image-20221129113028397

  1. 有向图的邻接矩阵可能是不对称的
  2. 顶点的出度=第i行元素之和、顶点的入度=第i列元素之和
  3. 顶点的度=第i行元素之和+第i列元素之和

==补充==：由邻接矩阵表示有向图可引出，邻接矩阵表示有向网：

其中邻接矩阵重新定义为A.arcs[n][n]：
$$
A.arc[i][j]=\begin{cases}
Wij,~~~~~if(Vi, Vj)∈E ~~或<Vi,Vj>∈E \
\
\
\infty,~~~~~else(无边/弧)
\end{cases}
$$
如下图所示：

image-20220609111055234

（3）邻接矩阵建立无向网★

邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵，

1
2
3
4
5
6
7
8
9
10
#define MVNum//最大顶点数
#define MaxInt IFINITY//表示极大值无穷
typedef char VerTexType;//设置边的权值类型为整型
typedef int AcrType;//设置顶点的数据类型字符型

typedef struct {
    VerTexType vexs[MVNum];//顶点表
    AcrType arcs[MVNum][MVNum];//邻接矩阵or边表
    int vexnum, arcnum;//图的当前顶点数和边数
} AMGraph;//Adjacency Matrix Graph

采用邻接矩阵表示法创建无向网：

  1. 输入总顶点vexnum数和总边数arcnum
  2. 建立顶点表：依次输入点的信息存入顶点表中
  3. 初始化邻接矩阵，使每个权值初始化为极大值
  4. 根据图G的边的情况构造邻接矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status createUDN(AMGraph &G) {//采用邻接矩阵表示法，创建Undirected Net无向网
    //1.输入图的顶点数与边数
    cin >> G.vexnum >> G.arcnum;
    //2.输入顶点信息
    for (int i = 0; i < G.vernum; ++i) cin >> G.vex[i];
    //3.初始化邻接矩阵
    for (int i = 0; i < G.vexnum; ++i)
        for (int j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = MaxInt;//边的权值均设为最大值
    //4.构造邻接矩阵（输入边信息）
    for (int i = 0; i < G.arcnums; ++i) {
        cin >> v1 >> v2 >> w;//输入一条边所依附的顶点及边的权值
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);//确定v1和v2在G中的位置
        G.arcs[i][j] = w;//边<v1, v2>的权值置为w
        G.arcs[j][i] = G.arcs[i][j];//对称边<v2, v1>的权值置为w
    }
    return OK;
}

image-20220609114146677

（4）邻接矩阵表示法分析：
优点
直观、简单、易于理解
便于检查任意一对顶点之间是否存在联系（边）
便于找到任意顶点的所有邻接点（有联系的点）
便于计算任意顶点的度：从该点出发的边数为出度、指向该点的边数为入度
缺点
不利于增加和删除顶点
浪费空间—存储稀疏图，点很多而边很少有大量无效元素
浪费时间—统计稀疏图中一共有多少条边

2.链式表示法AdjacencyList

建立一个顶点表记录各个顶点的信息 和一个线性链表记录关联着同一顶点的边的信息

image-20221129125459135

（1）无向图邻接表表示

image-20220609120726654

  1. 邻接表不是唯一的，链表结点的顺序是可调换的。
  2. 无向图中顶点vi的度即为第i个单链表中的节点数。
  3. 若无向图中有n个顶点与e条边，则邻接表需要n个头结点与2e个表结点来存储（更适合稀疏矩阵的存储）
（2）有向图邻接表表示

image-20220609121444700

  1. 有向图中顶点Vi的出度即为第i个单链表中的结点数。
  2. 有向图中顶点Vi的入度即为整个单链表中的邻接点域值为i-1的结点数（困难）。
（3）邻接表建立无向图★

邻接表的存储表示：

image-20221129130505524

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MVNum 100//最大顶点数
//顶点的结构定义
typedef struct VNode {
    VerTexTyped data;//顶点信息
    ArcNode *firstarc;//指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNum];//AdjList表示邻接表类型，即AdjList v;相当于VNode v[MVNum];

//边的结构定义
typedef struct ArcNode {
    int adjvex;//该边所指向的顶点的位置
    struct ArcNode *nextarc;//指向下一条边的指针
    OtherInfo info;//与边相关的信息
} ArcNode;

//图的结构定义
typedef struct {
    AdjList vertices;//vertexs
    int vexnum, arcnum;//图的当前顶点数和边数
} ALGraph;

采用邻接表表示法创建无向图：

  1. 输入总顶点vexnum数和总边数arcnum

  2. 建立顶点表：依次输入点的信息存入顶点表中，并且使每个表头结点的指针域初始化为NULL

  3. 根据图G的边的情况构造邻接表（单链表）：

    依次输入每条边依附的两个顶点，查找两个顶点的序号i和j建立边结点

    将此边结点分别插入到vi和vj对应的两个边链表的头部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Status createUDG(ALGraph &G) {//采用邻接表表示法，创建Undirected Graph无向网
    //1.输入图的顶点数与边数
    cin >> G.vexnum >> G.arcnum;
    //2.输入表头顶点信息 构造表头结点
    for (int i = 0; i < G.vernum; ++i) {
        cin >> G.vertices[i].data;//输入顶点值
        G.vertices[i].firstarc = NULL;//初始化表头结点的指针域
    }
    //3.输入边结点信息 构造邻接表
    for (int i = 0; i < G.arcnums; ++i) {
        cin >> v1 >> v2;//输入一条边所依附的两个顶点
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);//确定v1和v2在G中的位置
        
        //(1)生成一个新的边结点*p1
        p1 = new ArcNode;
        p1->adjvex = j;//邻接点序号为j
        p1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1;//将新结点*p1插入顶点Vi的边表头部
        
        //(2)生成一个新的对称边结点*p2
        p2 = new ArcNode;
        p2->adjvex = i;//邻接点序号为i
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;//将新结点*p2插入顶点Vj的边表头部
    }
    return OK;
}
（4）邻接表表示法分析：
优点
节约稀疏图的空间：需要N个头指针+2E个结点（每个结点至少2个域）
便于找到任意顶点的所有邻接点（有联系的点）
便于计算任意顶点的度：对于无向图方便，对于有向图只能计算出度，入度需要逆邻接表来计算
缺点
不便于检查任意一对顶点之间是否存在联系（边）

==邻接矩阵与邻接表之间的对比==：

联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点的个数等于矩阵行中非零元素的个数。

对比 邻接矩阵 邻接表
复杂度 邻接矩阵的空间复杂度为O（n2） 邻接表的空间复杂度为O（n+e）顶点数+边数
应用性 邻接矩阵多用于稠密图 邻接表多用于稀疏图
表示方式 邻接矩阵是唯一的（行列号与顶点编号一致） 邻接表不是唯一的（链表次序与顶点编号无关）对于任意无向图
邻边查找 邻接矩阵必须遍历对应的行/列 邻接表找有向图入边不方便（其余很方便）

3.链式表示法的改进：

image-20220610133350668

邻接表缺点 方案 具体
有向图时度计算困难（邻接表便于求出度、逆邻接表便于求入度） 十字链表 邻接表和逆邻接表结合形成的链表。
存储无向图时每条边重复存储的问题 邻接多重表 删除边、删除结点等操作十分的方便
（1）十字链表：

十字链表Orthogonal List，

  1. 是只能用于存储有向图的一种链式存储结构，
  2. 为了解决有向图度计算困难问题，将有向图的邻接表和逆邻接表结合起来形成的链表。
  3. 有向图中的弧对应十字链表中的弧结点，有向图中的顶点在十字链表中有对应的顶点结点。

image-20221201083212734

==案例演示==：根据如下有向图建立十字链表。

image-20220610140800222

image-20220610141020464

image-20220610141030988

十字链表建立完毕

（2）邻接多重表：

邻接多重表，

  1. 是只能用于存储无向图的一种链式存储结构，
  2. 为了解决邻接表存储无向图时每条边重复存储的问题而提出的。
  3. 删除边、删除结点等操作十分的方便

image-20221201090033627

==案例演示==：根据如下无向图建立邻接多重表：

image-20220610172039776

image-20220610173331143

image-20220610173341423

image-20220610173350462

image-20221201091650171

三、图的遍历

注：遍历的实质就是找到每一个顶点的邻接点的过程（需要设置visit数组避免重复访问结点的问题）

1.广度优先搜索BFS

（1）BFS思想：

注：连通图的广度优先遍历类似于树的层次遍历，需要一个辅助队列。

  1. 从图中某结点出发，首先依次访问该结点的所有相邻邻接结点vi1、vi2、…vin（同一层）
  2. 再按照这些顶点被访问的先后次序，依次访问与它们相邻的所有未被访问的顶点
  3. 重复此过程，直到所有顶点均被访问为止

image-20220611102814351

==BFS具体过程如下==：

image-20220611104125870

image-20221201104427135

image-20221201104546092

image-20221201104842078

image-20221201105009924

image-20221201105321891

image-20221201105330345

image-20221201105442729

image-20221201105523979

（2）BFS的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool visited[MAX_VERTEX_NUM];//访问标记数组（初始值都为false）

void BFSTraverse(Graph G) {//对图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
            BFS(G, i);//Vi未访问过则从vi开始BFS
        }
    }
}

void BFS(Graph G, int v) {//从顶点v出发 广度优先遍历图G
    visit(v);//访问初始顶点v
    visited[v] = TRUE;//对v做已标记访问
    InitQueue(Q);//辅助队列Q初始化 置空
    EnQueue(Q, v);//v入队列Q
    while (!isEmpty(Q)) {
        DeQueue(Q, u);//队头元素出队
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {
            //w为u的尚未访问的邻接顶点
            if (!visited[w]) {
                visit(w);
                visited[w] = TRUE;
                EnQueue(Q, W);
            }
        }
    }
}
（3）算法分析：
  • 用邻接矩阵来表示图，BFS对于每一个被访问到的顶点，都要循环检测矩阵中的完整一行（n个元素），时间复杂度为O（n2）
  • 用邻接表来表示图，虽然有2e个表结点但是只需扫描e个结点即可，加上访问n个头结点的时间，时间复杂度为O（n + e）
  • 同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一
  • 同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一

2.深度优先搜索DFS

（1）DFS思想：

注：连通图的深度优先遍历类似于树的先根遍历，需要一个辅助栈。

  1. 在访问图中起始顶点v之后，由顶点v出发访问它的任一邻接顶点v1

  2. 在访问图中邻接顶点v1之后，由顶点v1出发访问它的任一邻接但是还没有被访问过的顶点v2

  3. 在访问图中邻接顶点v2之后，进行类似的访问v3、v4、v5…直到所有的邻接顶点都被访问过为止

  4. 当在某顶点时其所有邻接顶点都被访问过，退到上一个访问过的顶点检测其是否还有没有被访问过的邻接顶点（回溯）

    如果有则对该未访问顶点进行访问，再从该顶点出发，进行类似的访问v3、v4、v5…直到所有的邻接顶点都被访问过为止

    如果没有则再退到上一个访问过的顶点检测其是否还有没有被访问过的邻接顶点（继续回溯）

  5. 重复上述过程，直到连通图中的所有顶点都被访问过为止。

image-20220611100033459

（2）DFS的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool visited[MAX_VERTEX_NUM];

void DFSTraverse(Graph G) {//对图G进行深度优先遍历
    for (int i = 0; i < G.vexnum; ++i) visited[i] = FALSE;//初始标记化数组
    for (int i = 0; i < G,vexnum; ++i) {//从v = 0开始遍历
        if (!visited[i]) {
            DFS(G, v);
        }
    }
}

void DFS(Graph G, int v) {//从顶点v出发 深度优先遍历图G
    visit(v);//访问顶点v
    visited[v] = TRUE;
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w]) {//w为u的尚未访问的邻接结点
            DFS(G, w);
        }
    }
}
  1. 如果图的存储结构确定（此处邻接矩阵结构确定）时，则DFS遍历的顺序只有一种
  2. 回溯的过程即为if不执行的情况，无需书写！
（3）算法分析：
  • 用邻接矩阵来表示图，遍历图中的每一个顶点都要从头扫描该顶点所在的行，时间复杂度为O（n2）
  • 用邻接表来表示图，虽然有2e个表结点但是只需扫描e个结点即可，加上访问n个头结点的时间，时间复杂度为O（n + e）

==DFS与BFS算法效率比较==：

  1. 空间复杂度相同O（n）：DFS借用了栈，而BFS借用了队列
  2. 时间复杂度只与存储结构有关，而与搜索的路径无关DFS/BFS