本文主要是介绍邻接矩阵基础入门,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
引言
邻接矩阵是图论中表示图的一种方式,它通过矩阵来描述图中各顶点之间的连接关系。在邻接矩阵中,图中的每个顶点都对应矩阵中的一行和一列,矩阵中的元素表示顶点之间是否存在边以及边的权重(如果是加权图)。
定义和性质
对于一个包含n个顶点的图G,其邻接矩阵A是一个n×n的矩阵,其中的元素A[i][j](i、j从0开始或从1开始,根据实际情况而定)定义如下:
- 如果存在一条从顶点i到顶点j的边,那么A[i][j]为1(在无权图中)或者边的权重(在加权图中)。
- 如果没有从顶点i到顶点j的边,那么A[i][j]为0。
因此,对于无向图来说,邻接矩阵是对称的,即对所有i和j有A[i][j] = A[j][i]。对于有向图,则不一定符合这个性质。
示例
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
在这个邻接矩阵中,A[0][1] = 1表示顶点0和顶点1之间有一条边,而A[0][3] = 0表示顶点0和顶点3之间没有边。
邻接矩阵的优缺点
邻接矩阵的主要优点是简单直观,容易理解和实现,特别适合用来表示稠密图。此外,基于邻接矩阵的图算法(如求最短路径的Floyd-Warshall算法)也比较简洁。
不过,邻接矩阵也有明显的缺点。其中最大的缺点是空间复杂度较高,对于包含n个顶点的图,不管图中有多少条边,邻接矩阵都需要n×n的空间。因此,对于稀疏图(边数远小于顶点数的平方)来说,使用邻接矩阵表示会造成很大的空间浪费。
此外,一些图算法(如寻找所有顶点对的最短路径)的时间复杂度也会受到邻接矩阵空间复杂度的影响。
使用邻接矩阵的示例代码
以下是使用C++实现的邻接矩阵表示法创建无向图的示例代码:
#include <iostream>
#include <vector>
using namespace std;class Graph {
private:int V; // 顶点数vector<vector<int>> adjMatrix; // 邻接矩阵
public:Graph(int V) {this->V = V;adjMatrix.resize(V, vector<int>(V, 0));}void addEdge(int u, int v) {adjMatrix[u][v] = 1;adjMatrix[v][u] = 1; // 无向图的邻接矩阵是对称的}void printAdjMatrix() {for (int i = 0; i < V; ++i) {for (int j = 0; j < V; ++j) {cout << adjMatrix[i][j] << " ";}cout << "\n";}}
};int main() {Graph g(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(1, 3);g.printAdjMatrix();return 0;
}
这段代码定义了一个Graph
类来表示图,使用邻接矩阵存储图中的边信息,并提供了添加边和打印邻接矩阵的方法。
结语
通过这篇文章,你应该对邻接矩阵有了一个基本的了解,包括它是什么、如何使用它以及它的优缺点。而实际上,根据具体应用的需要,你可能还会选择使用邻接列表等其他图表示法。
这篇关于邻接矩阵基础入门的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!