南开大学算法导论第三章课件.pdf

第三章 图 苏 明 1 3.1 基本定义与应用 无向图 G = (V, E) V = 顶点 E = 边，反映顶点之间的关系 图参数: n = |V|, m = |E|. 2 3.1 基本定义与应用 例子 V = { 1, 2, 3, 4, 5, 6, 7, 8 } E = { 1-2, 1-3, 2-3, 2-4, 2-5, 3-5, 3-7, 3-8, 4-5, 5-6 } n = 8 m = 11 3 3.1 基本定义与应用 应用 Graph Nodes Edges transportation street intersections highways communication computers fiber optic cables World Wide Web web pages hyperlinks social people relationships food web species predator-prey software systems functions function calls scheduling tasks precedence constraints circuits gates wires 4 3.1 基本定义与应用 图的起源 5 3.1 基本定义与应用 Web graph. Node: 网页 Edge: 一个网页到另外网页的超级链接(hyperlink). 6 3.1 基本定义与应用 食物生态链图 Node = 生物种类. Edge = 从猎物到捕食者. 7 图的表示 1 2 3 4 5 6 7 8 1 0 1 1 0 0 0 0 0 邻接矩阵 2 1 0 1