数据结构图的知识

1、234EACBD56V0V4V3V1V27 例例245136G1图图G1中：中：V(G1) = 1 , 2 , 3 , 4 , 5, 6 E(G1) = , , , , , , V0V0 V1V1 V2V2 V3V389 V0V0 V4V4 V3V3 V1V1 V2V2e eV0V1V2V31011无向图无向图G1G1有向图有向图G2 V0V0 V4V4 V3V3 V1V1 V2V2V0V1V2V312 非连通图非连通图 连通图连通图 强连通图强连通图 非强连通图非强连通图 V0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2

2、V3V3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V413(a)(a)(b)(b)(c)(c) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V214连通分量连通分量非连通图非连通图 V0V0 V2V2 V3V3 V1V1 V5V5 V4V415强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V116连通图连通图G1G1G1G1的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V

3、2V217 V0V0 V1V1 V2V2 V3V3Aij=Aij=1 1 若若(v(vi i,v,vj) ) E E 或或 v E E0 0 否则否则0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0在数组表示法中，用邻接在数组表示法中，用邻接矩阵表示顶点间的关系矩阵表示顶点间的关系 V0V0 V4V4 V3V3 V1V1 V2V20 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 018 V0V0 V4V4 V3

4、V3 V1V1 V2V22 2 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 03 34 4该结点表示边该结点表示边( (V2,V4)V2,V4)，其中的，其中的4 4是是V4V4在一在一维数组中的位置维数组中的位置19adjvex nextvexdata firstarc20211234v0v2v3v1vexdata firstarc 3 2 4 1adjvex next类似于无向图的邻接表，所不同的是：类似于无向图的邻接表，所不同的是：以同一顶点为以同一顶点为起点起点的弧：用线性链表存储的弧：用

5、线性链表存储V0V1V2V3221234v0v2v3v1vexdatafirstarc 4 1 1 3类似于有向图的邻接表，所不同的是：类似于有向图的邻接表，所不同的是：以同一顶点为以同一顶点为终点终点弧：用线性链表存储弧：用线性链表存储V0V1V2V323弧结点：弧结点：typedef struct arcnode int tailvex, headvex; /弧尾、弧头在表头数组中位置弧尾、弧头在表头数组中位置 struct arcnode *hlink；/指向弧头相同的下一条弧指向弧头相同的下一条弧 struct arcnode * *tlink; /指向弧尾相同的下一条弧指向弧尾相同的

6、下一条弧 ArcBox;tailvex headvex hlink tlink顶点结点：顶点结点：typedef struct VexNode VertexType data; /存与顶点有关信息存与顶点有关信息 ArcBox *firstin；/指向以该顶点为弧头的第一个弧结点指向以该顶点为弧头的第一个弧结点 ArcBox *firstout; /指向以该顶点为弧尾的第一个弧结点指向以该顶点为弧尾的第一个弧结点 VexNode;VexNode OLGraphM;data firstin firstout24例例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1

7、相同相同弧尾弧尾相同相同弧头弧头25顶点结点：顶点结点：typedef struct VexBox VertexType data; /存与顶点有关的信息存与顶点有关的信息 EBox * * firstedge; /指向第一条依附于该顶点的边指向第一条依附于该顶点的边 VexBox;VexBox AMLGraphM;data firstedge边结点：边结点：typedef struct node VisitIf mark; /标志域标志域，记录是否已经搜索过，记录是否已经搜索过 int ivex, jvex; /该边依附的两个顶点在表头数组中位置该边依附的两个顶点在表头数组中位置 struc

8、t node * * ilink, * * jlink; /分别指向依附于分别指向依附于ivex和和jvex的下一条边的下一条边 EBox;mark ivex ilink jvex jlink26例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 227V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1V2V4V8V5V3V6V728V1V2V4V5V3V7V6V8例例1例例1深度遍历深度遍历1：V1 V2 V4 V8 V5 V6 V3 V7 由于由于没有规定访问邻接点的顺序没有规定访问邻接点的顺序，所以深度优，所以深度优先序列不是唯一的。先序列不是唯一的

9、。例例1深度遍历深度遍历2：V1 V3 V7 V8 V6 V5 V2 V429V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V3 V6 V7 V530开始开始访问访问V,置置标志标志求求V邻接点邻接点有邻接点有邻接点w求下一邻接点求下一邻接点W访问过访问过结束结束NYNYDFS(G,w)开始开始标志数组初始化标志数组初始化V=0V访问过访问过?DFS(g,v)V=V+1VVexNum结束结束NYYN31V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V112341342vexdata firstarc 2 7 8 3adjvex next55 6 4

10、1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V432V1V2V4V5V3V7V6V8例例12341342vexdatafirstarc 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍历：深度遍历：V1V3 V7 V6 V2 V4 V8 V533V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V834开始开始标志数组初始化标志数组初始化V=0V访问过访问过BFSV=V+1VVexnum结束结束NYYN35开始开始访问访问V0,置置标志标志求求V邻接点邻接点ww存在吗

11、存在吗V下一邻接点下一邻接点ww访问过访问过结束结束NYNYBFS初始化队列初始化队列V0入队入队队列空吗队列空吗队头队头V出队出队访问访问w,置置标志标志w入队入队NY36例例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍历序列：遍历序列：10 1 2 3 4 54fr遍历序列：遍历序列：1 40 1 2 3 4 54 3fr遍历序列：遍历序列：1 4 337例例142350 1 2 3 4 54 3 2fr遍历序列：遍历序列：1 4 3 20 1 2 3 4 5 3 2fr遍

