迷宮生成演算法prim

㈠ prim演算法是什麼

prim演算法是：圖論中的一種演算法。

普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。

該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；並在1957年由美國計算機科學家羅伯特·普里姆（英語：Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆－亞爾尼克演算法。

通過鄰接矩陣圖表示的簡易實現中，找到所有最小權邊共需O（V）的運行時間。使用簡單的二叉堆與鄰接表來表示的話，普里姆演算法的運行時間則可縮減為O(ElogV)，其中E為連通圖的邊數，V為頂點數。如果使用較為復雜的斐波那契堆，則可將運行時間進一步縮短為O(E+VlogV)，這在連通圖足夠密集時（當E滿足Ω（VlogV）條件時），可較顯著地提高運行速度。

㈡ 迷宮演算法復雜度如何計算

迷宮生成可以O(n*m)完成。走迷宮的話可以O(n*m*2)左右。
只要記錄走到每一格的最優解就可以了。
最好不要用深度優先搜索。用廣度優先的實現方便。

㈢ 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。

㈣ Prim和Dijkstra演算法的區別

在圖論中，Prim演算法是計算最小生成樹的演算法，而Dijkstra演算法是計算最短路徑的演算法。二者看起來比較類似，因為假設全部頂點的集合是V，已經被挑選出來的點的集合是U，那麼二者都是從集合V-U中不斷的挑選權值最低的點加入U，那麼二者是否等價呢？也就是說是否Dijkstra也可以計算出最小生成樹而Prim也可以計算出從第一個頂點v0到其他點的最短路徑呢？答案是否定的，否則就不必有兩個演算法了。
二者的不同之處在於「權值最低」的定義不同，Prim的「權值最低」是相對於U中的任意一點而言的，也就是把U中的點看成一個整體，每次尋找V-U中跟U的距離最小（也就是跟U中任意一點的距離最小）的一點加入U；而Dijkstra的「權值最低」是相對於v0而言的，也就是每次尋找V-U中跟v0的距離最小的一點加入U。
一個可以說明二者不等價的例子是有四個頂點(v0, v1, v2, v3)和四條邊且邊值定義為(v0, v1)=20, (v0, v2)=10, (v1, v3)=2, (v3, v2)=15的圖，用Prim演算法得到的最小生成樹中v0跟v1是不直接相連的，也就是在最小生成樹中v0v1的距離是v0->v2->v3->v1的距離是27，而用Dijkstra演算法得到的v0v1的距離是20，也就是二者直接連線的長度。

㈤ 「prim」 演算法 是誰最先提出在那篇著作裡面提出來的對現在有什麼意義有什麼應用最好詳細點。謝謝

Prim演算法是圖論中求最小生成樹的一種演算法，最早於1930年由捷克數學家Vojtěch Jarník發現；並在1957年由美國計算機科學家Robert C. Prim獨立發現，1959年Edsger Dijkstra再次發現了該演算法，參見論文：
R. C. Prim. Shortest Connection Networks And Some Generalizations
JOSEPH B. KRUSKAL, JR. ON THE SHORTEST SPANNING SUBTREE OF A GRAPH AND THE TRAVELING SALESMAN PROBLEM
該演算法用於求解圖的最小生成樹，所有可轉換為求圖的最小生成樹的問題的應用均可以應用Prim演算法來解決，他本人的論文里也提及了部分應用。

㈥ Prim演算法，求大牛通俗易懂地解釋下為什麼成立。。。

prim演算法就是把點分成兩個集合，一個集合裡麵包含已經加入生成樹的點，另一個包含未加入的，然後不斷在兩個集合之間找最短的邊，直到所有的點都加入到生成樹中，這時候就構成了最小生成樹。

㈦ Prim演算法為什麼能保證迷宮有唯一通路

為了減少不必要的麻煩，可以不妨設圖中所有邊的權重都不同，這樣最小生成樹是唯一的
然後直接用反證法就行了
如果Prim演算法得到G，而最小生成樹是T
設在生成G的過程中第一次產生的不在T中的邊是e，而在G中去掉e得到的兩個連通分支記為V1和V2，那麼e連接了V1和V2

把e加入T之後會出現環，在這個環裡面V1的頂點和V2的頂點至少還被另一條邊f連接（否則T本身就不連通了），由Prim演算法的貪心策略可知e比f權重低，那麼在T裡面把f換成e可得一個總權重更小的生成樹，與T的最小性矛盾

（因為最小生成樹的總權重的邊的權重的連續函數，對於有權重重復出現的情況可以利用連續性取極限，這樣即使最小生成樹不唯一仍然可以保證Prim演算法生成的樹具有最小權重）

㈧ 什麼是Prim演算法

