图（邻接矩阵）知识大杂烩！！（邻接矩阵结构，深搜，广搜，prim算法，kruskal算法，Dijkstra算法，拓扑排序）（学会一文让你彻底搞懂！！）

  小伙伴们大家好，今天给大家带来图（邻接矩阵）的各种知识，让你看完此文章彻底学会邻接矩阵的相关问题。

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初始为1for(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];elsedist[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;
}

  注意当我们找到某个最小值时就要为其做上标记。另外还需要额外注意初始化问题，否则会引起很严重的错误。 

  关于图（邻接矩阵）的全部知识到此结束，我相信搞懂这一篇文章，你对图会有更深刻的理解！！多多点赞，感谢支持！