西安建设工程信息网人员信息_自媒体推广平台有哪些_全国最新的疫情数据_企业seo推广的绝密诀窍曝光

前言

这一期我们一起学习初级数据结构——邻接矩阵。邻接矩阵是数据结构中的一种重要表示方法，特别是在图论中得到了广泛应用。以下是对初级数据结构邻接矩阵的详细分析：

一、定义与表示

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V是顶点集合，E是边集合。邻接矩阵是一个二维数组，用于存储图中各顶点之间的连接关系。

二、特点与性质

存储方式：
邻接矩阵使用一个二维数组来存储顶点间的连接关系。
数组的行数和列数均等于图中的顶点数。

无向图与有向图：
对于无向图，邻接矩阵是对称的，即矩阵中第i行第j列的值等于第j行第i列的值。这表示如果顶点i与顶点j相连，则顶点j也与顶点i相连。

对于有向图，邻接矩阵不一定对称。如果顶点i到顶点j有一条有向边，则矩阵中第i行第j列的值不为0（通常表示为该边的权值），而第j行第i列的值可能为0。

权值表示：
在加权图中，邻接矩阵的元素可以表示边的权值。如果顶点i与顶点j不相连，则矩阵中对应的元素通常设为无穷大（或某个足够大的数）以表示不存在边。

在无权图中，如果顶点i与顶点j相连，则矩阵中对应的元素可以设为1（或其他非零值），不相连则设为0。

空间复杂度：
邻接矩阵的空间复杂度为O(n^2)，其中n为图中的顶点数。这是因为需要使用一个n×n的二维数组来存储顶点间的连接关系。

三、操作与应用

初始化：
在使用邻接矩阵表示图之前，需要先初始化矩阵。通常将矩阵的所有元素设为0（对于无权图）或无穷大（对于加权图），并设置顶点数和边数。

创建图：
根据用户输入或给定的数据，可以创建邻接矩阵表示的图。这包括输入顶点数据、边的数据（以及可能的权值）等。

遍历与查找：
邻接矩阵便于遍历和查找顶点间的连接关系。通过访问矩阵的特定元素，可以判断两个顶点是否相连以及边的权值。

应用：
邻接矩阵在图论算法中有广泛应用，如最短路径算法（如Dijkstra算法）、拓扑排序、图的遍历（深度优先搜索和广度优先搜索）等。
此外，邻接矩阵还可以用于表示社交网络中的好友关系、交通网络中的路线连接等实际问题。

四、代码模版

#include<iostream>
using namespace std;#define inf -1 // 用于表示两个定点没有边
class Graph {int vertices;int** edges;//相当于一个二维数组
public:Graph(int vertices);~Graph();void addEdge(int u, int v, int w);void printGraph();
};Graph::Graph(int vertices) {this->vertices = vertices;edges = new int* [vertices];for (int i = 0; i < vertices; i++) {edges[i] = new int[vertices];for (int j = 0; j < vertices; j++) {edges[i][j] = inf;//初始化图，任意两个顶点都没有边}}
}Graph::~Graph() {for (int i = 0; i < vertices; i++) {delete edges[i];}delete[]edges;
}void Graph::addEdge(int u, int v, int w) {edges[u][v] = w;
}void Graph::printGraph() {for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {cout << edges[i][j] << " ";}cout << endl;}
}int main() {Graph graph(5);graph.addEdge(0, 1, 1);graph.printGraph();return 0;
}

五、经典例题

1.——LCP 07. 传递信息

代码题解

class Solution {//这题就是比较典型的深度优先搜索int matrix[10][10];int N;int dfs(int u,int k){if(!k)return (u==N-1)?1:0;//k为零的时候就只用判断起始顶点，它也作为递归出口int sum=0;for(int i=0;i<N;i++){if(matrix[u][i])sum+=dfs(i,k-1);}return sum;}
public:int numWays(int n, vector<vector<int>>& relation, int k) {N=n;memset(matrix,0,sizeof(matrix));//邻接矩阵初始化为零for(int i=0;i<relation.size();i++){int a=relation[i][0];int b=relation[i][1];matrix[a][b]=1;}return dfs(0,k);}
};

2.——547. 省份数量

class Solution {//这题其实就是让我们求连通分量的个数bool color[201];int count;int n;void dfs(vector<vector<int>>& isConnected,int u){//深度优先搜索把这个定点所在的联通分量的所有顶点都访问过if(color[u])return;color[u]=true;for(int i=0;i<n;i++){if(isConnected[u][i])dfs(isConnected,i);}}
public:int findCircleNum(vector<vector<int>>& isConnected) {n=isConnected.size();count=0;memset(color,false,sizeof(color));for(int i=0;i<n;i++){if(color[i]==false){dfs(isConnected,i);++count;//没访问过的定点就自增一}}return count;}
};

3.——785. 判断二分图

class Solution {//这题是邻接表的题，到时将邻接表的时候仔细讲int color[101];
public:bool isBipartite(vector<vector<int>>& graph) {memset(color,-1,sizeof(color));int n=graph.size();while(1){int u=-1;for(int i=0;i<n;i++){if(color[i]==-1){u=i;break;}}if(u==-1)break;color[u]=0;queue<int>q;q.push(u);while(!q.empty()){u=q.front();q.pop();for(int i=0;i<graph[u].size();i++){int v=graph[u][i];if(color[v]!=-1){if(color[v]==color[u])return false;}else{color[v]=1-color[u];q.push(v);}}}}return true;}
};

六、总结

综上所述，邻接矩阵是一种直观且易于理解的图表示方法，适用于顶点数量相对较少且需要频繁查询顶点间连接关系的场景。

七、结语

邻接矩阵是一个用于存储图数据非常重要的数据结构，相信大家对邻接矩阵的了解有了提升，我们今后学习深度优先搜索和广度优先搜索会经常用到邻接矩阵这个数据结构，那么我们本期对邻接矩阵的学习就告一段落了，下期我们一起学习邻接矩阵的兄弟初级数据结构——邻接表，我们下期不见不散。

关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家