树和图 tree and graph 蔡亚星.

Presentation on theme: "树和图 tree and graph 蔡亚星."— Presentation transcript:

1 树和图 tree and graph 蔡亚星

2 树和图

3 树 n个顶点 n-1条边 连通无环 加一条边成环 删一条边不连通 任意两点路径唯一 根 叶子 有根树 无根树 父节点 子节点 祖先 子树 链

4 图 n个节点 m条边 简单图 不允许有重边和自环 多重图 允许有重边或自环

5 图 无向图 度 完全图

6 图 有向图 度 入度 出度

7 树和图的存储 邻接矩阵 邻接表 前向星 十字链表

8 邻接矩阵

9 邻接表

10 邻接表 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)); //初始化

11 邻接表 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] //找反向边

12 最短路问题 边权 固定？正负？ 源 单源？多源？

13 最短路 单源 边权固定 bfs

14 最短路 多源 含负权边 Floyd-Warshall算法
dist[i,j]:=min{dist[i,k]+dist[k,j],dist[i,j]}； O(N^3)

15 最短路 单源 正权边 Dijkstra’s算法 O(N^2) 堆优化 O(N log M)

16 最短路 单源 正权边 Dijkstra’s算法 O(N^2) 堆优化 O(N log M)

17 最短路 单源 含负权边 Bellman–Ford算法 O(NM) SPFA算法 队列优化 O(kM)

18 最近公共祖先 倍增 Tarjan算法

19 强连通分量 Tarjan算法 Kosaraju算法

20 割点割边 Tarjan算法

21 最后 2-sat问题 Dfs序 最小生成树 树链剖分 网络流 点分治 。。。 图论问题还有很多很多。。。

22 谢谢大家