最小生成樹算法

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

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

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

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

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

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

　　Prim算法

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

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

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

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

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

　　Kruskal算法

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

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

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

　　Dijkstra——貪心算法

　　從一個頂點到其余頂點的最短路徑

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

　　步驟：

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

　　從U中選取一個頂點u，頂點v到u的距離最小，然后把頂點u加入S中。

　　以頂點u為新考慮的中間點，修改v到U中各個點的距離。

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

　　ASL

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

　　順序查找

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

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