Prim演算法
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](i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）
（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。

參考程序

/* Prim.c

Copyright (c) 2002, 2006 by ctu_85

All Rights Reserved.

*/

/* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */

#include "stdio.h"

#define maxver 10

#define maxright 100

int main()

{

int G[maxver][maxver],in[maxver]=,path[maxver][2];

int i,j,k,min=maxright;

int v1,v2,num,temp,status=0,start=0;

restart:

printf("Please enter the number of vertex(s) in the graph:\n");

scanf("%d",&num);

if(num>maxver||num<0)

{

printf("Error!Please reinput!\n");

goto restart;

}

for(j=0;j<num;j++)

for(k=0;k<num;k++)

{

if(j==k)

G[j][k]=maxright;

else

if(j<k)

{

re:

printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);

scanf("%d",&temp);

if(temp>=maxright||temp<-1)

{

printf("Invalid input!\n");

goto re;

}

if(temp==-1)

temp=maxright;

G[j][k]=G[k][j]=temp;

}

}

for(j=0;j<num;j++)

{

status=0;

for(k=0;k<num;k++)

if(G[j][k]<maxright)

{

status=1;

break;

}

if(status==0)

break;

}

do

{

printf("Please enter the vertex where Prim algorithm starts:");

scanf("%d",&start);

}while(start<0||start>num);

in[start-1]=1;

for(i=0;i<num-1&&status;i++)

{

for(j=0;j<num;j++)

for(k=0;k<num;k++)

if(G[j][k]<min&&in[j]&&(!in[k]))

{

v1=j;

v2=k;

min=G[j][k];

}

if(!in[v2])

{

path[i][0]=v1;

path[i][1]=v2;

in[v1]=1;

in[v2]=1;

min=maxright;

}

}

if(!status)

printf("We cannot deal with it because the graph is not connected!\n");

else

{

for(i=0;i<num-1;i++)

printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+1);

}

return 1;

}

Prim演算法。

設圖G =（V，E），其生成樹的頂點集合為U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。

③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。

其演算法的時間復雜度為O(n^2)

參考程序

//Prim 演算法 讀入頂點數(n)、邊數(m)，邊的起始點和權值 用鄰接矩陣儲存

//例如

//7 12 (7個頂點12條邊)

//1 2 2

//1 4 1

//1 3 4

//2 4 3

//2 5 10

//3 4 2

//4 5 7

//3 6 5

//4 6 8

//4 7 4

//5 7 6

//6 7 1

#include <stdio.h>

#include <string.h>

int main()

{

int m , n;

int a[201][201] , mark[201] , pre[201] , dist[201];

int s , t , w;

int i , j , k , min , tot;

freopen("Prim.txt" , "r" , stdin);

//讀入數據

memset(a , 0 , sizeof(a));

scanf("%d %d" , &n , &m);

for (i = 0; i < m; i ++)

{

scanf("%d %d %d" , &s , &t , &w);

a[s][t] = w; a[t][s] = w;

}

//賦初值

memset(mark , 0 , sizeof(mark));

memset(pre , 0 , sizeof(pre));

memset(dist , 9999 , sizeof(dist));

dist[1] = 0;

//Prim

for (i = 1; i <= n; i ++)

{

min = 9999; k = 0;

for (j = 1; j <= n; j ++)

if ((mark[j] == 0) && (dist[j] < min)) {min = dist[j]; k = j;}

if (k == 0) break;

mark[k] = 1;

for (j = 1; j <= n; j ++)

if ((mark[j] == 0) && (a[k][j] < dist[j]) && (a[k][j] > 0))

{

dist[j] = a[k][j];

pre[j] = k;

}

}

tot = 0;

for (i = 1; i <= n; i ++) tot += dist[i];

printf("%d\n" , tot);

return 0;

}

㈨ 數據結構迷宮演算法求解

注釋非常詳細，希望對你有所幫助。
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定義迷宮內點的坐標類型
{
int x;
int y;
};

struct Element //"戀"棧元素，嘿嘿。。
{
int x,y; //x行,y列
int d; //d下一步的方向
};

typedef struct LStack //鏈棧
{
Element elem;
struct LStack *next;
}*PLStack;

/*************棧函數****************/

int InitStack(PLStack &S)//構造空棧
{
S=NULL;
return 1;
}

int StackEmpty(PLStack S)//判斷棧是否為空
{
if(S==NULL)
return 1;
else
return 0;
}

int Push(PLStack &S, Element e)//壓入新數據元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}

int Pop(PLStack &S,Element &e) //棧頂元素出棧
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}

