小伙伴们大家好,今天给大家带来图(邻接矩阵)的各种知识,让你看完此文章彻底学会邻接矩阵的相关问题。
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;
}
注意当我们找到某个最小值时就要为其做上标记。另外还需要额外注意初始化问题,否则会引起很严重的错误。
关于图(邻接矩阵)的全部知识到此结束,我相信搞懂这一篇文章,你对图会有更深刻的理解!!多多点赞,感谢支持!