实验一-可行遍性问题

1、实验一 可行遍性问题可行遍性问题是指下述两类问题：1.是否可以从图G的任何一个顶点出发，不重复的行遍所有边。如果可以，则图中必有一条路（回路），经过各条边恰好一次，这条路（回路）称为欧拉路（回路）（欧拉图）。2.是否可以从图中的任意一个顶点出发，不重复的行遍所有的顶点。如果可以，则图中必有一条道路（圈），经过每个顶点恰好一次，这条道路（圈）称为哈密顿通路（圈）（哈密顿图）。一、深度优先搜索二、广度优先搜索 一、图的遍历遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。图的特点：

2、图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。解决思路：可设置一个辅助数组 ，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited i为1，防止它被多次访问。图常用的遍历：怎样避免重复访问？一、深度优先搜索( DFS )基本思想：仿树的先序遍历过程。Depth_First Searchv1v1v2v3v8v7v6v4v5DFS 结果例1：v2v4v8v5v3v6v7例2：v2 v1 v3 v5 DFS 结果v4 v6起点起点遍历步骤应退回到V8，因为V2已有标记深

3、度优先搜索（遍历）步骤：详细归纳：在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2；然后再从 w2 出发，进行类似的访问， 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它未被访问的邻接顶点。 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问； 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。简单归纳： 访问起始点 v; 若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再

4、找v的第2个邻接点重新遍历。讨论1：计算机如何实现DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS 结果邻接矩阵A辅助数组 visited n 起点开辅助数组 visited n ！例：123456101110021000103100010410000150110006000100v2v1v3v5v4v6请注意逐级回退是递归概念for( j=1; ja=0:10;a*5ans= 0 5 10 15 20 25 30 35 40 45 50

5、3.向量乘法向量与向量乘法称为向量乘法，运算规则为向量的相应元素分别相乘，运算指令为A.*Ba=0:10;b=1:11;a.*bans= 0 2 6 12 20 30 42 56 72 90 110注意：向量相乘中，相乘向量必须大小相同4.向量除法向量除的指令分别为：A./B:向量右除，A和B对应元素相除A.B:向量左除，B和A对应元素相除 与数组乘法相同，数组除法中运算的数组大小必须相同。A=1:5;B=6:10;A./Bans= 0.1667 0.2857 0.3750 0.4444 0.5000A.Bans= 6.0000 3.5000 2.6667 2.2500 2.00005.乘方运

6、算乘方指令为A.B,就是A和B对应元素的乘方。A=1:5;B=6:10;C=2;A.Bans= 1 128 6561 262144 9765625A.Cans= 1 4 9 16 25C.Aans= 2 4 8 16 321.矩阵操作矩阵运算1.加减运算2.矩阵乘法3.矩阵除法4.矩阵转秩1.加减运算矩阵加减运算规则和数组相同，指令为A+B,A-B2.矩阵乘法矩阵相乘指令A*B，运算规则为线性运算规则。A的行数必须和B的列数相同。A=magic(3);B=ones(3);A*Bans= 15 15 15 15 15 15 15 15 15 3.矩阵除法矩阵的除法分为左除和右除。矩阵除法遵从线性

7、运算规则。A/B:左除AB:右除A=magic(3);B=1:3;4:6;7:9;ABans= 0.0167 0.0833 0.1500 0.7667 0.8333 0.9000 0.0167 0.0833 0.1500B/Aans= -0.0333 0.4667 -0.0333 0.1667 0.6667 0.1667 0.3667 0.8667 0.36674.矩阵转秩矩阵的转秩运算指令为AA=magic(3);Aans= 8 3 4 1 5 9 6 7 2 5.Matlab运算符算术运算符关系运算符逻辑运算符特殊运算符算术运算符加法减法乘法除法关系运算符小于：AB小于等于：=等于：=不等

8、于：=逻辑运算符逻辑与：A&B进行逻辑与运算，如果都不为0则返回1，否则返回0逻辑非：A，如果A非零则返回0，否则返回1逻辑或：A|B，有一个非零返回1，否则返回0逻辑异或：xor(A,B),如果一个非零，一个为零返回结果为1，否则为0特殊运算符冒号(:)：创建数组，访问数组的特定行、列或元素句点(.)：M文件编写Function = 程序命名为.m多个因变量时，要用将所有因变量括起来Eg. Functione,d=tree(P,C)流程控制For循环：允许一组命令以固定和预定的次数重复，循环一般形式是： for x=array commands endWhile循环：以不定的次数循环求一组语句的值while expression commands end If-else-end: if expression commands else express