第8章 图 提纲 CONTENTS 8.6拓扑排序 8.1图的基本概念 8.7 AOE网与关键路径 8.2图的存储结构 8.5最短路径 8.3图的遍历 作业 8.4生成树和最小生成树 上机实验题 1/40
CONTENTS 提纲 1/40
图的基本概念8.18.1.1图的定义图G（Graph）由两个集合V（Vertex）和E（Edge）组成，记为G=（V，E）V是顶点的有限集合，记为V(G)。E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。2/40
图G（Graph）由两个集合V（Vertex）和E（Edge）组成，记为G=(V，E)。 V是顶点的有限集合，记为V(G)。 E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。 2/40
抽象数据类型图的描述ADT Grapht数据对象：D={ai|≤i≤n-1，n≥0，a为int类型}//a为每个顶点的唯一编号数据关系：R=(r]r={<ai，a,>|ai，a,ED,≤i≤n-1,0≤j≤n-1，其中a,可以有零个或多个前驱元素，可以有零个或多个后继元素基本运算：voidCreateGraph（）：根据相关数据建立一个图。voidDispGraph()：输出一个图。7说明约定用i（0≤i≤n-1）表示第i个顶点的编号。3/40
ADT Graph { 数据对象： D={ai | 0≤i≤n-1，n≥0，ai为int类型} //ai为每个顶点的唯一编号 数据关系： R={r} r={<ai，aj> | ai，aj∈D，0≤i≤n-1，0≤j≤n-1，其中ai可以有零个 或多个前驱元素，可以有零个或多个后继元素 } 基本运算： void CreateGraph()：根据相关数据建立一个图。 void DispGraph()：输出一个图。 . } 抽象数据类型图的描述 说明 约定用i（0≤i≤n-1）表示第i个顶点的编号。 3/40
无向图和有向图在图G中，如果代表边的顶点对（或序偶）是无序的，则称G为无向图。无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向边。如(i，j)表示顶点i与顶点j的一条无向边，显然，（i，j)和(j,所代表的是同一条边。如果表示边的顶点对（或序偶）是有序的，则称G为有向图。在有向图中代表边的顶点对通常用尖括号括起来，用以表示一条有向边（又称为弧），如<i，>表示从顶点i到顶点的一条边。（a）一个无向图(b） 一个有向图4/40
在图G中，如果代表边的顶点对（或序偶）是无序的，则称G为无向图。 无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向 边。如(i，j)表示顶点i与顶点j的一条无向边，显然，(i，j)和(j， i)所代表的是同一条边。 如果表示边的顶点对（或序偶）是有序的，则称G为有向图。在有向图 中代表边的顶点对通常用尖括号括起来，用以表示一条有向边（又称为 弧），如<i，j>表示从顶点i到顶点j的一条边。 无向图和有向图 1 2 3 0 4 1 2 3 0 4 （a）一个无向图 （b）一个有向图 4/40
数据结构中的图一般不重复出现一条边，如果允许重复边出个现，这样的图称为多重图，如一个无向图中顶点1和2之间出现两条或两条以上的边。本书中讨论的图均指非多重图。（a）多重无向图（b）多重有向图5/40
数据结构中的图一般不重复出现一条边，如果允许重复边出 现，这样的图称为多重图，如一个无向图中顶点1和2之间出 现两条或两条以上的边。本书中讨论的图均指非多重图。 1 2 0 3 1 2 0 3 （a）多重无向图 （b）多重有向图 5/40