割点桥双连通分量.pptVIP

图论1 江川 七桥问题 七桥问题 图、点、边 G=(V,E) V 顶点集 E 边集 G=(V,E) 有向图、无向图 无向图 VV e= {a,b} 有向图 VxV e= a,b = {{a}, {a,b}} G=(V,E) 度（入度、出度） 环 路径 割 G=(V,E) 简单图 完全图 二分图 平面图 邻接矩阵 邻接表（边表） 判定 连通 度数平衡（有向、无向） 求解 “有边就走” 回溯 其他 欧拉路 混合图 NP-Complete 对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密顿图。 汉密尔顿回路 vs 欧拉回路 如果一个问题不是多项式时间可解的…… 1、加强条件，针对特定情况 2、减弱要求，求近似解 3、降低问题规模 O(n!*n） ？ 状态压缩动态规划 要考虑的状态： 已经经过哪些点？ 2^n 经过点的顺序？ n！? n*n ? n 例：[1,0,1,1,0][3] 表示经过了1、3和4，并停在3 状态数：2^n*n 转移：n 复杂度：O（2^n*n^2） POJ 3311 Floyd 点对间的距离 O（n^3） 动态规划的思想 F[i,j,k]?F[i,j] Dijkstra 单源最短路径 贪心算法 寻找未处理的最小的点?更新其他点 不能有负权边 O（V^2）? O（VlogV+E） Bellman-Ford 对每一条边进行松弛操作，重复V次： for each edge(u,v) if d[v] d[u] + w(u,v) d[v] = d[u] + w(u,v) 允许负权边，可判断负权圈 O（VE） SPFA Shortest Path Faster Algorithm Bellman-Ford的优化 用一个队列存储被更新的点 期望复杂度：O（kE） 特殊的图 连通性 结构实用 序 层次 最小生成树 Prim算法 两个点集（加入生成树和未加入生成树） O（V^2） Kruscal算法 按边权顺序从小到大枚举 O（E log E） 次小生成树 在最小生成树上添边 ?生成环 ?删边 ?新的生成树 在最小生成树上求两点路径上最大的边 poj1679 拓扑排序 1、选择入度为0的点v 2、删除v和从v出发的所有边 强连通分量 Tarjan算法 基于对图深度优先有哪些信誉好的足球投注网站的算法 DFN（u）：u有哪些信誉好的足球投注网站到的次序编号（时间戳） Low（u）：u或者u的子树能够追溯到的最早的有哪些信誉好的足球投注网站栈中的节点的次序号。 DFN(u)=Low(u)时，以u为根的有哪些信誉好的足球投注网站子树上所有节点是一个强连通分量。 O（V+E） POJ 2762 割点v：去掉点v后图不连通 桥/割边e：去掉边e后图不连通 双连通分量： 1、（边）任意去掉一条边，图仍连通 2、（点）任意去掉一个点，图仍连通 Tarjan算法求割点 在图的有哪些信誉好的足球投注网站树中，如果u为割点，当且仅当满足下面的条件： 1、如果u为树根，那么u必须有多于1棵子树 2、如果u不为树根，那么（u,v）为树枝边，当Low[v]=DFN[u]时。 在一个网络中，某些点之间可以接发信息（单向）。问至少增加多少条边可以使从任一点发送的信息可以到达其他所有点？ 强连通分量? 看做一个点 观察入度为0的点和出度为0的点 poj1236 给定一个有向无环图，n个点，m条边（1=n=100000,?0=m=1000000），每个点有点权。要求选择一条从某个入度为0的点到某个出度为0的点的路径，使得整个路径上点的权值之和最大。 有向无环图? 拓扑排序 图DP poj3249 谢谢！ 拓扑排序与强连通分量 拓扑排序与强连通分量 割点、桥、双连通分量 割点、桥、双联通分量 割点、桥、双联通分量 例题1 例题1 例题2 * 七桥问题 图的基本概念 图的基本概念 图的基本概念 图的基本概念 图的表示 图的表示 欧拉环 欧拉环 欧拉环 汉密尔顿回路 汉密尔顿回路 汉密尔顿回路 汉密尔顿回路 汉密尔顿回路 最短路 最短路 有效的程序员不应该浪费很多时间用于程序调试，他们应该一开始就不要把故障引入。 最短路 最短路 树 生成树 生成树 拓扑排序与强连通分量 拓扑排序与强连通分