南京做网站的公司,如何建立公司网站账号,徐州网站定制公司哪家好,服饰 视频 网站建设目录 1 基础知识2 模板3 工程化 1 基础知识
树和图的存储#xff1a;邻接矩阵、邻接表。 树和图的遍历#xff1a;dfs、bfs。
2 模板
树是一种特殊的图#xff08;即#xff0c;无环连通图#xff09;#xff0c;与图的存储方式相同。 对于无向图中的边ab#xff0c;… 目录 1 基础知识2 模板3 工程化 1 基础知识
树和图的存储邻接矩阵、邻接表。 树和图的遍历dfs、bfs。
2 模板
树是一种特殊的图即无环连通图与图的存储方式相同。 对于无向图中的边ab存储两条有向边a-b, b-a。 因此我们可以只考虑有向图的存储。
(1) 邻接矩阵g[a][b] 存储边a-b
(2) 邻接表
// 对于每个点k开一个单链表存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;// 添加一条边a-b
void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}// 初始化
idx 0;
memset(h, -1, sizeof h);3 工程化
题目1求树的重心。把某个结点删除剩余连通块的最大值。遍历每一个结点求取这个最大值集合中的最小值。 考察点用dfs()遍历树注意走过的结点不用走了。
#include iostream
#include vectorusing namespace std;const int N 1e5 10;
int n;
int res 1e9;
vectorbool visited(N);
vectorvectorint g(N);int dfs(int u) {//返回以u为根结点的子树的结点数目visited[u] true;int sum 1;int ans 0; //把u删除之后的剩余连通块数目最大值for (auto x : g[u]) {if (visited[x] false) {int t dfs(x);ans max(ans, t);sum t; }}ans max(ans, n - sum);res min(res, ans);return sum;
}int main() {cin n;int x, y;for (int i 0; i n - 1; i) {cin x y;g[x].emplace_back(y);g[y].emplace_back(x);}dfs(1);cout res endl;return 0;
}题目2给你一张图结点编号1,2,3…n给你一些边边的权重均是1求结点1到结点n的最短距离如果不存在路径输出-1。 考察点bfs()遍历图。
#include iostream
#include vector
#include queueusing namespace std;const int N 1e5 10;
vectorvectorint g(N);
vectorint d(N, -1);
int n, m;int main() {cin n m;int x, y;for (int i 0; i m; i) {cin x y;g[x].emplace_back(y);}queueint q;q.push(1);d[1] 0;while (!q.empty()) {int t q.front();q.pop();//t可以走到哪儿for (auto x : g[t]) {if (d[x] ! -1) continue;d[x] d[t] 1;q.push(x);}}cout d[n] endl;return 0;
}
