当前位置: 首页> 汽车> 行情 > 5.图论.题目2

5.图论.题目2

时间:2025/7/12 2:05:45来源:https://blog.csdn.net/weixin_43831098/article/details/140487736 浏览次数: 0次

5.图论.题目2

  • 题目
    • 8.字符串接龙
    • 9.有向图的完全可达性
    • 10.岛屿的周长
    • 11.寻找存在的路径
    • 12.冗余连接1
    • 13.冗余连接2
    • 14.寻宝

题目

8.字符串接龙

题目链接
在这里插入图片描述
本题的直观思路如下图所示;但该题有两个问题:1.图中的线是如何连接起来的 2.如何确定起点到终点的最短路径。题中没给出节点之间的连线,条件是字符智能差一个。这里无向图求最短路,广搜最为合适,广搜只要搜到了终点,那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。另外得注意

  • 本题是无向图,需要用标记位,标记节点是否遍历过,否则就会死循环
  • 使用set检查字符串是否出现过会更快
    在这里插入图片描述
#include <iostream>
#include "vector"
#include "queue"
#include "unordered_map"
#include "unordered_set"using namespace std;int main(){string beginstr, endstr, strlist;int n;cin >>n;unordered_set<string> set; // store all the stringscin>> beginstr>> endstr;for(int i=0; i<n; i++) {cin >> strlist;set.insert(strlist);}queue<string> q;q.push(beginstr);unordered_map<string, int> visited;visited[beginstr] = 1;while(!q.empty()) {string curstr = q.front();q.pop();int path = visited[curstr];for(int i=0; i<curstr.size(); i++){string newstr = curstr;for(int j=0; j<26; j++){newstr[i] = 'a'+j;if(newstr == endstr){cout<< path+1<< endl;return 0;}if(set.find(newstr)!=set.end() && visited.find(newstr)==visited.end()){q.push(newstr);visited[newstr] = path+1;}}}}cout<< 0<< endl;return 0;
}

9.有向图的完全可达性

题目链接
在这里插入图片描述
题目要求判断节点的完全可达性;有向图搜索全路径的问题。 只能用深搜(DFS)或者广搜(BFS)来搜。
1.确认递归函数,参数:需要传入地图,需要知道key(知道下一步的节点)。同时需要一个数组,记录已经遍历的节点,这样才能判断有无将所有的节点已经遍历。
2.终止条件:因为在深度搜索时,没进入下一层搜索,是根据当前节点所对的邻接表key-list中的指向的节点,因此这是有限的遍历,当把邻接表所有的边遍历完,即可退出。

#include <iostream>
#include "vector"
#include "list"using namespace std;void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited){list<int> adjs = graph[key];for(int adj: adjs){if(!visited[adj]){visited[adj] = true;dfs(graph, adj, visited);}}
}int main(){int n,m,s,t;cin>> n>> m;vector<list<int>> graph(n+1);while(m--){cin >>s >>t;graph[s].push_back(t);}vector<bool> visited(n+1,false);visited[1] = true;dfs(graph, 1, visited);for(int i=1; i<=n; i++){if(!visited[i]){cout<< -1<< endl;return 0;}}cout<< 1<< endl;return 0;
}

10.岛屿的周长

题目链接
在这里插入图片描述
求中间岛屿的周长,如果是使用dfs,bfs搜索算法的话,就是当发现并遍历岛屿时,每遍历一个节点,就计算其四周临近海水的边数,统计总数即可。
但其实本题是可以不适用dfs,bfs搜索算法,直接执行全图的遍历,当遍历到陆地时,检查其四周节点的情况,当四周是海水,或者超出图范围时,可认为是其边界。

#include <iostream>
#include "vector"using namespace std;int main(){int n,m,s,t;cin>> n>> m;vector<vector<int>> graph(n, vector<int>(m, 0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>> graph[i][j];}}int dir[4][2] = {0, 1, 1, 0,-1,0,0,-1};int res = 0;for(int i=0;i<n;i++) {for (int j = 0; j < m; j++) {if (graph[i][j] == 1) {for (auto &d: dir) {int x = i + d[0];int y = j + d[1];if(x<0 || x>=n || y<0 || y>=m || graph[x][y]==0) res++;}}}}cout<<res<<endl;return 0;
}