12、历序列：遍历序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍历序列：遍历序列：1 4 3 2 512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 238例例142350 1 2 3 4 5 2 5fr遍历序列：遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：遍历序列：1 4 3 2 512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 23940UV-U vu

13、U扩大扩大V-U缩小缩小vu 41V V3 3V V1 1V V4 4V V6 6V V5 5V V2 23 36 65 52 21 16 65 55 54 46 6V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 12 2V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14 4V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14 42 2V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14 45 52 2V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14

14、 45 53 3U= U= V1V1 U= U= V1,V3V1,V3 U= U= V1,V3,V6V1,V3,V6U= U= V1,V3,V6,V4V1,V3,V6,V4 U= U= V1,V3,V6,V4,V2V1,V3,V6,V4,V2 U= U= V1,V3,V6,V4,V2,V5V1,V3,V6,V4,V2,V5 4243V V3 3V V1 1V V4 4V V6 6V V5 5V V2 23 36 65 52 21 16 65 55 54 46 61654321234544V V3 3V V1 1V V4 4V V6 6V V5 5V V2 23 36 65 52 21 16 6

15、5 55 54 46 616543212345datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222采用边集数组的形式保存图：采用边集数组的形式保存图：45普里姆算法普里姆算法 克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名算法名适应范围464748C1C2C3C4C5C6C7C8C9C10C11C1249C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-

16、C4-C5-C7-C9-C10-C11-C6-C12-C8或或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一个一个AOV网的拓网的拓扑序列不是唯一的扑序列不是唯一的50C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C151C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C152C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1 -C253C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1 -C254C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑

17、序列：C1 -C2 -C355C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1 -C2 -C356C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C457C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C458C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C4-C559C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C4-C560C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C4-C5-C761C

18、6C7C8C9C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C4-C5-C762C6C8C9C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C4-C5-C7-C963C6C8C9C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C4-C5-C7-C964C6C8C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C4-C5-C7-C9-C1065C6C8C10C11C12拓扑序列：拓扑序列：C1 -C2 -C3 -C4-C5-C7-C9-C10-C11-C6 -C12-C8666732104例例1234560122inlink 5 5 4 3

19、vex next3 2 5 2 40123456top16toptop680122inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：输出序列：63210416toptopp2690122inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：输出序列：63210416topp21700122inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：输出序列：63210416P=NULL21top1710112inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：输出序列

20、：63210416P20top1720112inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：输出序列：63210446P20top1730112inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：输出序列：63210446P20top10740112inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：输出序列：63210443P20top10750112inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：输出序列：63210443P20top101P=NU

21、LL760112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：63210443P10top1013770111inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：63210443P10top1003780111inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：63210442P10top1003P=NULL790111inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6321044210top1003P=NUL

22、L2800111inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序列：632104400top1003P2 4810111inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序列：632104500top1003P2 4820111inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序列：632104500top1003P=NULL2 4830111inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序列：63210400top1003P=

23、NULL2 4 584V3V3V1V1V4V4V6V6V5V5V2V2a a4=34=3a a1=31=3a a2=22=2a a6=36=3a a5=45=4a a3=23=2a a7=27=2a a8=18=1顶点表示事件顶点表示事件边表示活动边表示活动事件事件VjVj发生发生表示表示 ak已结束已结束ak VjVi事件事件ViVi发生表示发生表示 ak可以开始可以开始 AOE网网858687在这条路径上，在这条路径上，必定只含一条必定只含一条弧到弧到V1，且，且这条弧的这条弧的权值最小。权值最小。 它只可能有两种情况：或者是它只可能有两种情况：或者是直接从源点到该点直接从源点到该点（只含

24、一条（只含一条弧）；或者是弧）；或者是从源点经过顶点从源点经过顶点v1，再到达该顶点，再到达该顶点（由两条弧（由两条弧组成）。组成）。它可能有三种情况：或者是它可能有三种情况：或者是直接从源点到该点直接从源点到该点（只含一条弧（只含一条弧）；或者是）；或者是从源点经过顶点从源点经过顶点v1v1，再到达该顶点，再到达该顶点（由两条弧组（由两条弧组成）；或者是成）；或者是从源点经过顶点从源点经过顶点v2v2，再到达该顶点，再到达该顶点。它或者是它或者是直接从源点到该点直接从源点到该点（只含一条弧）；（只含一条弧）； 或者是或者是从源从源点经过已求得最短路径的顶点，再到达该顶点。点经过已求得最短路径

25、的顶点，再到达该顶点。8889138 30 32V2:8终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6Vj51643208562301371732990138 30 32V2:813-1330 32V1:13终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6Vj51643208562301371732991138 30 32V2:813-1330 32V1:13-13302220V3:13终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6Vj516432085

26、62301371732992138 30 32V2:813-1330 32V1:13-13302220V3:13-192220V4:19终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6Vj51643208562301371732993138 30 32V2:813-1330 32V1:13-13302220V3:13-192220V4:19终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:2051643208562301371732994627543185623013717329017020605079032308130ad95627543185623013717329017020605079032308131addist0 1 2 3 4 5 60 13 8 3