Ⅰ Prim演算法的實現過程
G=（V,E）
①初始化：讀入的數據用鄰接矩陣x存儲，一個一維布爾型數組chosen，記錄第i個節點是否已選，初始值除1外全部設為false，記錄權值的變數cost賦值為0；
以下②到④循環執行v-1次（每次生成一條邊，運行（點的個數減1）次後，生成一棵最小生成樹）：
②臨時變數p賦值為無限大，用於記錄當前最小值；
③二重循環（外循環i，內循環j）掃描鄰接矩陣：如果chosen[i]=true（也就是說第i個點已選），那麼掃描x[i]，如果not(chosen[j])（也就是說第j個點未選），那麼如果x[i,j]<p，那麼p賦值為x[i,j],臨時變數q賦值為j;
④把cost賦值為cost+o，把chosen[q]賦值為true（也就是說第j個點已選）；
⑤輸出cost。
一、以上給出具體的運行過程。這個演算法的策略就是貪心，和dijkstra差不多，每次都選擇未選的邊中權值最小的那一條，直到生成最小生成樹。用chosen的目的就是保證生成過程中沒有環出現，也就是說保證選擇的邊不會通向一個已經包含在生成樹中的點。
二、這個只輸出最小生成樹的每條邊權值之和，如果要輸出整棵最小生成樹，加一個[1..n,1..2]的數組，在第④步的時候把每次選的邊記錄下來就可以了。
三、用小頂堆在第③步優化一下的話就不用每次都掃描那麼多邊了，只不過建堆維護堆代碼寫起來很麻煩。
四、prim適合用於比較稠密的網，點數和邊數差不多的時候效率很惡心，一般都用kruskal。
Ⅱ 題目1:一個簡單的演算法演示程序(java語言實現)
1. 選擇一個演算法（提供選擇見下），利用各種方法（圖形、動畫等）演示演算法的演示過程。
2. 可以進行手動演示，也可以自動步進式演示。
3. 允許用戶設置演算法的各個輸入參數，以及自動步進式演示中的時間間隔。
4. 不同的演算法輸入要求見下。
界面要求：
1. 盡量使用圖形界面實現，要符合日常軟體使用規范來設計菜單和界面。
2. 如果無法實現圖形界面，則在命令行方式下也需要提供菜單，方便用戶操作。
其他要求：
1. 標識符命名遵循Windows命名規范。
2. 能夠注意各種異常處理，注重提高程序運行效率。
提交內容：
1. 全部源代碼。
2. 軟體設計和使用說明書（UML類圖；實現的功能、主要技術；使用幫助文檔）
參考演算法：
1. 最小生成樹演算法：Prim演算法、Kruskal演算法。允許以下方式輸入一個圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。
2. 單源最短路演算法：Dijkstra演算法。允許以下方式輸入一個圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。
3. 最優編碼演算法：Huffman編碼演算法。允許用戶輸入一段英文文字，或者打開一個txt文檔（英文內容），據此文檔內容進行編碼。要求動態列出每個字元的出現概率統計結果以及對應編碼。
4. 其他可供演示的具有一定難度的演算法，如關鍵路徑問題、有向圖的極大連通分支等。
Ⅲ 普里姆演算法
可以這么理解：因為最小生成樹是包含所有頂點的所以開始lowcost先儲存到第一個點的所有值，然後執行下面演算法，找到最小值並記錄是第幾個點，比如說這個點是3，這樣有了一條1-3得道路已經確定，現在從3出發找從3出發到其他頂點的路徑，如果這個從3出發到達的路徑長度比從1出發的短，則更新lowcost，這樣使得lowcost保存一直到達該頂點的最短路徑。比如1-4是5，3-4是4，則lowcost從原來的5被改為4。
Ⅳ 普里姆演算法
測試結果:
610
123456
016
021
035
125
143
235
246
254
352
456
1---31
3---64
6---42
3---25
2---53
//圖最小生成樹Prim演算法
#include"stdio.h"
#include"stdlib.h"
#defineMAXVEX200
#defineINFINITY65535
typedefstruct
{
charvexs[MAXVEX];//頂點
intarc[MAXVEX][MAXVEX];//邊的權值
intnumVertexes;//頂點總數
intnumEdges;//邊的總數
}MGraph;
voidCreateMGraph(MGraph*G)/*構件圖*/
{
charstr[200];
intbeginVert,endVert,weight;
inti,j;
//輸入頂點總數,邊的總數
scanf("%d%d",&i,&j);
G->numVertexes=i;
G->numEdges=j;
//輸入頂點符號
scanf("%s",str);
for(i=0;i<G->numVertexes;i++)
{
G->vexs[i]=str[i];
}
for(i=0;i<G->numVertexes;i++)/*初始化圖*/
{
for(j=0;j<G->numVertexes;j++)
{
if(i==j)
{
G->arc[i][j]=0;
}
else
{
G->arc[i][j]=G->arc[j][i]=INFINITY;
}
}
}
//輸入所有邊的權值
for(i=0;i<G->numEdges;i++)
{
scanf("%d%d%d",&beginVert,&endVert,&weight);
G->arc[beginVert][endVert]=weight;
}
for(i=0;i<G->numVertexes;i++)
{
for(j=i;j<G->numVertexes;j++)
{
G->arc[j][i]=G->arc[i][j];
}
}
}
/*Prim演算法生成最小生成樹*/
voidMiniSpanTree_Prim(MGraphG)
{
intmin,i,j,k;
intadjvex[MAXVEX]; /*保存相關頂點下標*/
intlowcost[MAXVEX]; /*保存相關頂點間邊的權值*/
charbeginVert,endVert;
lowcost[0]=0;/*初始化第一個權值為0，即v0加入生成樹*/
/*lowcost的值為0，在這里就是此下標的頂點已經加入生成樹*/
adjvex[0]=0; /*初始化第一個頂點下標為0*/
for(i=1;i<G.numVertexes;i++) /*循環除下標為0外的全部頂點*/
{
lowcost[i]=G.arc[0][i]; /*將v0頂點與之有邊的權值存入數組*/
adjvex[i]=0; /*初始化都為v0的下標*/
}
for(i=1;i<G.numVertexes;i++)
{
min=INFINITY; /*初始化最小權值為∞，*/
/*通常設置為不可能的大數字如32767、65535等*/
j=1;k=0;
while(j<G.numVertexes) /*循環全部頂點*/
{
if(lowcost[j]!=0&&lowcost[j]<min)/*如果權值不為0且權值小於min*/
{
min=lowcost[j]; /*則讓當前權值成為最小值*/
k=j; /*將當前最小值的下標存入k*/
}
j++;
}
beginVert=G.vexs[adjvex[k]];
endVert=G.vexs[k];
//列印當前頂點邊中權值最小的邊
printf("%c---%c%d ",beginVert,endVert,min);
lowcost[k]=0;/*將當前頂點的權值設置為0,表示此頂點已經完成任務*/
for(j=1;j<G.numVertexes;j++) /*循環所有頂點*/
{
if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j])
{//如果下標為k頂點各邊權值小於此前這些頂點未被加入生成樹權值
lowcost[j]=G.arc[k][j];//將較小的權值存入lowcost相應位置
adjvex[j]=k; //將下標為k的頂點存入adjvex
}
}
}
}
intmain(void)
{
MGraphG;
CreateMGraph(&G);
MiniSpanTree_Prim(G);
return0;
}
Ⅳ 誰能幫我畫個PRIM演算法的流程圖
對於這種比較高級的演算法代碼直接看程序會比較蒙，你就光看我的演算法流程吧，prim演算法用的是貪心演算法的思想，即每一步都作出局部的最優解，關於prim演算法為什麼能用貪心演算法的證明，你可以參考《計算機演算法設計與分析》這本書。（我反正不想看那麼無聊的證明，也看不明白，呵呵）。
定義一個集合v 和 a，其中v是全體節點（總節點數為n）的集合，v初始為空。定義一個記錄最小生成數邊數的變數c。
1.在v中任選一個節點，並加入到a中。在v中刪除該節點。
2.選一個在所有連接v集合和a集合權值最小的邊（即一個節點是v的某一個節點，一個是a中的某一個節點）
3。將兩個節點連接。將c加1
4.將第3步才在v中節點刪除並加入到a中.
5.如果c為n-1則完成最小生成樹，否則回到第2步。
明白了沒？不明白再問我啊，希望對你有所幫助。
Ⅵ cs61b實驗記錄（三）project 2 prim迷宮隨機生成演算法
nothing special
具體詳見我的GitHub： https://github.com/BoL0150/Berkeley-cs61b/tree/main/hw1
Random對象是一個「偽隨機數」生成器，它可以產生一串無窮的看起來是隨機數的數字序列，調用nextInt方法獲取序列中的每一個數字。
它之所以叫「偽隨機數」是因為它產生的序列並不是真正隨機的。我們獲取不同的序列的方式是向Random的構造器中傳入一個數字，這個數字被稱為「seed」，如果我們用相同的seed構造Random，那麼我們一定會獲得完全相同的序列。
java.lang.Math中也有一個名為random()的靜態方法可以生成隨機數
Math.random() 方法生成[0, 1)范圍內的double類型隨機數；Random類中的nextXxxx(n)系列方法生成0（包括）到n（不包括）之間的隨機數；
繪制地圖：
從宏觀上來看，主要分為這么幾步：
創建一個Room類，將每一個房間當作一個對象，隨機生成房間的坐標以及長和寬，然後判斷房間是否重疊，
同時設置一個參數，控制房間重復生成的上限次數。 將所有生成的房間對象放在一個List中 ，因為在修建完迷宮後還需要對每一個房間與它旁邊的迷宮進行打通，以便獲取房間的位置和參數。
此時在房間中填GRASS以及使用兩個數組的原因稍後進行解釋。
我們將這一步分解來看，首先：如何在一張空的圖上生成迷宮？
我們採用 prim迷宮隨機生成演算法 ，此演算法的原理及具體實現如下：
原理：
具體實現：
生成迷宮時要注意 隨機 從候選列表中選取點，否則生成的迷宮會朝著同一個方向
我們知道了如何在空的圖上生成迷宮，也可以由此推斷出如何在房間的周圍生成迷宮
這一步沒什麼好說的，對每一個房間隨機選取一條邊上的一點向外打通，如果不符合條件（如碰到NOTHING等）就重新選取一點。
然而，此時的圖中還有很多的死胡同（即三面都是牆的FLOOR），以及房間中依然是GRASS，所以我們需要填補所有的死胡同，將GRASS替換為FLOOR。
去除死胡同我們需要對每一個點，查看周圍的四個點是否是WALL，然後改變這個點，再進入下一個點。這會讓人想起DFS，但是原本的DFS是沿著一條路線，從一頭走到另一頭，對路上的每一個點都只是 依次 查看周圍的點，一旦找到可以通過的點，就立馬進入， 無法確定這一點周圍是否有3個WALL 。只有當走到頭時，掃描了周圍的四個點，發現都無法通過，才會往後退。也就是說，只有後退的時候，我們才能知道某一點周圍所有點的情況。而填補所有的死胡同需要我們從所有的死胡同的終點出發，向中間匯聚，一邊移動一邊填補。
所以我們需要將DFS改造成 前進和後退時都要查看周圍所有點的情況 ，才能進行下一步。
我們還需要移除所有多餘的牆，也就是四個角上沒有FLOOR的WALL
最後，再添加上Player和Lock_Door就完成了
附上autograder的評分
Ⅶ 利用Prim（普里姆）演算法 構造最小生成樹 程序
演算法同樣是解決最小生成樹的問題。
其演算法為：在這n個點中的相通的邊進行排序，然後不斷地將邊添加到集合中（體現了貪心的演算法特點），在並入集合之前，必須檢查一下這兩點是不是在一個集合當中，這就用到了並查集的知識。直到邊的集合達到了n-1個。
與prim演算法的不同：prim演算法為單源不斷尋找連接的最短邊，向外擴展，即單樹形成森林。而Kruskal演算法則是不斷尋找最短邊然後不斷將集合合並，即多樹形成森林。
復雜度的不同：prim演算法的復雜度是O(n^2),其中n為點的個數。Kruskal演算法的復雜度是O(e*loge)，其中e為邊的個數。兩者各有優劣，在不同的情況下選擇不同的演算法。
Prim演算法用於求無向圖的最小生成樹
設圖G =（V，E），其生成樹的頂點集合為U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。
③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。
其演算法的時間復雜度為O(n^2)
Prim演算法實現：
（1）集合：設置一個數組set(i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）
（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
{先選定一個點，然後從該點出發，與該點相連的點取權值最小者歸入集合，然後再比較在集合中的兩點與其它各點的邊的權值最小者，再次進入集合，一直到將所有的點都歸入集合為止。}
Ⅷ 有什麼無權無向圖的最短路徑演算法比較好，求一個用java實現的
有什麼無權無向圖的最短路徑演算法比較好
帶權圖也分有向和無向兩種，基本的演算法可以看看書咯。 帶權的無向圖的最短路徑又叫最小生成樹，Prim演算法和Kruskal演算法； 帶權的有向圖的最短路徑演算法有迪傑斯特拉演算法和佛洛依德演算法；
String[]s={"January","February","March","April","May","June","July","August","September","October","November","December"};
System.out.print("請輸入數字（1-12）：");
BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
Stringstr=br.readLine();
intm=Integer.parseInt(str);
if(m<=0||m>=13)
{
Ⅸ 一個簡單的演算法演示程序(JAVA語言實現)
這么大的程序起碼得寫好幾天呢 樓主就給十分啊……