[工学]基本数据结构-图.ppt

ACM/ICPC程序设计 基本数据结构 及其在程序设计中的应用 张淑平 非线性结构 树、二叉树 图 数据结构课程中所要求的图 掌握图模型中数据的存储方式：图的邻接矩阵存储和邻接表存储结构。 掌握图的两种遍历方法：深度优先遍历和广度优先遍历算法。 理解求最小生成树、拓扑排序、求关键路径、求最短路径等算法。 图的示例 图结构 基本概念 图是顶点集和边集组成的二元组G=(V,E),E中每条边是V中一对顶点(u,v)间的联系,如果是无序对，那么称该图为无向图，否则为有向图。 顶点u,v间有边，u,v互为邻接点。 边(u,v)，和顶点u和v相关联。 顶点v的度是和v相关联的边的数目.有向图中,以v为头的弧的数目称为出度;以v为尾的弧的数目称为入度。 连通图、强连通子图(分量) 无向图的生成树 ...... 无向图及其生成树 有向图及其强连通子图 图的邻接矩阵表示 图的邻接链表表示 图的算法 基本算法 遍历算法 求最小生成树的算法 求最短路径的算法 拓扑排序算法 关键路径求解算法 ...... 其他算法 连通性问题及求解算法 匹配问题及算法 网络流问题及算法 … 例3：Is it a tree? 例3：Is it a tree? 例4：学校网络 例4：学校网络(续) 例4：学校网络(续) 深度优先有哪些信誉好的足球投注网站DFS 深度优先遍历图的方法是，从图中某顶点v出发： (1)访问顶点v； (2)依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相同的顶点都被访问 (3)若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止(用栈) 广度优先有哪些信誉好的足球投注网站BFS 从图中某顶点vi出发： ① 访问顶点vi ； ② 访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ； ③ 依次从这些邻接点（在步骤②中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问； (用队列) DFS VS BFS 例5：SPF(1119) 例5：SPF 例5：SPF 例5：SPF 例5：SPF 掌握有关图的基本算法 遍历方法：深度优先遍历(DFS)，广度优先遍历(BFS) 求最短路径：Dijkstra算法，Floyd算法，Bellman-Ford算法 最小生成树：Prim算法，Kruskal算法 关键路径 关节点 最大独立集，最小支配集 最大匹配，最优匹配 最大网络流 ... ... 最小代价生成树 克鲁斯卡尔算法求最小生成树 最小代价生成树 克鲁斯卡尔算法求最小生成树 最小代价生成树 克鲁斯卡尔算法求最小生成树 最小代价生成树 克鲁斯卡尔算法求最小生成树 例6：QS Network 例6：QS Network 例6：QS Network 例6：QS Network 例6：QS Network 要求 编程实现二叉树的先序、中序、后序和层序遍历算法。 编程实现构造最优二叉树完成哈夫曼编码、译码处理。 编程实现图的深度优先、广度优先遍历算法。 编程实现求解最小生成树的算法。 编程实现求解图的最短路径算法。 实例 zoj 1060《Sorting It All Out》 由输入构造有向图，判断是否有环，判断是否完全图，最后冒泡排序确定输出序列。 zoj 1082《Stockbroker Grapevine 》 Floyd算法求最短路径。 zoj 1105《FatMouses Tour 》 应用欧拉图的性质。 zoj 1203《Swordfish》 最小生成树。 zoj 1119《SPF》 找图的关节点。 zoj 1492《Maximum Clique》 找最大团。 附在线试题库： / / 美国中学信息学网站(usaco)：强烈推荐 /usacogate Each QS has its favorate brand of network adapters and always buys the brand in all of its connections. Also the distance between QS vary. Given the price of each QSs favorate brand of network adapters and the price of cable between each pair of QS, your task is to write a program to determine the minimum cost to setup a QS network. Input The 1st line of the input contains an integer t which indic