J6-2 图的概念与遍历

bfs 模版bool vis[最大状态]; int dep[最大状态]; void bfs( /*初始结点*/ ) { // 声明队列 // 初始化 dep 和 vis // 初始结点入队记录最短步数 while(/*队列非空*/) { 当前结点 q.front(); q.pop(); for( /*枚举所有的邻结点*/) { if( /*该结点已访问 或者 结点非法*/ ) continue; // 邻结点入队记录 dep、标记 vis } } }E. 传递闭包思路仅经由 1 号点能不能从 i 到达 j仅经由 1、2 号点能不能从 i 到达 j……仅经由 1、2、...、n 号点能不能从 i 到达 j最后得到传递闭包的关系矩阵。for(int k 1; k n; k){ for(int i 1; i n; i){ for(int j 1; j n; j){ if(adj[i][k] adj[k][j]) adj[i][j] true; } } }F. 关键节点思路枚举节点 2 ~ n-1 作为关键节点删除节点 i 后从 1 开始遍历是否能到达 n。删除节点想办法让遍历过程中不使用节点 i标记 i 为已访问int cnt 0; // 统计关键节点个数 for(/*枚举节点 i 为关键节点*/) { // 初始化访问数组 vis memset(...); // 不允许经过 i 设 i 节点为已访问 从 1 开始 dfs 遍历 if(/*不能访问到 n*/) cnt; }