11.寻找存在的路径

题目链接
在这里插入图片描述
这题是并查集的基础题目,并查集解决的集合问题:1)判断两个节点在不在一个集合 2)将来两个节点添加到一个集合中

#include <iostream>
#include "vector"using namespace std;int n; // number of nodes
vector<int> father(n+1, 0);// Union-Find Set's initialize Fucntion
void init(){for(int i=0;i<=n;i++){father[i] = i;}
}// Union-Find Set's Find Function
int find(int u){return u == father[u]? u : father[u] = find(father[u]); // path compression 路径压缩
}// Union-Find Set's Union Function
void join(int u, int v){u = find(u);v = find(v);if(u!= v) {father[v] = u;}
}// Union-Finds Set's isSame Function
bool isSame(int u, int v){u = find(u);v = find(v);return u == v;
}int main(){int m, s, t, source , destination;cin>> n>> m;init();while(m--){cin>> s>> t;join(s, t);}cin>> source>> destination;if(isSame(source, destination)) cout<< 1<< endl;else cout<< 0<< endl;return 0;
}

12.冗余连接1

题目链接
在这里插入图片描述
题目说是无向图,返回一条可以删去的边,使得结果图是一个有着N个节点的树(即:只有一个根节点)。如果有多个答案,则返回二维数组中最后出现的边。因此我们可以从前向后遍历边,边的两个节点如果不是在通过一个集合,就加入同一个集合(即,同一个根节点);如果两个节点已经在同一个集合,不添加改变,避免成环(无法成为树)。

#include <iostream>
#include "vector"using namespace std;int n; // number of nodes
vector<int> father(n+1, 0);void init(){for(int i=0;i<=n;i++){father[i] = i;}
}// Union-Find Set's Find Function
int find(int u){return u == father[u]? u : father[u] = find(father[u]); // path compression
}// Union-Find Set's Union Function
void join(int u, int v){u = find(u);v = find(v);if(u!= v) {father[v] = u;}
}// Union-Finds Set's isSame Function
bool isSame(int u, int v){u = find(u);v = find(v);return u == v;
}int main(){int s,t;cin>> n;init();for(int i=0;i<n;i++){cin>> s>> t;if(isSame(s, t)){cout<< s<< " "<< t<< endl;return 0;}else{join(s, t);}}return 0;
}

13.冗余连接2

题目链接
本题的本质是 :有一个有向图,是由一颗有向树 + 一条有向边组成的 (所以此时这个图就不能称之为有向树),现在让我们找到那条边 把这条边删了,让这个图恢复为有向树,而且考虑若有多条边可以删除,请输出标准输入中最后出现的一条边。

有向树的特征是,节点的父子点是唯一的,即节点的入度是1;而且不能成环,必有一个节点的父子点是其自己,分为可以分为以下三种情况:
1.情况一:如果我们找到入度为2的点,那么删一条指向该节点的边就行了
在这里插入图片描述
2.情况二:节点3 的入度为 2,但在删除边的时候,只能删 这条边(节点1 -> 节点3),如果删这条边(节点4 -> 节点3),那么删后本图也不是有向树了(因为找不到根节点)
在这里插入图片描述
3.情况三:没有入度为2的点,说明 图中有环了,删除构成环的边(最后形成的)就可以了
在这里插入图片描述
给出代码

