树和图 tree and graph 蔡亚星
树和图
树 n个顶点 n-1条边 连通无环 加一条边成环 删一条边不连通 任意两点路径唯一 根 叶子 有根树 无根树 父节点 子节点 祖先 子树 链
图 n个节点 m条边 简单图 不允许有重边和自环 多重图 允许有重边或自环
图 无向图 度 完全图
图 有向图 度 入度 出度
树和图的存储 邻接矩阵 邻接表 前向星 十字链表
邻接矩阵
邻接表
邻接表 struct edge { int to, dis, next; //to - 指向节点 dis - 边权 next - 下一条从同一节 点出发的边的编号 }; edge e[M]; //e - 每一条边下标即为编的编号 N - 边数 int h[N]; //h - 从各节点出发的边的第一条边的编号 N - 节点数 int c = -1; //c - 当前边的编号 memset(h, -1, sizeof(h)); //初始化
邻接表 void addedge(int u, int v, int w) { //u - 出发节点 v - 指向节点 w - 边权 ++c; e[c] = (edge){v, w, h[u]}; h[u] = c; } for (int i = h[cur]; i != -1; i = e[i].next) { //遍历所有从cur节点出发的边 int to = e[i].to, dis = e[i].dis; edge[i ^ 1] //找反向边
最短路问题 边权 固定？正负？ 源 单源？多源？
最短路 单源 边权固定 bfs
最短路 多源 含负权边 Floyd-Warshall算法 dist[i,j]:=min{dist[i,k]+dist[k,j],dist[i,j]}； O(N^3)
最短路 单源 正权边 Dijkstra’s算法 O(N^2) 堆优化 O(N log M)
最短路 单源 正权边 Dijkstra’s算法 O(N^2) 堆优化 O(N log M)
最短路 单源 含负权边 Bellman–Ford算法 O(NM) SPFA算法 队列优化 O(kM)
最近公共祖先 倍增 Tarjan算法
强连通分量 Tarjan算法 Kosaraju算法
割点割边 Tarjan算法
最后 2-sat问题 Dfs序 最小生成树 树链剖分 网络流 点分治 。。。 图论问题还有很多很多。。。
谢谢大家