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++; }