简单解释一下，对于矩阵的主对角线的值 adj[0][0]、adj[1][1]、adj[2][2]、adj[3][3] 全为 0，因为这个图中，不存在顶点自己到自己的边，adj[0][1]=1 是因为 A 到 B 的边存在，而 adj[2][0]=0 是是因为 C 到 A 的边不存在。对于无向图而言，

它的邻接矩阵是一个对称矩阵。有了这个矩阵,我们就可以很容易地知道图中的信息。

1）我们要判定任意两顶点之间是否有边就非常容易。

2）我们要知道某个顶点的度，其实就是这个顶点在邻接矩阵中 i 行的元素之和。

3）求顶点 i 的所有邻接点就是将矩阵中第 i 行元素扫描一遍，arc[i][j] 为 1 就是邻接点。

3.带权图的邻接矩阵

在带权图的邻接矩阵中，每个矩阵元素表示一个有向边的权值。如果不存在从一个节点到另一个节点的边，则通常将其表示为特殊的值，如0，-1或无穷。

假设有一个有向带权图，它有4个顶点（A, B, C, D），边及其权重如下：

• 边 A->B 的权重是3

• 边 A->C 的权重是7

• 边 B->A 的权重是4

• 边 B->D 的权重是1

• 边 C->D 的权重是2

• 边 D->A 的权重是1

我们可以将这个有向带权图表示为以下的邻接矩阵：

在这个矩阵中，行表示起始顶点，列表示目标顶点。矩阵元素的值代表起始顶点到目标顶点的边的权重。如果没有边存在，我们用0来表示。例如，第一行表示从A到各点的边的权重，可以看出有从A到B的边，权重为3，有从A到C的边，权重为7，没有从A出发到达D的边，所以为0。

当然，什么情况下不能用0来代表边不存在的情况？

大多数情况下边权是正值，但个别时候真的有可能就是0，甚至有可能是负值。因此必须要用一个不可能的值来代表不存在。

4.邻接矩阵的优点

1）简单直观：邻接矩阵是一个二维顺序表，通过矩阵中的元素值可以直接表示顶点之间的连接关系，非常直观和易于理解。

2）存储效率高：对于小型图，邻接矩阵的存储效率较高，因为它可以一次性存储所有顶点之间的连接关系，不需要额外的空间来存储边的信息。

3）算法实现简单：许多图算法可以通过邻接矩阵进行简单而高效的实现，例如遍历图、检测连通性等。

5.邻接矩阵的缺点

1）空间复杂度高：对于大型图，邻接矩阵的空间复杂度较高，因为它需要存储一个 n × n 的矩阵，这可能导致存储空间的浪费和效率问题。

2）不适合稀疏图：邻接矩阵对于稀疏图（即图中大部分顶点之间没有连接）的表示效率较低，因为它会浪费大量的存储空间来存储零元素。

6.邻接矩阵存储结构定义


//c++代码定义
#include <iostream>
#include <vector>
 
using namespace std;
 
class Graph {
private:
    int n; // 顶点数
    vector<vector<int>> adj_matrix; // 邻接矩阵
 
public:
    // 构造函数
    Graph(int n) {
        this->n = n;
        adj_matrix.resize(n, vector<int>(n, 0)); // 初始化邻接矩阵为全 0
    }
 
    // 添加边
    void addEdge(int u, int v) {
        adj_matrix[u][v] = 1; // 设置 u 到 v 的边权为 1
    }
 
