其他常用知识和算法new

《其他常用知识和算法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、PASCAL语言教程第九章其他常用知识和算法  本章将抛砖引玉地探讨一些程序设计中常用的知识及算法，包括图论及其基本应用，动态规划等。要想对这些问题进行深一步地研究，可以系统地学习图论、组合数学、运筹学等书籍。 第一节　图论及其基本算法   图是另一种有层次关系的非线性的数据结构。在日常生活中有图的许多实例，如铁路交通网，客运航空线示意图，化学结构式，比赛安排表等。下面的如几个例子都可称为图。在实际运用中，我们可以用图来表示事物间相互的关系，从而根据需要灵活地构建数学模型。例如：图(A)，可以用点来表示人，如果两个人相互认识，则在表示这两个人的点之间连一条线。这

2、样从图中我们就可以清楚地看到，这些人之间相互认识的关系。图(B)：可以用点表示城市，若两城市间有连线则表示可在这两城市架设通信线路，线旁的数字表示架设这条线路的费用。图(C)：4个点表示4支足球队，它们进行循环比赛，若甲队胜乙队，则连一条由甲队指向乙队的有向线段。在上面三个例子中，(A)，(B)又可称为无向图，(C)称为有向图，其中(B)是一个有权图。  图常用的存储方式有两种，一种是邻接表法，另一种是邻接矩阵法。  邻接表表示图有两个部分：一部分表示某点的信息，另一部分表示与该点相连的点。例如：图A的邻接表如下所示：   ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌

3、─┬─┐   │v1│─┼→│v2│─┼→│v3│─┼→│v4│^│   └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘   ┌─┬─┐ ┌─┬─┐ ┌─┬─┐               │v2│─┼→│v1│─┼→│v3│^│               └─┴─┘ └─┴─┘ └─┴─┘               ┌─┬─┐ ┌─┬─┐ ┌─┬─┐               │v3│─┼→│v1│─┼→│v2│^│               └─┴─┘ └─┴─┘ └─┴─┘                ┌─┬─┐ ┌─┬─┐           

4、                │v4│─┼→│v1│^│                           └─┴─┘ └─┴─┘                         邻接矩阵是用一个二维数组表示图的有关信息，比如图A的邻接矩阵为：       ┌─┬─┬─┬─┬─┐                    │点│v1│v2│v3│v4│                    ├─┼─┼─┼─┼─┤                    │v1│0│1│1│1│                    ├─┼─┼─┼─┼─┤             

5、       │v2│1│0│1│0│                    ├─┼─┼─┼─┼─┤                    │v3│1│1│0│0│                    ├─┼─┼─┼─┼─┤                    │v4│1│0│0│0│                    └─┴─┴─┴─┴─┘               在邻接矩阵中，第i行第j表示图中点i和点j之间是否有连线，若有则值为1，否则为0。比如说：点v1和v2之间有连线，则矩阵的第一行第二列的值为1。而矩阵的第四行行三列的值为0说明图中点v4

6、和v3之间没有连线。图A是一个无向图，它的邻接矩阵是一个关于主对角线对称的矩阵。而有向图的邻接矩阵则不一定是对称的。比如图C的邻接矩阵为：        ┌─┬─┬─┬─┬─┐                     │点│v1│v2│v3│v4│                     ├─┼─┼─┼─┼─┤                     │v1│0│1│1│1│                     ├─┼─┼─┼─┼─┤                     │v2│0│0│1│1│                     ├─┼─┼─┼─┼

7、─┤                     │v3│0│0│0│0│                     ├─┼─┼─┼─┼─┤                     │v4│0│0│1│0│                     └─┴─┴─┴─┴─┘             例一、图的遍历：请编一个程序对下图进行遍历。分析："遍历"是指从图的某个点出发，沿着与之相连的边访问图中的每个一次且仅一次。基本方法有两种：深度优先遍历和广度优先遍历。   深度优先和广度优先遍历，与前面所说的树的深度与广度优先遍历是类似的：比下图中，如果从点V1出发，那么： 

8、  深度优先遍历各点的顺