/***************求迷宮路徑函數***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口點作上標記
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //開始為-1
Push(S1,elem);
while(!StackEmpty(S1)) //棧不為空 有路徑可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一個方向
while(d<4) //試探東南西北各個方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向輸出為-1 判斷是否到了出口
Push(S1,elem);
printf("\n0=東 1=南 2=西 3=北 886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)\n");
while(S1) //逆置序列 並輸出迷宮路徑序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出兩層循環，本來用break,但發現出錯，exit又會結束程序，選用return還是不錯滴
}
if(maze[a][b]==0) //找到可以前進的非出口的點
{
maze[a][b]=2; //標記走過此點
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //當前位置入棧
i=a; //下一點轉化為當前點
j=b;
d=-1;
}
d++;
}
}
printf("沒有找到可以走出此迷宮的路徑\n");
}

/*************建立迷宮*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宮行,列 [/M]

printf("請輸入迷宮的行數 m=");
scanf("%d",&m);
printf("請輸入迷宮的列數 n=");
scanf("%d",&n);
printf("\n請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表牆\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宮為(最外圈為牆)...\n");
for(i=0;i<=m+1;i++) //加一圈圍牆
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}

void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐標
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次為東西南北 [/M]

initmaze(sto);//建立迷宮

printf("輸入入口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&start.x,&start.y);
printf("輸入出口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&end.x,&end.y);

MazePath(start,end,sto,add); //find path
system("PAUSE");
}
測試數據，演算法復雜度你就自己來寫吧，如果你連這都不自己做，那你一定是在應付作業。勸你還是自己運行測試一下吧，免得答辯時老師問你，什麼都不知道，那你就悲劇了。祝你好運！！

㈩ 怎麼製作迷宮圖

方案一：主路扭曲型

1、首先，按照下圖的間隔規則來生成基礎的大地圖，1為陸地，0為水域。

2、然後，選擇一個靠近邊緣的1作為起點，在它的周圍隨機找另一個黃色的1（這里的「周圍」指的是上下左右4個方向，斜邊不算）。找到就把他們聯通，即把兩個1之間的0變成陸地，這里用紅色來表示。

3、把上一步「終」的格子作為新的一個「起」格子，不停循環第二步的過程，直到找不到周圍有黃色的1。

4、這時候，原路往回走（即不停去找前一個格子），直到找到一個格子，這個格子周圍有黃色的1，那麼從這個格子開始重復前兩個步驟。

5、接下來就是不停重復上面的步驟，找到就聯通，找不到就往回走。

6、填充完整個地圖之後，迷宮就算是製作完成了，根據需求加上終點即可。

總結一下，這種方案生成的迷宮會有一條明顯的主路，即一條特別長、貫穿大部分區域的路線，同時，迷宮的路線一般比較扭曲。

方案二：自然分岔型

這個方案的雛形來自於隨機prim演算法，具體步驟如下：

1、跟方案一一樣，生成一個基礎地圖。格子先用黃色1和灰色0來表示，暫時不區分水陸。

2、隨機取一個地圖邊緣的黃色1，把它標記為紅色1，即變成陸地。然後把它旁邊的灰色0標記成藍色0，表示「待定」。（注意的是，大地圖四周的灰色0固定不變，作為地圖邊緣而存在）

3、敲黑板了！！這里是重點！！！

隨機選一個藍色的0（這一步很重要，會使這個方案明顯區別於上一個方案），然後看紅色1隔著這個藍色0對面的格子，是否是黃色的1：

如果是，則把對面的黃色1標記成紅色1，即變成陸地，然後把藍色0變成紅色的0，即也變成陸地；

如果不是，就把這個藍色的0變成灰色的0。

最後，把新創建的紅色1周圍的灰色0，標記成藍色0。

4、繼續重復上面的步驟

5、對比上圖和下圖，這里取一個藍色0生成一個紅色1之後，新生成的紅色1旁邊，有兩個藍色0的兩邊都是紅色1了，那麼就根據第三步的規則，在稍後取到這些藍色0時，就會把他們變成灰色0。

6、繼續重復上述步驟，直到整個地圖沒有藍色0了，地圖就生成完畢。

總結一下，對比方案一，這套方案不會出現明顯的主路，迷宮相對比較自然，但迷宮的分岔路會比較多，所以迷宮可能會更復雜，即玩家需要做選擇的次數可能比較多。

方案三：塊狀分割型

上述兩個方案有個共同的特點，就是道路永遠都是1個格子寬，如果游戲需要給地圖創造一些小型地塊或者更寬的道路，需要在迷宮生成之後再用各種分布的規則來豐富迷宮。

而第三個方案則以小型地塊作為出發點來設計迷宮，這套方案的雛形來自於國外大神Bob Nystrom，有興趣的可以去查看他個人主頁。

1、首先，在大地圖（還是之前那個大地圖）上生成若干小型地形，保證邊長是奇數且不重合就好（示意圖全部使用了正方形，實際上可以做成長方形讓地圖更加自然）。注意頂點要在黃色1格子上即可，這里我用橙色1來表示這些小型地塊。

2、然後，根據之前方案一的迷宮生成方案，在非小型地塊的區域里，用迷宮來填充。這一步完成之後，迷宮和小型地形是分隔開來的。

3、在橙色1的小型地形周圍，隨機取點以連接黃色1，連接點的數量可以根據需要來確定，建議是不要吝嗇連接點的個數，因為這種地圖之下，分岔路遠比前兩種方案要少。

4、接下來是簡化地圖，目的是去掉一些死胡同，因為這種方案的核心在於小型地塊，沒有必要讓玩家在迷宮的路上繞。方法是把一些3邊都是灰色0的黃色1去掉即可，具體數量也根據游戲需求來制定，我這里只去掉了一部分。

5、最後，給地圖加上出口和入口，地圖就做完啦！

總結一下，這種方案比前兩種多了小型地塊，這一點比較適合設計玩家的階段性反饋。同時地圖的分岔路明顯減少，玩家在這種方案下的選擇次數會明顯降低。另外，由於這個方案的步驟相對多且獨立，所以對於設計者來講會比較容易控制地圖的結構。