    // 打印邻接矩阵
    void printAdjMatrix() {
        cout << "Adjacency Matrix:" << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << adj_matrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

邻接表和链式前向星

邻接表（指针或数组下标）和链式前向星（容器模拟）的思路一样，只是表达方式不同。

1.邻接表的概念

邻接表是一种表示图的数据结构。邻接表的主要概念是：对于图中的每个顶点，维护一个由与其相邻的顶点组成的列表。这个列表可以用数组、链表或其他数据结构来实现。实际上，邻接表可以用于有向图、无向图、带权图、无权图。这里只考虑无权图的情况，带权图只需要多存储一个数据就可以了。

2.邻接表的顺序表存储

在C语言的静态数组中，如果要实现邻接表，一般图中的点的数量控制在1000 左右的量级，是比较合适的，如果在大一点，存储会产生问题。

在C++中，有 vector 这种柔性数组，所以可以支持百万的量级。当然，也可以用C语言的静态数组来模拟实现一个 C++中的柔性数组。

这里不讨论柔性数组的情况，只考虑 1000 量级的情况，如下：


#define maxn 1010
int adjSize[maxn];
int adj[maxn][maxn];

其中 adjSize[i] 代表从 i 出发，能够直接到达的点的数量；

而 adj[i][j] 代表从 i 出发，能够到达的第 j 个顶点；

在一个 n 个顶点的图上，由于任何一个顶点最多都有 n-1 个顶点相连，所以在C语言中，定义时必然要定义成二维数组，空间复杂度就是 O(n^2)，对于一个稀疏图来说，数组实现，浪费空间严重，建议采用链表实现。

3.邻接表的链表存储

用链表来实现邻接表，实际上就是对于每个顶点，它能够到达的顶点，都被存储在以它为头结点的链表上。

对于如上的图，存储的就是四个链表：

这就是用链表表示的邻接表。注意：这里实际上每个链表的头结点是存储在一个顺序表中的，所以严格意义上来说是顺序表 + 链表的实现。

4.邻接表的应用

邻接表一般应用在图的遍历算法，比如深度优先搜索、广度优先搜索。更加具体的，应用在最短路上，比如 Dijkstra、Bellman-Ford、SPFA；以及最小生成树，比如 Kruskal、Prim；还有拓扑排序、强连通分量、网络流、二分图最大匹配等等问题。

5.邻接表的优点

邻接表表示法的优点主要有空间效率、遍历效率。

1）空间利用率高：邻接表通常比邻接矩阵更节省空间，尤其是对于稀疏图。因为邻接表仅需要存储实际存在的边，而邻接矩阵需要存储所有的边。

2）遍历速度：邻接表表示法在遍历与某个顶点相邻的所有顶点时，时间复杂度与顶点的度成正比。对于稀疏图，这比邻接矩阵表示法的时间复杂度要低。

6.邻接表的缺点

1）不适合存储稠密图：对于稠密图（即图中边的数量接近于 n^2），导致每个顶点的边列表过长，从而降低存储和访问效率。

2）代码复杂：相比于邻接矩阵，实现代码会更加复杂一些。

7.邻接表存储结构定义


//c++代码定义
#include <iostream>
#include <vector>
#include <list>
 
using namespace std;
 
class Graph {
private:
    int n; // 顶点数
    vector<list<int>> adj_list; // 邻接表
 
public:
    // 构造函数
    Graph(int n) {
        this->n = n;
        adj_list.resize(n); // 初始化邻接表
    }
 
    // 添加边
    void addEdge(int u, int v) {
        adj_list[u].push_back(v); // 将顶点 v 添加到顶点 u 的邻接表中
    }
 
    // 打印邻接表
    void printAdjList() {
        cout << "Adjacency List:" << endl;
        for (int i = 0; i < n; i++) {
            cout << i << ": ";
            for (int neighbor : adj_list[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

十字链表

十字链表是有向图的一种链式存储结构。在十字链表中，有向图的每条狐用一个节点（弧节点）来表示，每个顶点也用一个节点（顶点节点）来表示。两种节点的结构存储如下

有向图的十字链表表示：

十字链表存储结构定义


//c++代码定义
#include <iostream>
#include <vector>
 
using namespace std;
 
// 十字链表节点结构
struct Node {
    int row, col;  // 节点在矩阵中的行和列
    int value;     // 节点的值
    Node* left;    // 左指针
    Node* right;   // 右指针
    Node* up;      // 上指针
    Node* down;    // 下指针
};
 
// 十字链表类
class SparseMatrix {
private:
    vector<Node*> rowHead;  // 行头节点数组
    vector<Node*> colHead;  // 列头节点数组
    int rows, cols;         // 矩阵的行数和列数
 
public:
    // 构造函数
    SparseMatrix(int r, int c) {
        rows = r;
        cols = c;
        rowHead.resize(r, nullptr);
        colHead.resize(c, nullptr);
    }
 
    // 插入元素
    void insert(int row, int col, int value) {
        Node* newNode = new Node{row, col, value, nullptr, nullptr, nullptr, nullptr};
 
        // 插入行链表
        if (rowHead[row] == nullptr || rowHead[row]->col > col) {
            newNode->right = rowHead[row];
            rowHead[row] = newNode;
        } else {
            Node* temp = rowHead[row];
            while (temp->right != nullptr && temp->right->col < col) {
                temp = temp->right;
            }
            newNode->right = temp->right;
            temp->right = newNode;
        }
 
        // 插入列链表
        if (colHead[col] == nullptr || colHead[col]->row > row) {
            newNode->down = colHead[col];
            colHead[col] = newNode;
        } else {
            Node* temp = colHead[col];
            while (temp->down != nullptr && temp->down->row < row) {
                temp = temp->down;
            }
            newNode->down = temp->down;
            temp->down = newNode;
        }
    }
 
    // 访问元素
    int get(int row, int col) {
        Node* temp = rowHead[row];
        while (temp != nullptr && temp->col <= col) {
            if (temp->col == col) {
                return temp->value;
            }
            temp = temp->right;
        }
        return 0;
    }
};

邻接多重表

邻接多重表是无向图的一种链式存储结构。在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下所示。

其中，ivex和jvex这两个域指示该边依附的两个顶点的编号:iink域指向下一条依附于顶点ivex的边；jlink域指向下一条依附于顶点jvex的边，info域存放该边的相关信息。
每个顶点也用一个结点表示，它由如下所示的两个域组成。

其中， data域存放该顶点的相关信息，firstedae 域指向第一条依附于该顶点的边。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，因为每条边依附于两个顶点，所以每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

无向图的邻接多重表表示：

邻接多重表存储结构定义


//c++代码定义
#include <iostream>
#include <vector>
#include <list>
 
using namespace std;
 
// 边的结构体
struct Edge {
    int dest; // 目标顶点
    int weight; // 边的权重
};
 
// 顶点的结构体
struct Vertex {
    int data; // 顶点数据
    list<Edge> adj_list; // 邻接表
};
 
// 图的类
class Graph {
private:
    int num_vertices; // 顶点数
    vector<Vertex> vertices; // 顶点数组
 
public:
    // 构造函数
    Graph(int n) {
        num_vertices = n;
        vertices.resize(n);
        for (int i = 0; i < n; i++) {
            vertices[i].data = i;
        }
    }
 
    // 添加边
    void add_edge(int src, int dest, int weight) {
        Edge e = {dest, weight};
        vertices[src].adj_list.push_back(e);
    }
 
    // 打印图
    void print_graph() {
        for (int i = 0; i < num_vertices; i++) {
            cout << "Vertex " << vertices[i].data << ": ";
            for (auto it = vertices[i].adj_list.begin(); it != vertices[i].adj_list.end(); ++it) {
                cout << "(" << it->dest << ", " << it->weight << ") ";
            }
            cout << endl;
        }
    }
};

图的四种存储方式的总结

图的遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次，且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

图的遍历比树的遍历要复杂得多，因为图的任意一个顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组visite[ ]来标记顶点是否被访问过。图的遍历算法主要有两种:广度优先搜索和深度优先搜索。

深度优先搜索（DFS）

1）算法原理

深度优先搜索（Depth First Search），是图遍历算法的一种。用一句话概括就是：“一直往下走，走不通回头，换条路再走，直到无路可走”。具体算法描述为：

选择一个起始点 u 作为当前结点，执行如下操作：

a. 访问当前结点，并且标记该结点已被访问，然后跳转到 b；

b. 如果存在一个和当前结点相邻并且尚未被访问的结点 v，则将 v 设为当前结点，继续执行 a；

c. 如果不存在这样的 v，则进行回溯，回溯的过程就是回退当前结点；

上述所说的当前结点需要用一个栈来维护，每次访问到的结点入栈，回溯的时候出栈。

2）算法实现

【例题】给定一个 n 个结点的无向图，要求从 0 号结点出发遍历整个图，求输出整个过程的遍历序列。其中，遍历规则为：

1）如果和当前结点相邻的结点已经访问过，则不能再访问；

2）每次从和当前结点相邻的结点中寻找一个编号最小的没有访问的结点进行访问；

对上图以深度优先的方式进行遍历，起点是 0；

第一步，当前结点为 0，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 1；

第二步，当前结点为 1，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 3；

第三步，当前结点为 3，标记已访问，没有尚未访问的相邻结点，执行回溯，回到结点 1；

第四步，当前结点为 1，从相邻结点中找到编号最小的且没有访问的结点 4；

第五步，当前结点为 4，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 5；

第六步，当前结点为 5，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 2；

第七步，当前结点为 2，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 6；

第八步，当前结点为 6，标记已访问，没有尚未访问的相邻结点，执行回溯，回到结点 2；

第九步，按照 2 => 5 => 4 => 1 => 0 的顺序一路回溯，搜索结束；

如图所示，红色实箭头表示搜索路径，蓝色虚箭头表示回溯路径。

上图中，红色块表示往下搜索，蓝色块表示往上回溯，遍历序列为：

0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6

3）代码


const int MAXN = 7;
void dfs(int u) {
    if(visit[u]) { // 1
        return ;
    }
visit[u] = true; // 2
dfs_add(u); // 3
for(int i = 0; i < MAXN; ++i) {
    int v = i;
    if(adj[u][v]) { // 4
        dfs(v); // 5
    }
}

1、visit[MAXN] 数组是一个bool数组，用于标记某个节点是否已访问，初始化都为 false；这里对已访问结点执行回溯；

2、visit[u] = true; 对未访问结点 u 标记为已访问状态；

3、dfs_add(u); 用来将 u 存储到的访问序列中，实际函数实现如下：


void dfs_add(int u) {
    ans[ansSize++] = u;
}

4、adj[MAXN][MAXN] 是图的邻接矩阵，用 0 或 1 来代表点是否连通，对于上面的例子，邻接矩阵表示如下：


bool adj[MAXN][MAXN] = {
 {0, 1, 1, 0, 0, 0, 0},
 {1, 0, 0, 1, 1, 0, 0},
 {1, 0, 0, 0, 0, 1, 1},
 {0, 1, 0, 0, 0, 0, 0},
 {0, 1, 0, 0, 0, 1, 0},
 {0, 0, 1, 0, 1, 0, 0},
 {0, 0, 1, 0, 0, 0, 0},
};

（ adj[u][v] = 1 代表 u 和 v 之间有一条有向边；adj[u][v] = 0 代表没有边）

5、递归调用相邻结点

4）算法性能分析

DFS算法是一个递归算法，需要借助一个递归工作栈，所以其空间复杂度为o(|V|)。

遍历图的过程实质上是通过边查找邻接点的过程，因此两种遍历方式的时间复杂度都相同，不同之处仅在于对顶点访问顺序的不同。采用邻接矩阵存储时，总时间复杂度为O(|V|^2)。采用邻接表存储时，总的时间复杂度为O(|V|+|E|)。

5）深度优先的生成树和生成森林

对连通图调用DFS才能产生深度优先生成树，否则产生的将是深度优先生成森林

广度优先搜索（BFS）

1）算法原理

广度优先搜索(Breadth-First Search, BFS)算法是一种遍历图的方法，它从起点开始，先访问所有相邻的顶点,然后再访问这些顶点的相邻顶点,直到所有可达的顶点都被访问到。用一句话概括就是“一层又一层，泛起层层涟漪”。具体算法描述如下：

选择一个起始顶点作为根节点。
将根节点加入到一个队列中。
从队列中取出一个顶点,访问该顶点。
将该顶点的所有未访问过的相邻顶点加入到队列中。
重复步骤 3 和 4,直到队列为空。

2）算法实现

【例题】给定一无向图G如图，要求从结点a 开始，采用BFS算法遍历整个图。

对于上图采用广度优先搜索：

第一步，a先入队。

第二步，此时队列非空，取出队头元素a，因为b，c与a邻接且未被访问过，于是依次访问b， c,并将b， c依次入队。

第三步，队列非空，取出队头元素b，依次访问与b邻接且未被访问的顶点d， e,并将d，e入队(注意:a与b也邻接，但a已置访问标记，所以不再重复访问)。

第四步，此时队列非空，取出队头元素c，访问与c邻接且未被访问的顶点f,g,并将f，g 入队。

第五步，此时，取出队头元素d，但与d邻接且未被访问的顶点为空，所以不进行任何操作。继续取出队头元素e，将h入队列。

最终取出队头元素h后，队列为空，从而循环自动跳出。最终得到的遍历序列：

a -> b -> c -> d -> e -> f ->g -> h

3）代码


void bfs(char start) {
    // 创建一个队列和一个访问标记数组
    queue<char> q;
    vector<bool> visited(graph.size(), false);
 
    // 将起始顶点入队并标记为已访问
    q.push(start);
    visited[start - 'a'] = true;
 
    // 执行 BFS 遍历
    while (!q.empty()) {
        char u = q.front(); //取出队头
        q.pop();
        cout << u << " ";
 
        // 将 u 的所有未访问过的相邻顶点入队并标记为已访问
        for (char v : graph[u - 'a']) {
            if (!visited[v - 'a']) {
                q.push(v);
                visited[v - 'a'] = true;
            }
        }
    }
}

其中邻接表graph存储图：


// 图的邻接表表示
vector<vector<char>> graph = {
    {'b', 'c'},         // 顶点 a 的邻接顶点
    {'a', 'd', 'e'},  // 顶点 b 的邻接顶点
    {'a', 'f', 'g'},  // 顶点 c 的邻接顶点
    {'b'},            // 顶点 d 的邻接顶点
    {'b','h'},        // 顶点 e 的邻接顶点
    {'c'},            // 顶点 f 的邻接顶点
    {'c'},            // 顶点 g 的邻接顶点
    {'e'}             // 顶点 h 的邻接顶点
};

从上例不难看出，图的广度优先搜索的过程与二叉树的层序遍历是完全一致的，这也说明了图的广度优先搜索遍历算法是二叉树的层次遍历算法的扩展。

4）算法性能分析

无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q， n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(|V|)。

遍历图的过程实质上是对每个顶点查找其邻接点的过程，耗费的时间取决于所采用的存储结构。采用邻接表存储时，每个顶点均需搜索(或入队)一次，时间复杂度为O(|V|)，在搜索每个顶点的邻接点时，每条边至少访问一次，时间复杂度为O(|E|),总的时间复杂度为O(|V|+|E|)。采用邻接矩阵存储时，查找每个顶点的邻接点所需的时间为O(|V|)，总时间复杂度为O(|V|^2)。

5）BFS算法求解单源最短路径问题

若图G=(V, E)为非带权图，定义从顶点u到顶点v的最短路径d(u,v)为从u到v的任何路径中最少的边数；若从u到v没有通路，则d(u, v)=∞。
使用BFS，我们可以求解一个满足上述定义的非带权图的单源最短路径问题，这是由广优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。

【例题】

解题思路：

用bfs算法更新起点到其他结点的距离，如果边界条件满足，令当前顶点step + 1 并入队，继续遍历其他顶点，当找到终点时，返回其距离就是我们找的最短路径。

AC代码：


#include <iostream>
#include <queue>
using namespace std;
 
const int N = 105;
char mp[N][N];   //定义邻接矩阵
bool vis[N][N];  //定义标记数组
int n, m, x2, y2, ans = -1;
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} }; //上下左右四个方向
 
//定义位置及起点到该点的步数
struct node {
    int x, y;  
    int step;
};
queue<node> qe;
//判断是否超出地图
bool in(int x, int y) { 
    return x > 0 && x <= n && y > 0 && y <= m;
}
void bfs(int x1, int y1) {
    //起点入队
    qe.push({ x1,y1,0 });
    vis[x1][y1] = true;
 
    while (!qe.empty()) {
        //队头出队
        node t = qe.front();
        qe.pop();
        //若找到终点，将step赋给答案
        if (t.x == x2 && t.y == y2) {  
            ans = t.step;
            return;
        }
        //遍历四个方向
        for (int i = 0; i < 4; ++i) {
            int tx = t.x + dir[i][0];
            int ty = t.y + dir[i][1];
            if (in(tx, ty) && !vis[tx][ty] && mp[tx][ty] == '1') {
                vis[tx][ty] = true;
                qe.push({ tx,ty,t.step + 1 });
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> mp[i][j];
        }
    }
    int x1, y1;
    cin >> x1 >> y1 >> x2 >> y2;
    bfs(x1, y1);
    cout << ans;
    return 0;
}

【例题】 2368. 受限条件下可到达节点的数目 - 力扣（LeetCode）

题目描述

解题思路：

先用哈希表标记受限制的顶点，建图时，只需要建立未标记的顶点连接的图，然后用BFS从0开始扫一遍，将能访问的顶点计数器加一，最后就是0能访问不受限制的结点。

AC代码：


class Solution {
public:
    int bfs(vector<vector<int>> &G, vector<bool> &vis) {
        int ans = 0;
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            ++ans;
            vis[u] = true;
            for (auto v : G[u]) {
                if (!vis[v]) {
                    q.push(v);
                }
            }
        }
        return ans;
    }
 
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        unordered_set<int> op(restricted.begin(), restricted.end()); // 使用集合加快查找效率
 
        // 建图
        vector<vector<int>> G(n);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            // 确保这条边的两个端点都不在限制列表中
            if (op.find(u) == op.end() && op.find(v) == op.end()) {
                G[u].push_back(v);
                G[v].push_back(u);
            }
        }
 
        vector<bool> vis(n, false);
        int ans = bfs(G, vis);
 
        return ans;
    }
};

6）广度优先生成树

在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树。需要注意的是，同一个图的邻接矩阵存储表示是唯一的，所以其广度优先生成树也是唯一的，但因为邻接表存储表示不唯一，所以其广度优先生成树也是不唯一的。

以上是图的基本内容，接下来才到本文的硬核

图的应用

最小生成树

定义

在无向图中，连通而且不含有圈（环路）的图，称为树。最小生成树 MST：一个有 n 个结点的连通图的生成树是原图的极小连通子图，包含原图中的所有 n 个结点，并且边的权值之和最小。

Prim算法

对点进行贪心操作：“最近的邻居一定在 MST 上”。从任意一个点 u 开始，把距离它最近的点 v 加入到 MST 中；下一步，把距离 {u, v} 最近的点 w 加入到 MST 中；继续这个过程，直到所有点都在 MST 中。

Prim算法的具体步骤如下：

假设G = {V，E}是连通图，其最小生成树T={U，Et}，Et是最小生成树中边的集合。

初始化：向空树T=(U，Et)中添加图G = (V，E)的任意一个顶点u0,使U={u0}，E{T}=Ø。

循环(重复下列操作直至U = V)：从图G中选择满足{(u，v) | u∈U, v∈V-U}且具有最小权值的边(u, v),加入树T，置U = U ∪ {v} ， Et=Et ∪ {(u， v)}。

代码：


#include <iostream>
#include <vector>
using namespace std;
 
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
vector<int> demo;
int visited[MAXN], lowcost[MAXN], m, n;//m为节点的个数，n为边的数量
int G[MAXN][MAXN];//邻接矩阵
 
int prim(){
    for (int i = 0; i < m; i++)
        lowcost[i] = INF;
    
    for (int i = 0; i < m; i++)
        visited[i] = 0;
    
    visited[0] = -1;              //加入第一个点，-1表示该点在集合U中，否则在集合V中
    int num = 0, ans = 0, v = 0;  //v为最新加入集合的点
    while (num < m - 1){          //加入m-1条边
        int mincost = INF, minvertex = -1;
        for (int i = 0; i < m; i++)
            if (visited[i] != -1){
                int temp = G[v][i];
                if (temp < lowcost[i]){
                    lowcost[i] = temp;
                    visited[i] = v;
                }
                if (lowcost[i] < mincost)
                    mincost = lowcost[minvertex = i]; 
            }
        ans += mincost;
        demo.push_back(mincost);
        visited[v = minvertex] = -1;   //标记已加入顶点
        num++;
    }
    return ans;
}
 
int main(){
 
    scanf("%d %d", &m, &n);
    memset(G, INF, sizeof(G));
    for (int i = 0; i < n; ++i){
        int a, b, c;             //a为起点，b终点，c权值
        cin >> a >> b >> c;
 
        G[b][a] = G[a][b] = c;
 
    }
 
    cout << prim() << endl;
    for (int i = 0; i < m - 1; i++) cout << demo[i] << " ";
    return 0;
}

Prim算法的时间复杂度为O(|V|^2)，不依赖于|E|，因此它适用于稠密图。

kruskal 算法

对边进行贪心操作：“最短的边一定在 MST 上”。从最短的边开始，把它加入到 MST 中；在剩下的边中找最短的边，加入到 MST 中；继续这个过程，直到所有点都在 MST 中。

Kruskal算法的具体步骤如下：

kruskal 算法的 2 个关键技术：（1）对边进行排序。（2）判断圈，即处理连通性问题。这个问题用并查集简单而高效，并查集是 kruskal 算法的实现基础。

初始时最小生成树 MST 为空。开始的时候，每个点属于独立的集。

按边长从小到大进行边的遍历操作：

尝试将最小边加入最小生成树：

如果边的两个端点属于同一个集合，就说明这两个点已经被加入最小生成树。则不能将边加入，否则就会生成一个环。
如果两个端点不属于同一个集合，就说明该点还未纳入最小生成树，此边可以加入。

重复上述操作，直到加入 n-1 条边。

代码：


#include <iostream>
#include <algorithm>
using namespace std;
 
const int maxn = 11000000;
int n, m;
int pre[maxn];
 
struct edge {
    int x;
    int y;
    int k;
} Q[maxn];
 
int find(int x) {
    if (pre[x] == x)
        return x;
    return pre[x] = find(pre[x]);  //路径压缩
}
bool cmp(edge a, edge b) {   //按权值排序
    return a.k < b.k;
}
int main() {
    scanf("%d %d", &n, &m);
 
    int cont = 0, sum = 0, num = 0;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &Q[i].x, &Q[i].y, &Q[i].k);
        cont += Q[i].k;
    }
    sort(Q, Q + m, cmp);
    for (int i = 1; i <= n; i++)  //初始化并查集
        pre[i] = i;
    for (int i = 0; i < m; i++) {
        int rx = find(Q[i].x);
        int ry = find(Q[i].y);
        if (rx != ry) {          //判环
            sum += Q[i].k;
            pre[rx] = ry;
            num++;
 
            if (num == n - 1)  //边数等于n-1时结束循环，此时已经构成最小生成树
                break;
        }
    }
    printf("%d\n", sum);
    return 0;
}

kruskal 算法的复杂度包括两部分：对边的排序 O(ElogE)，并查集的操作 O(E)，一共是 O(ElogE + E)，约等于 O(ElogE)，时间主要花在排序上。如果图的边很多，kruskal 的复杂度要差一些。kruskal 适用于稀疏图。

例题

解题思路：

AC代码：


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 100001;
int a[N], x[N], y[N], pre[N];
int n, m;
 
struct edge {
	int u;
	int v;
	double w;
};
bool cmp(edge a, edge b) {
	return a.w < b.w;
}
vector<edge> e;
int root(int x) {
	return x == pre[x] ? x : pre[x] = root(pre[x]);
}
int main() {
	cin >> m;
	for (int i = 1; i <= m; ++i) cin >> a[i];
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i];
		pre[i] = i;   
	}
	//建图
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			double w = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
			e.push_back({ i,j,w });
		}
	}
	sort(e.begin(), e.end(), cmp);
	int edge_num = 0;
	double maxw = 0.0;
	for (int i = 0; i < e.size(); ++i) {
		int fu = root(e[i].u);
		int fv = root(e[i].v);
		if (fu != fv) {
			edge_num++;
			pre[fu] = fv;
			maxw = max(maxw, e[i].w);
		}
		if (edge_num == n - 1) {
			break;
		}
	}
	int res = 0;
	for (int i = 1; i <= m; ++i) {
		if (a[i] >= maxw) res++;
	}
	cout << res;
	return 0;
}

