计算机算法技术总结.ppt

人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 第二章 图与遍历算法 基本概念和术语 二叉树与遍历算法 双连通与网络可靠性 对策树 图的基本概念和术语 图是一个用（边）连结节点（顶点）的结构. 三元素：顶点集、边集、关联关系 G=( V,E,I) 术语：顶点与边关联、边的端点、顶点的度、简单图、完全图、偶图、k-部图、途径、迹、路、圈、连通 Euler公式： 哥尼斯堡七桥 Euler图 图的邻接矩阵和关联矩阵 图G=(V,E,I) , 邻接矩阵 关联矩阵 右边的图不是连通的，有两个连通分支。它含有两个圈，不是树。 有7个顶点和7条边的图 上图的邻接矩阵与关联矩阵 e5 e6 e7 e4 6 4 5 7 e1 1 e2 e3 3 2 树的性质 定义 不含圈的连通图称为树。对于连通图，适当去掉一些边后，会得到一个不含圈、而且包含所有顶点的连通图， 它是一棵树，称为原图的生成树。 森林是由若干棵树构成的图。 定理 如果G是具有n个顶点、m条边的图，则下列结论立： 1. 若G是树， 则m = n-1； 2. 若G是连通图，而且满足m = n-1，则G是树； 3. 若G不包含圈，而且满足m = n-1，则G是树； 4. 若G是连通图，则m ? n-1; 5. 若G是由k棵树构成的森林，则m = n-k ； 6. 若G有k个连通分支，而且满足m = n-k，则G是森林; 7. 若G有k个连通分支，则m ? n-k。 有向图 有向图 ; 有向边 ; 出(入)度 ( ); Euler 公式 有向途径、有向迹、有向路，有向圈，双向连通（强连通） 邻接矩阵 关联矩阵 2 3 4 5 6 1 e1 e2 e3 e4 e5 e6 e7 e8 赋权图 赋权图是将图的每个边都赋予一个权值，表示成本、效益值、容量、流量等。 赋权图的邻接矩阵的 - 元素为连结顶点 ， 的权值。当顶点 ， 没有边连结时，可根据问题需要，取 或 等。 一个赋权图 上图的一个最优生成树 2 6 2 3 1 6 6 2 6 3 7 2 3 1 3 6 8 3 1 2 4 3 5 6 7 图的邻接链表 1 2 3 4 (a) (b) 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 2 3 4 1 2 3 4 9 8 7 6 5 2 4 0 Vertex 1 3 0 Vertex 2 Vertex 3 Empty list 2 3 0 Vertex 4 (c) (d) Vertices Edges 5 7 0 8 2 6 4 0 3 0 2 9