数据结构之图Python版.pptx

《数据结构之图Python版.pptx》由会员分享，可在线阅读，更多相关《数据结构之图Python版.pptx（52页珍藏版）》请在优知文库上搜索。

1、1目录一、图的定义和术语二、图的存储结构和实现三、图的基本算法及应用23456 V1 V4 V2 V3 V1 V4 V2 V3 V571iv0vimiv0vimiv2iv0vi1iv1iv2ivmiv1 -miv1iv0vimiv2iv0vimiv V1 V4 V2 V3 V589V1V2V3V4V5V1V2V3V4V5生成树10V1V2V3V4V5V6V7V1V2V3V4V5V6V7生成森林111213 10arcji Wij0arc或ji14V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1

2、V2V3V41516 vertex firstedge adjvex next17 vertex firstedge adjvex next V1 V4 V2 V3 V5 v1 v2 v3 v4 v5 1 4 4 1 2 2 3 0 4 3 1 0 V1 V4 V2 V3 v1 v2 v3 v4 2 3 0 1 v1 v2 v3 v4 3 0 2 00123401231819 firstout tailvex headvex headlink vertex firstin taillink info20 V1 V4 V2 V3 1 v1 v2 v3 v4 0 0 2 0 3 2 3 1 3 2

3、 0 3 2012321 vertex firstedge jvex ivex ilink jlink info22 V1 V5 V2 V4 V3 v1 v2 v3 v4 v5 0 0 1 3 2 2 1 3 4 2 1 403124232425 v1 v2 v4 v3 v5 v8 v7 v62627 v1 v2 v4 v3 v5 v8 v7 v6282930顶点集UVUuvvu顶点集T1T231 V1 V4 V2 V3 V5 V66515536426 V1 V3 V6 V4 V2 V53233 V1 V4 V2 V3 V56515536426 V1 V3 V4 V2 V5 V6 V63435BAEDC105030101002060AE：100ADE：90 ADCE：60 ABCE：703637 集 合 V-S集合 Svkvvi38ABAEDC105030101002060BDCE3940414243拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。4445C1C2C3C4C6C5C7拓扑序列： C1, C2, C3, C4, C5, C6, C7 4647484950v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=45152