實驗一-可行遍性問題

1、實驗一 可行遍性問題可行遍性問題是指下述兩類問題：1.是否可以從圖G的任何一個頂點出發(fā)，不重復(fù)的行遍所有邊。如果可以，則圖中必有一條路（回路），經(jīng)過各條邊恰好一次，這條路（回路）稱為歐拉路（回路）（歐拉圖）。2.是否可以從圖中的任意一個頂點出發(fā)，不重復(fù)的行遍所有的頂點。如果可以，則圖中必有一條道路（圈），經(jīng)過每個頂點恰好一次，這條道路（圈）稱為哈密頓通路（圈）（哈密頓圖）。一、深度優(yōu)先搜索二、廣度優(yōu)先搜索 一、圖的遍歷遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。遍歷實質(zhì)：找每個頂點的鄰接點的過程。圖的特點：

2、圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。解決思路：可設(shè)置一個輔助數(shù)組 ，用來標(biāo)記每個被訪問過的頂點。它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個頂點i 被訪問，就立即改 visited i為1，防止它被多次訪問。圖常用的遍歷：怎樣避免重復(fù)訪問？一、深度優(yōu)先搜索( DFS )基本思想：仿樹的先序遍歷過程。Depth_First Searchv1v1v2v3v8v7v6v4v5DFS 結(jié)果例1：v2v4v8v5v3v6v7例2：v2 v1 v3 v5 DFS 結(jié)果v4 v6起點起點遍歷步驟應(yīng)退回到V8，因為V2已有標(biāo)記深

3、度優(yōu)先搜索（遍歷）步驟：詳細歸納：在訪問圖中某一起始頂點 v 后，由 v 出發(fā)，訪問它的任一鄰接頂點 w1；再從 w1 出發(fā)，訪問與 w1鄰接但還未被訪問過的頂點 w2；然后再從 w2 出發(fā)，進行類似的訪問， 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它未被訪問的鄰接頂點。 如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問； 如果沒有，就再退回一步進行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。簡單歸納： 訪問起始點 v; 若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點；若當(dāng)前鄰接點已訪問過，再

4、找v的第2個鄰接點重新遍歷。討論1：計算機如何實現(xiàn)DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS 結(jié)果鄰接矩陣A輔助數(shù)組 visited n 起點開輔助數(shù)組 visited n ！例：123456101110021000103100010410000150110006000100v2v1v3v5v4v6請注意逐級回退是遞歸概念for( j=1; ja=0:10;a*5ans= 0 5 10 15 20 25 30 35 40 45 50

5、3.向量乘法向量與向量乘法稱為向量乘法，運算規(guī)則為向量的相應(yīng)元素分別相乘，運算指令為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對應(yīng)元素相除A.B:向量左除，B和A對應(yīng)元素相除 與數(shù)組乘法相同，數(shù)組除法中運算的數(shù)組大小必須相同。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對應(yīng)元素的乘方。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.矩陣轉(zhuǎn)秩1.加減運算矩陣加減運算規(guī)則和數(shù)組相同，指令為A+B,A-B2.矩陣乘法矩陣相乘指令A(yù)*B，運算規(guī)則為線性運算規(guī)則。A的行數(shù)必須和B的列數(shù)相同。A=magic(3);B=ones(3);A*Bans= 15 15 15 15 15 15 15 15 15 3.矩陣除法矩陣的除法分為左除和右除。矩陣除法遵從線性

7、運算規(guī)則。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.矩陣轉(zhuǎn)秩矩陣的轉(zhuǎn)秩運算指令為AA=magic(3);Aans= 8 3 4 1 5 9 6 7 2 5.Matlab運算符算術(shù)運算符關(guān)系運算符邏輯運算符特殊運算符算術(shù)運算符加法減法乘法除法關(guān)系運算符小于：AB小于等于：=等于：=不等

8、于：=邏輯運算符邏輯與：A&B進行邏輯與運算，如果都不為0則返回1，否則返回0邏輯非：A，如果A非零則返回0，否則返回1邏輯或：A|B，有一個非零返回1，否則返回0邏輯異或：xor(A,B),如果一個非零，一個為零返回結(jié)果為1，否則為0特殊運算符冒號(:)：創(chuàng)建數(shù)組，訪問數(shù)組的特定行、列或元素句點(.)：M文件編寫Function = 程序命名為.m多個因變量時，要用將所有因變量括起來Eg. Functione,d=tree(P,C)流程控制For循環(huán)：允許一組命令以固定和預(yù)定的次數(shù)重復(fù)，循環(huán)一般形式是： for x=array commands endWhile循環(huán)：以不定的次數(shù)循環(huán)求一組語句的值while expression commands end If-else-end: if expression commands else express