最小生成樹算法

　　連通圖：在無向圖G中，若從頂點(diǎn)i到頂點(diǎn)j有路徑，則稱頂點(diǎn)i和頂點(diǎn)j是連通的。若圖G中任意兩個(gè)頂點(diǎn)都連通，則稱G為連通圖。

　　生成樹：一個(gè)連通圖的生成樹是該連通圖的一個(gè)極小連通子圖，它含有全部頂點(diǎn)，但只有構(gòu)成一個(gè)數(shù)的(n-1)條邊。

　　最小生成樹：對于一個(gè)帶權(quán)連通無向圖G中的不同生成樹，各樹的邊上的權(quán)值之和最小。構(gòu)造最小生成樹的準(zhǔn)則有三條：

　　必須只使用該圖中的邊來構(gòu)造最小生成樹。

　　必須使用且僅使用(n-1)條邊來連接圖中的n個(gè)頂點(diǎn)。

　　不能使用產(chǎn)生回路的邊。

　　Prim算法

　　假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖，T(U,TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，則由G構(gòu)造從起始頂點(diǎn)v出發(fā)的最小生成樹T的步驟為：

　　初始化U={v}，以v到其他頂點(diǎn)的所有邊為候選邊(U中所有點(diǎn)到其他頂點(diǎn)的邊)。

　　重復(fù)以下步驟(n-1)次，使得其他(n-1)個(gè)頂點(diǎn)被加入到U中。

　　從候選邊中挑選權(quán)值最小的邊加入TE，設(shè)該邊在V-U(這里是集合減)中的頂點(diǎn)是k，將k加入U(xiǎn)中。

　　考察當(dāng)前V-U中的所有頂點(diǎn)j，修改候選邊，若邊(k,j)的權(quán)值小于原來和頂點(diǎn)j關(guān)聯(lián)的候選邊，則用(k,j)取代后者作為候選邊。

　　Kruskal算法

　　假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖，T(U,TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，則由G構(gòu)造從起始頂點(diǎn)v出發(fā)的最小生成樹T的步驟為：

　　置U的初始值等于V(即包含G中的全部頂點(diǎn))，TE的初始值為空

　　將圖G中的邊按權(quán)值從小到大的順序依次選取，若選取的邊未使生成樹T形成回路，則加入TE，否則放棄，知道TE中包含(n-1)條邊為止。

　　Dijkstra——貪心算法

　　從一個(gè)頂點(diǎn)到其余頂點(diǎn)的最短路徑

　　設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第1組為已求出最短路徑的頂點(diǎn)（用S表示，初始時(shí)S只有一個(gè)源點(diǎn)，以后每求得一條最短路徑v,...k，就將k加到集合S中，直到全部頂點(diǎn)都加入S）。第2組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長度的遞增次序把第2組的頂點(diǎn)加入S中。

　　步驟：

　　初始時(shí)，S只包含源點(diǎn)，即S={v}，頂點(diǎn)v到自己的距離為0。U包含除v外的其他頂點(diǎn)，v到U中頂點(diǎn)i的距離為邊上的權(quán)。

　　從U中選取一個(gè)頂點(diǎn)u，頂點(diǎn)v到u的距離最小，然后把頂點(diǎn)u加入S中。

　　以頂點(diǎn)u為新考慮的中間點(diǎn)，修改v到U中各個(gè)點(diǎn)的距離。

　　重復(fù)以上步驟知道S包含所有頂點(diǎn)。

　　ASL

　　由于查找算法的主要運(yùn)算是關(guān)鍵字的比較，所以通常把查找過程中對關(guān)鍵字的平均比較次數(shù)（平均查找長度）作為衡量一個(gè)查找算法效率的標(biāo)準(zhǔn)。ASL=∑(n,i=1)Pi*Ci，其中n為元素個(gè)數(shù)，Pi是查找第i個(gè)元素的概率，一般為Pi=1/n，Ci是找到第i個(gè)元素所需比較的次數(shù)。

　　順序查找

　　原理是讓關(guān)鍵字與隊(duì)列中的數(shù)從最后一個(gè)開始逐個(gè)比較，直到找出與給定關(guān)鍵字相同的數(shù)為止，它的缺點(diǎn)是效率低下。時(shí)間復(fù)雜度o(n)。

　   以上就是動(dòng)力節(jié)點(diǎn)Java培訓(xùn)機(jī)構(gòu)小編介紹的“2020年Java常見算法筆試題”的內(nèi)容，希望對大家有幫助，如有疑問，請?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。