#include <iostream>
#include "vector"using namespace std;int n; // number of nodes
vector<int> father;void init(){for(int i=0;i<=n;i++){father[i] = i;}
}// Union-Find Set's Find Function
int find(int u){return u == father[u]? u : father[u] = find(father[u]); // path compression
}// Union-Find Set's Union Functionvoid join(int u, int v){u = find(u);v = find(v);if(u!= v) {father[v] = u;}
}// Union-Finds Set's isSame Function
bool isSame(int u, int v){u = find(u);v = find(v);return u == v;
}bool isTreeaftermove(const vector<vector<int>>& edges, int delete_index){init();for(int i=0;i<n;i++){if(i==delete_index) continue;if(isSame(edges[i][0], edges[i][1])) return false; // 出现环join(edges[i][0], edges[i][1]);}return true; // 无环
}void moveEdge(const vector<vector<int>>& edges){init();for(int i=0;i<n;i++){if(isSame(edges[i][0], edges[i][1])){cout<< edges[i][0]<< " " << edges[i][1]<< endl;return;}else{join(edges[i][0], edges[i][1]);}}return;
}int main(){int s,t;cin>> n;father.resize(n+1,0);vector<vector<int>> edges(n, vector<int>(2,0)); // 存储边vector<int> indegree(n+1, 0); // 记录t节点的入度for(int i=0;i<n;i++){cin>> s>> t;edges[i][0] = s;edges[i][1] = t;indegree[t]++;}vector<int> vec; // 记录edges中使得出现入度位2节点出现的边的下标for(int i=n-1;i>=0;i--){if(indegree[edges[i][1]]==2) vec.push_back(i);}if(!vec.empty()){// 处理入度为2的边的节点 vec中有且只有2个元素if(isTreeaftermove(edges, vec[0])){cout<< edges[vec[0]][0]<< " " << edges[vec[0]][1]<< endl;}else {cout << edges[vec[1]][0] << " " << edges[vec[1]][1] << endl;}return 0;}else{// 处理自成环的节点moveEdge(edges);return 1;}
}

14.寻宝

题目链接
在这里插入图片描述
本题是最小生成树的模板题,最小生成树 可以使用 prim算法 也可以使用 kruskal算法计算出来。

最小生成树是所有节点的最小连通子图, 即:以最小的成本(边的权值)将图中所有节点链接到一起。图中有n个节点,那么一定可以用 n - 1 条边将所有节点连接到一起。那么如何选择 这 n-1 条边 就是 最小生成树算法的任务所在。
在这里插入图片描述
prim算法核心就是三步,我称为prim三部曲,大家一定要熟悉这三步:

  • 第一步,选距离生成树最近节点
  • 第二步,最近节点加入生成树
  • 第三步,更新非生成树节点到生成树的距离(即更新minDist数组)
    prim算法代码:
#include <iostream>
#include "vector"
#include "climits"using namespace std;int main(){int v, e; // 节点数,边数int x, y, k;cin>> v>> e;vector<vector<int>> graph(v+1, vector<int>(v+1, INT_MAX));for(int i=0; i<e; i++){cin>> x>> y>> k;graph[x][y] = k;graph[y][x] = k;}vector<int> minDist(v+1, INT_MAX);vector<bool> visited(v+1, false);vector<int> parent(v+1, -1);  // 用于记录每个节点i能被到达的父节点for(int i=1; i<=v; i++){// 从i=1出发,默认根节点是1int cur = -1;int minVal = INT_MAX;// 选择距离源点最近的节点作检查for(int j=1; j<=v; j++){if(!visited[j] && minDist[j] < minVal){minVal = minDist[j];cur = j;}}// 更新minDistvisited[cur] = true;for(int j=1; j<=v; j++){if(!visited[j] && graph[cur][j] < minDist[j]){minDist[j] = graph[cur][j];parent[j] = cur; // 记录边}}}int res = 0;for(int i=2; i<=v; i++){res += minDist[i];}cout<< res<< endl;return 0;
}

prim 算法是维护节点的集合,而 Kruskal 是维护边的集合。kruscal的思路:

  • 边的权值排序,因为要优先选最小的边加入到生成树里
  • 遍历排序后的边:1)如果边首尾的两个节点在同一个集合,说明如果连上这条边图中会出现环 2)如果边首尾的两个节点不在同一个集合,加入到最小生成树,并把两个节点加入同一个集合
    kruskal算法实现
在这里插入代码片
关键字:5.图论.题目2

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: