挑战程序设计竞赛 第十二章 图
2021/4/10 18:17:19
本文主要是介绍挑战程序设计竞赛 第十二章 图,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
图的搜索 :
DFS(深度优先搜索)
BFS(广度优先搜索)
这两种算法对有向图无向图都适用
BFS常用作求最短路径的算法
图的表示
分为邻接表,邻接矩阵两种方法
DFS(12.3)
用递归实现深度优先搜索
#include<iostream> using namespace std; const int N = 100; int m[N][N]; int color[N] , d[N],f[N],tt=0; int n; void dfs_v(int u){ int v; color[u] = 1; //标记为正在走此点 d[u] = ++tt; for(v=1;v<=n;v++){ if(m[u][v] == 0) continue; if(color[v] == 0){ //如果v点没有走过,进行递归遍历 dfs_v(v); } } color[u] = 2; // 2代表此点已经走完 f[u] = ++tt; } void dfs() { int i,u; for(i=1;i<=n;i++) color[i] = 0; //全部初始化为没走过 for(i=1;i<=n;i++){ if(color[i] == 0){ //依次进行dfs dfs_v(i); } } for(i=1;i<=n;i++){ cout << i <<" "<< d[i] <<" " <<f[i] <<endl; } } int main() { int u,v,k,i,j; cin >> n; for(i=1;i<=n;i++){ for(j=1;j<=n;j++) m[i][j] = 0; //全部初始化为0 } for(i=0;i<n;i++){ cin >> u >>k; for(j=0;j<k;j++){ cin >> v; m[u][v] = 1; //初始化为1 } } dfs(); return 0; }
这篇关于挑战程序设计竞赛 第十二章 图的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)