长宁手机网站建设,学校网站建设项目背景,绵阳力嘉信息网站建设公司,wordpress首页添加音乐小伙伴们大家好#xff0c;今天给大家带来图#xff08;邻接矩阵#xff09;的各种知识#xff0c;让你看完此文章彻底学会邻接矩阵的相关问题。
1.邻接矩阵表示方法
1.1知识讲解 我们用一个二维数组arr来表示图。若图为有向图#xff0c;其中arr【i】【j】w表示i号点和… 小伙伴们大家好今天给大家带来图邻接矩阵的各种知识让你看完此文章彻底学会邻接矩阵的相关问题。
1.邻接矩阵表示方法
1.1知识讲解 我们用一个二维数组arr来表示图。若图为有向图其中arr【i】【j】w表示i号点和j号点之间的距离为w如果i和j之间无路可以设定w0或无穷。根据个人喜好后续代码会有不同若图为无向图arr【i】【j】w表示i和j之间是否直接相连w1表示相连w0表示不相连。
1.2.相关操作及代码 1.2.1初始化
void create(int a[][5],int n,int m){for(int i0;in;i){for(int j0;jm;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 j0;jn;j){visited[j]0;}queueintq;q.push(start);while(!q.empty()){iq.front();q.pop();visited[i]1;couti1 ;//可以换成其它处理逻辑for(int j0;jm;j){if(arr[i][j]!visited[j]){q.push(j);}}}coutendl;
}
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;coutstart1 ;for(int i0;im;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_queueint,vectorint,greaterint q){while(!q.empty()){q.pop();}
}int prim(int arr[][5],int n,int m,int start){int visited[n],cur,sum0,flag;priority_queueint,vectorint,greaterint q;//最小堆for(int i0;in;i){visited[i]0;}visited[start]1;//标记出发点for(int i0;im;i){if(arr[start][i]){//此时其他点均未被标记if(q.empty()||arr[start][i]q.top()){flagi;//记录距离最小点的下标}q.push(arr[start][i]);}}curq.top();//堆顶为距离最小值visited[flag]1;//为该店打上标记sumsumcur;cout选择权值curendl;clear(q);//清空最小堆int count1;while(countn-1){//开始时找到一条边再找n-2条边,count初始为1for(int i0;in;i){for(int j0;jm;j){if(visited[i]!visited[j]arr[i][j]){if(q.empty()||arr[i][j]q.top()){flagj;}q.push(arr[i][j]);}}}visited[flag]1;count;curq.top();sumsumcur;cout选择权值curendl;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-point10;n-point20;n-value0;return n;
}
//重载比较方法
struct cmp{bool operator()(struct node* a,struct node* b){return a-valueb-value;}
};
//重载哈希表
struct PairHash {template class T1, class T2size_t operator() (const pairT1, T2 pair) const {return hashT1()(pair.first) ^ hashT2()(pair.second);}
};
int find1(int *parent,int x){while(x!parent[x]){xparent[x];}return x;
}
void merge(int *parent,int x,int y){int fxfind1(parent,x);int fyfind1(parent,y);if(fx!fy){parent[fy]fx;}
}
int kruskal(int arr[][5],int n,int m){//每次选取权值最小的边不构成环取该边 priority_queueNode,vectorNode,cmp p;//重载比较方法 unordered_mappairint,int,int,PairHashu;int sum0;Node min;for(int i0;in;i){for(int j0;jm;j){if(arr[i][j]u.find(make_pair(i,j))u.end()){Node ncreatenode();n-point1i;n-point2j;n-valuearr[i][j];p.push(n);u[make_pair(i,j)]1;u[make_pair(j,i)]1;}}}int size0;int parent[n];for(int i0;in;i){parent[i]i;}while(sizen-1){minp.top();p.pop();if(find1(parent,min-point1)!find1(parent,min-point2)){//不构成环 cout选取权值min-valueendl;size;sumsummin-value;merge(parent,min-point1,min-point2);}}return sum;
} Kruskal算法第一步找出所有的边并加入最小堆中。由于是无向图比如arr【0】【1】和arr【1】【0】的边权值均为2如果不做处理可能重复选择。因此我们使用了哈希表来解决此问题。其中哈希表key值为pair型value为int型。value其它类型也可以我们用不到当i0j1时我们除了将01存入哈希表也需要将10存入哈希表这样当i1j0时就不会重复了。其中哈希表需要重载详细见上述代码。 Kruskal算法第二步选出最短边堆顶看是否和之前的边构成环。我们查看i和j的根是否相同若相同则说明构成环将其抛弃。否则说明不构成环是我们所需要的边并将i和j合并为同一集合。我们根据堆顶要找出该边所相连的点因此堆中应放一个结构体NodeNode中有三个元素分别为一条边和边所连接的两个点。其中小根堆的比较方法需要我们重载具体见上述代码。直到我们找出n-1条边时返回sum。 对于哈希表不了解的伙伴们可以看我之前的文章Leetcode--两数之和(day 3)-CSDN博客
6.拓扑排序
6.1知识讲解 拓扑排序适用于有向无环图。 拓扑排序是根据点的入度来实现的。当我们遍历找到一个入度为0的点时将其拿出并去除其影响。将因为该点而产生的其它点的入度消除继续遍历直至我们找完所有点。每一轮可能有多个入度为0的点这也就决定了拓扑排序结果不唯一。 举个例子1-21-32-3。1的入度为02的入度为13的入度为2。我们第一次找出1并去除其影响1-21-3此时2的入度为03的入度为1我们找出2并去除其影响2-3此时3的入度为0我们找出3。此时所有点均被找出拓扑排序结束。
6.2代码
void Toposort(int arr[][5],int n,int m){int vidited[n];for(int j0;jn;j){visited[j]0;}coutendl; int count[n];for(int i0;in;i){count[i]0;}for(int i0;in;i){for(int j0;jm;j){if(arr[i][j]){count[j];//统计入度 }}}int size0;while(sizen){for(int i0;in;i){if(!count[i]!visited[i]){//入度为0并且之前没被拿出,拿出并将其影响去除 couti1 ;visited[i]1;//标记此点防止重复size;for(int j0;jm;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 *distnew int[n];//初始化 for(int i0;in;i){if(arr[start][i])dist[i]arr[start][i];elsedist[i]88888;visited[i]0;}for(int i0;in;i){for(int j0;jn;j){if(ij){continue;}arr[i][j]arr[i][j]?arr[i][j]:88888;}}
// for(int i0;in;i){
// coutdist[i] ;
// }
// coutendl;dist[start]0;visited[start]1;for(int i0;in-1;i){//求n-1个最小值 //找距离start最短路径的点min999999;for(int j0;jn;j){if(!visited[j]dist[j]min){curj;mindist[j];}}dist[cur]min;visited[cur]1;//更新其它点 for(int j0;jn;j){if(!visited[j]dist[cur]arr[cur][j]dist[j]){dist[j]dist[cur]arr[cur][j];}} }return dist;
} 注意当我们找到某个最小值时就要为其做上标记。另外还需要额外注意初始化问题否则会引起很严重的错误。 关于图邻接矩阵的全部知识到此结束我相信搞懂这一篇文章你对图会有更深刻的理解多多点赞感谢支持
