小伙伴们大家好，今天给大家带来图（邻接矩阵）的各种知识，让你看完此文章彻底学会邻接矩阵的相关问题。
1.邻接矩阵表示方法
1.1知识讲解
我们用一个二维数组arr来表示图。若图为有向图，其中arr【i】【j】=w表示i号点和j号点之间的距离为w，如果i和j之间无路可以设定w=0或无穷。（根据个人喜好，后续代码会有不同）若图为无向图，arr【i】【j】=w表示i和j之间是否直接相连，w=1表示相连；w=0表示不相连。
1.2.相关操作及代码
1.2.1初始化
void create(int a[][5],int n,int m){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
a[i][j]=0;
}
}
}我这里数组为5行5列，因此传参时使用a【】【5】。大家根据自己数组情况更改，或者使用全局变量。n和m为行列数。第i行代表i号点和其它点之间的关系。 我这里初始化为0，大家也可以初始化为无穷。
2.广搜（bfs）
2.1知识讲解
广度搜索我们使用队列完成。给定一个出发点i，将其入队列。拿出队列首元素，我们遍历arr数组第i行，如果arr【i】【j】不为0说明i和j直接相连，将其存入队列，直至遍历完第i行。此时队列中的元素为与i号点相连的点。（i号点已经出队列）然后再拿出队列首元素，重复上述操作，直至队列为空。应该注意的是：当我们拿出队列首元素后，就要为其打上标记，放置再将其入队列。
2.2代码
void bfs(int arr[][5],int n,int m,int start){//从start节点开始
int visited[n],i;
for(int j=0;j<n;j++){
visited[j]=0;
}
queue<int>q;
q.push(start);
while(!q.empty()){
i=q.front();
q.pop();
visited[i]=1;
cout<<i+1<<" ";//可以换成其它处理逻辑
for(int j=0;j<m;j++){
if(arr[i][j]&&!visited[j]){
q.push(j);
}
}
}
cout<<endl;
}3.深搜（dfs）
3.1知识讲解
广搜的思想是：每次将当前点的所有相连点遍历完。而深搜的思想是：若当前点找到相连点后，从相连点出发，继续寻找相连点，若找不到则返回上一层。这种思想很符合递归策略。其中，仍然需要visited标记数组防止重复找点。
3.2代码
int visited[5]={0};
void dfs(int arr[][5],int n,int m,int start){
visited[start]=1;
cout<<start+1<<" ";
for(int i=0;i<m;i++){
if(arr[start][i]&&!visited[i]){
dfs(arr,n,m,i);
}
}
}其中，visited数组必须为全局变量。否则递归重新进入函数会让其不断清零，起不到标记作用。
4.寻找最小生成树-prim算法
4.1最小生成树
定义：给定一个连通的无向图，最小生成树是指包含图中所有顶点的一棵树，且该树的所有边的权重之和最小。
判断是否联通我们可以使用深搜以及广搜，看能否遍历所有节点。也可以使用我之前讲过的并查集，通过不断地merge操作，看最后是否只有一个根。
相关连接：岛屿数量+并查集_岛屿数量 并查集-CSDN博客。我们在讲解时默认图是联通的。
若图有n个点，那么最小生成树会有n-1条边。这个性质用于让我们知道何时循环结束。
4.2 Prim算法知识讲解
Prim算法思想：从一个出发点开始（标记出发点），寻找与其直接相连的点，在这些点中找出与其距离最小的点将其标记。下一次操作时，凡是被标记的点都要寻找与其距离最小的点（要求所寻找的点未被标记），最终从这些距离最小点中再选出最小点将其标记。重复操作，直至找出n-1条边。
4.3代码
void clear(priority_queue<int,vector<int>,greater<int> >&q){
while(!q.empty()){
q.pop();
}
}
int prim(int arr[][5],int n,int m,int start){
int visited[n],cur,sum=0,flag;
priority_queue<int,vector<int>,greater<int> >q;//最小堆
for(int i=0;i<n;i++){
visited[i]=0;
}
visited[start]=1;//标记出发点
for(int i=0;i<m;i++){
if(arr[start][i]){//此时其他点均未被标记
if(q.empty()||arr[start][i]<q.top()){
flag=i;//记录距离最小点的下标
}
q.push(arr[start][i]);
}
}
cur=q.top();//堆顶为距离最小值
visited[flag]=1;//为该店打上标记
sum=sum+cur;
cout<<"选择权值"<<cur<<endl;
clear(q);//清空最小堆
int count=1;
while(count<n-1){//开始时找到一条边，再找n-2条边,count初始为1
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(visited[i]&&!visited[j]&&arr[i][j]){
if(q.empty()||arr[i][j]<q.top()){
flag=j;
}
q.push(arr[i][j]);
}
}
}
visited[flag]=1;
count++;
cur=q.top();
sum=sum+cur;
cout<<"选择权值"<<cur<<endl;
clear(q);
}
return sum;
} 这里使用最小堆来存储边的权重，大家注意如何找到距离最小的那个点的下标，因为开始时我就在这有点晕。
5.寻找最小生成树算法-kruskal算法
5.1知识讲解
Kruskal算法相较于prim算法较为简单，思想如下：每次从所有边中选择最短的那条，如果选择之后和之前选择的边不构成环，那么接受。如果构成环则拒绝，重新寻找。直至选择n-1条边。重点是如何判断是否成环：在此我使用了并查集的思想。不会的可以查看我之前的文章：岛屿数量+并查集_岛屿数量 并查集-CSDN博客
5.2代码
struct node{
int point1;
int point2;
int value;
};
typedef struct node* Node;
Node createnode(){
Node n=(Node)malloc(sizeof(struct node));
n->point1=0;
n->point2=0;
n->value=0;
return n;
}
//重载比较方法
struct cmp{
bool operator()(struct node* a,struct node* b){
return a->value>b->value;
}
};
//重载哈希表
struct PairHash {
template <class T1, class T2>
size_t operator() (const pair<T1, T2> &pair) const {
return hash<T1>()(pair.first) ^ hash<T2>()(pair.second);
}
};
int find1(int *parent,int x){
while(x!=parent[x]){
x=parent[x];
}
return x;
}
void merge(int *parent,int x,int y){
int fx=find1(parent,x);
int fy=find1(parent,y);
if(fx!=fy){
parent[fy]=fx;
}
}
int kruskal(int arr[][5],int n,int m){//每次选取权值最小的边不构成环取该边
priority_queue<Node,vector<Node>,cmp >p;//重载比较方法
unordered_map<pair<int,int>,int,PairHash>u;
int sum=0;
Node min;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]&&u.find(make_pair(i,j))==u.end()){
Node n=createnode();
n->point1=i;
n->point2=j;
n->value=arr[i][j];
p.push(n);
u[make_pair(i,j)]=1;
u[make_pair(j,i)]=1;
}
}
}
int size=0;
int parent[n];
for(int i=0;i<n;i++){
parent[i]=i;
}
while(size<n-1){
min=p.top();
p.pop();
if(find1(parent,min->point1)!=find1(parent,min->point2)){//不构成环
cout<<"选取权值"<<min->value<<endl;
size++;
sum=sum+min->value;
merge(parent,min->point1,min->point2);
}
}
return sum;
}Kruskal算法第一步：找出所有的边，并加入最小堆中。由于是无向图，比如arr【0】【1】和arr【1】【0】的边权值均为2，如果不做处理可能重复选择。因此我们使用了哈希表来解决此问题。其中哈希表key值为pair型，value为int型。（value其它类型也可以我们用不到）当i=0，j=1时，我们除了将（0，1）存入哈希表也需要将（1，0）存入哈希表，这样当i=1，j=0时就不会重复了。其中哈希表需要重载，详细见上述代码。
Kruskal算法第二步：选出最短边（堆顶），看是否和之前的边构成环。我们查看i和j的根是否相同，若相同则说明构成环，将其抛弃。否则，说明不构成环，是我们所需要的边，并将i和j合并为同一集合。我们根据堆顶要找出该边所相连的点，因此堆中应放一个结构体Node，Node中有三个元素，分别为一条边和边所连接的两个点。其中小根堆的比较方法需要我们重载，具体见上述代码。直到我们找出n-1条边时，返回sum。
对于哈希表不了解的伙伴们，可以看我之前的文章：Leetcode--两数之和(day 3)-CSDN博客
6.拓扑排序
6.1知识讲解
拓扑排序适用于有向无环图。
拓扑排序是根据点的入度来实现的。当我们遍历找到一个入度为0的点时，将其拿出并去除其影响。（将因为该点而产生的其它点的入度消除）继续遍历，直至我们找完所有点。每一轮可能有多个入度为0的点，这也就决定了拓扑排序结果不唯一。
举个例子，1->2，1->3，2->3。1的入度为0，2的入度为1，3的入度为2。我们第一次找出1，并去除其影响（1->2，1->3），此时2的入度为0，3的入度为1，我们找出2，并去除其影响（2->3），此时3的入度为0，我们找出3。此时所有点均被找出，拓扑排序结束。
6.2代码
void Toposort(int arr[][5],int n,int m){
int vidited[n];
for(int j=0;j<n;j++){
visited[j]=0;
}
cout<<endl;
int count[n];
for(int i=0;i<n;i++){
count[i]=0;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]){
count[j]++;//统计入度
}
}
}
int size=0;
while(size<n){
for(int i=0;i<n;i++){
if(!count[i]&&!visited[i]){//入度为0并且之前没被拿出,拿出并将其影响去除
cout<<i+1<<" ";
visited[i]=1;//标记此点防止重复
size++;
for(int j=0;j<m;j++){
if(arr[i][j]){
count[j]--;//去除其影响
}
}
}
}
}
}注意拿出一个点后，就要为其打上标记，防止重复拿。
7.Dijkstra算法-单元最短路径
7.1知识讲解
Dijkstra算法思想第一步：寻找与出发点最近的点。第二步：根据最近点更改其它点：如果出发点距离某个点i的距离大于出发点到最近点的距离加上最近点到i点的距离，那么更改出发点到i点的距离为出发点到最近点的距离加上最近点到i点的距离。重复n-1次操作。（因为出发点到出发点距离为0）
7.2代码
int *dijkstra(int arr[][5],int start,int n){//n为点的数量
int visited[n],min,cur;
int *dist=new int[n];
//初始化
for(int i=0;i<n;i++){
if(arr[start][i])
dist[i]=arr[start][i];
else
dist[i]=88888;
visited[i]=0;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j){
continue;
}
arr[i][j]=arr[i][j]?arr[i][j]:88888;
}
}
// for(int i=0;i<n;i++){
// cout<<dist[i]<<" ";
// }
// cout<<endl;
dist[start]=0;
visited[start]=1;
for(int i=0;i<n-1;i++){//求n-1个最小值
//找距离start最短路径的点
min=999999;
for(int j=0;j<n;j++){
if(!visited[j]&&dist[j]<min){
cur=j;
min=dist[j];
}
}
dist[cur]=min;
visited[cur]=1;
//更新其它点
for(int j=0;j<n;j++){
if(!visited[j]&&dist[cur]+arr[cur][j]<dist[j]){
dist[j]=dist[cur]+arr[cur][j];
}
}
}
return dist;
}注意当我们找到某个最小值时就要为其做上标记。另外还需要额外注意初始化问题，否则会引起很严重的错误。
关于图（邻接矩阵）的全部知识到此结束，我相信搞懂这一篇文章，你对图会有更深刻的理解！！多多点赞，感谢支持！
标签：arr,parent,int,入度,最小,邻接矩阵,算法,搞懂 From： https://blog.csdn.net/weixin_74901355/article/details/143267365