ACM培训资料数据结构与算法学习教案

1、会计学1ACM培训资料数据结构与算法培训资料数据结构与算法2第1页/共73页叫做边叫做边(edge)集合。集合。Path (x, y)表表示从示从 x 到到 y 的一条通路。的一条通路。3第2页/共73页4第3页/共73页5第4页/共73页6第5页/共73页7第6页/共73页例例157324G26例例245136G1路径：路径：1，2，3，5，6，3路径长度：路径长度：5简单路径：简单路径：1，2，3，5回路：回路：1，2，3，5，6，3，1简单回路：简单回路：3，5，6，3路径：路径：1，2，5，7，6，5，2，3路径长度：路径长度：7简单路径：简单路径：1，2，5，7，6回路：回路：1，2

2、，5，7，6，5，2，1简单回路：简单回路：1，2，3，18第7页/共73页9第8页/共73页10第9页/共73页11第10页/共73页12第11页/共73页13第12页/共73页14第13页/共73页例例G1bdac1234acdbvexdatafirstarc 4 1 1 3adjvexnext15第14页/共73页16第15页/共73页17第16页/共73页18第17页/共73页mark ivex ilink jvex jlinkdata firstedge19第18页/共73页例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 220第19页/共73页i 为

3、为 1，防止它被多次访问。，防止它被多次访问。21第20页/共73页22第21页/共73页例例V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V3 V6 V7 V523第22页/共73页遍历结果：遍历结果：A A、B B、D D、C C例例24第23页/共73页邻接表：是以邻接表：是以G.verticesi为表头为表头结点的单链表上的所有结点。结点的单链表上的所有结点。25第24页/共73页V1V2V4V5V3V7V6V8例例1234V1V3V4V2vexdataf

4、irstarc 2 7 8 3adjvexnext5V5 6 4 8 2V6V7V8678 7深度遍历：深度遍历：V1V3 V7 V6 V2 V4 V8 V526第25页/共73页27第26页/共73页28第27页/共73页例例V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V6 V7 V8 V529第28页/共73页遍历结果：遍历结果：A A、B B、C C、D D例例30第29页/共73页开始开始标志数组初始化标志数组初始化Vi=1Vi访问过访问过BFSVi=V

5、i+1Vi=Vexnums结束结束NNYY31第30页/共73页开始开始访问访问Vi,置置标志标志求求V邻接点邻接点WW存在吗存在吗V下一邻接点下一邻接点WW访问过访问过结束结束NYNY初始化队列初始化队列Vi入队入队队列空吗队列空吗队头队头V出队出队访问访问W,置置标志标志W入队入队NaaY32第31页/共73页33第32页/共73页强连通分量强连通分量。34第33页/共73页连通图连通图例例245136强连通图强连通图356例例非连通图非连通图连通分量连通分量例例24513635第34页/共73页36第35页/共73页 含含n个顶点个顶点n-1条边的图不一定条边的图不一定是生成树是生成树G

6、HKI37第36页/共73页V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V838第37页/共73页例例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林39第38页/共73页165432713179181275241040第39页/共73页最小生成树的重要性质：

7、最小生成树的重要性质： 设设 G =G =（V V，E E）是一个连通网络，）是一个连通网络，U U是顶点集是顶点集V V的的一个真子集。若（一个真子集。若（u u，v v）是）是G G中所有的一个顶点在中所有的一个顶点在U,U,另另一个顶点不在一个顶点不在 U U 的边中，的边中，具有最小权值具有最小权值的一条边，则的一条边，则一定存在一定存在 G G 的一棵最小生成树包括此边。的一棵最小生成树包括此边。uvUVU41第40页/共73页42第41页/共73页 上述算法的初始化时间是上述算法的初始化时间是O(1)O(1)，k k循环中有两个循循环中有两个循环语句，其时间大致为：环语句，其时间大

8、致为： 令令O(1)O(1)为某一正常数为某一正常数C C，展开上述求和公式可知其，展开上述求和公式可知其数量级仍是数量级仍是 n n 的平方。所以，整个算法的时间复杂性的平方。所以，整个算法的时间复杂性是是O(nO(n2 2) )43第42页/共73页同一个连通分量上为止。同一个连通分量上为止。44第43页/共73页例例16543265135664251654321234545第44页/共73页46第45页/共73页47第46页/共73页学生课程学习工程图学生课程学习工程图48第47页/共73页49第48页/共73页50第49页/共73页51第50页/共73页52第51页/共73页C0C1C

9、2C3C4C5(a) 有向无环图有向无环图(b) 输出顶点输出顶点C4(c) 输出顶点输出顶点C0C2C5C1C0C3C4C1C2C5C3C0C2C5C1C3(d) 输出顶点输出顶点C353第52页/共73页C1C2C5(e) 输出顶点输出顶点C2C5C1(f) 输出顶点输出顶点C1C5(g) 输出顶点输出顶点C5(h) 拓扑排序完成拓扑排序完成54第53页/共73页C0C1C2C3C4C5 dest next C0 C1 C2 C3 0 C4 C5 0012345count data adj 130103 1 3 0 5 1 5 0 0 1 5 055第54页/共73页56第55页/共73页57第56页/共73页58第57页/共73页59第58页/共73页60第59页/共73页1324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8