DS09_图1题库.pptVIP

图的存储结构 四、无向图的邻接多重表表示法—进行“边”的操作 顶点结点： typedef struct VexBox { VertexType data; //存与顶点有关的信息 EBox * firstedge; //指向第一条依附于该顶点的边 } VexBox; VexBox AMLGraph[M]; data firstedge 边结点： typedef struct node { VisitIf mark; //标志域，记录是否已经有哪些信誉好的足球投注网站过 int ivex, jvex; //该边依附的两个顶点在表头数组中位置 struct EBox * ilink, * jlink; //分别指向依附于ivex和jvex的下一条边 } EBox; mark ivex ilink jvex jlink 图的存储结构 四、无向图的邻接多重表表示法 例 a e c b d 1 2 3 4 a c d b 5 e 1 2 1 4 3 4 3 2 3 5 5 2 ^ ^ ^ ^ ^ 与邻接表区别：后者同一条边，只需一个链结点表示 data firstedge mark ivex ilink jvex jlink 小结 图的基本概念 图、顶点、边（弧） 有关术语： 度、子图、路径、连通图、生成树 图的基本操作与储存表示 访问、修改 4种表示法 邻接矩阵 邻接表 十字链表 邻接多重表 作业：网络教室 下次课程预告 图2 图的遍历 最小生成树 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * * * 北京理工大学 / * 1 内容提要 图的基本概念 定义、术语 常见操作 图的储存结构 图的遍历 图的最小生成树 线性表中结点之间的关系是一对一的，除头结点和尾结点外，每个结点仅有一个前驱和一个后继； 树是按分层关系组织的结构，树结构中结点之间关系是一对多，一个双亲可以有多个孩子，每个孩子结点仅有一个双亲； 图结构中，顶点之间的关联是任意的，图中每个顶点都可以和其它顶点相关联，即数据元素之间存在多对多的关系。 图的引入 图的应用举例 例1、交通图（公路、铁路） 顶点：地点 边：连接地点的路 例2、电路图 顶点：元件 边：连接元件之间的线路 例3、通讯线路图（互联网） 顶点：地点 边：地点间的连线 例4、各种流程图 如产品的生产流程图。 顶点：工序 边：各道工序之间的顺序关系 研究热点：复杂网络研究 图的基本概念 图(Graph)——图G是由两个集合V(G)和E(G)组成的，记为G=(V，E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对。 图的分类 有向图 无向图 图的基本概念 有向图——有向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头。 图的基本概念 例如： G1 = V1,E1 V1 = { A, B, C, D, E } E1 = {A,B, A,E, B,C, C,D, D,B, D,A, E,C } E A C B D 图的基本概念 无向图——无向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是边的有限集合，边是顶点的无序对，记为 (v,w) 或 (w,v)，并且(v,w)=(w,v)。 图的基本概念 例如： G2 = (V2,E2) V2 = { v0 ,v1,v2,v3,v4 } E2 = { (v0,v1), (v0,v3), (v1,v2), (v1,v4),  (v2,v3), (v2,v