例题

解题思路:

给了 n 个节点，又给了 n 个基点之间相互连接需要多少钱，现在要 n 个村庄都通电，只需要保证 n 个节点构成连通子图即可。

最小的连通子图是树，也就是构造一棵树，那么在图上构造一棵最最少花费的树的问题即为最小生成树。

AC代码：


#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring> 
using namespace std;
 
const int N = 1005;
int pre[N], x[N], y[N], h[N];
struct edges {
	int u;
	int v;
	double w;
	bool operator <(const edges& a) const {  //重载小于号
		return w < a.w;
	}
};
 
vector<edges> e;
int root(int x) {
	return x == pre[x] ? x : pre[x] = root(pre[x]);
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i] >> h[i];
		pre[i] = i;     //初始化并查集
	}
	//建图
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			double w = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) + (h[i] - h[j]) * (h[i] - h[j]);
			e.push_back({ i,j,w });
		}
	}
	sort(e.begin(), e.end());
	int edge_num = 0;
	double sumPrice = 0.0;
	for (int i = 0; i < e.size(); ++i) {
		int ru = root(e[i].u);
		int rv = root(e[i].v);
		if (ru != rv) {
			edge_num++;
			pre[ru] = rv;
			sumPrice += e[i].w;
		}
		if (edge_num == n - 1) break;
	}
	printf("%.2lf", sumPrice);
	return 0;
}

最短路径

最广为人知的图论问题就是最短路径问题。

简单图的最短路径

树上的路径：任意 2 点之间

只有一条路径

所有边长都为 1 的图：用 BFS 搜最短路径，复杂度
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/671656