bfs演算法
Ⅰ BFS演算法的鄰接矩陣
鄰接矩陣就是一個二維數組。
比如 ：map[N][N]；
大多都是存兩點之間的距離，時間等邊權。
Ⅱ 廣度優先演算法
廣度優先演算法（Breadth-First Search），同廣度優先搜索，又稱作寬度優先搜索，或橫向優先搜索，簡稱BFS，是一種圖形搜索演演算法。簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點，如果發現目標，則演算終止。廣度優先搜索的實現一般採用open-closed表。
Ⅲ C++演算法BFS迷宮題
這個是面向對象裡面的重載 node重名的函數叫做它的構造函數 作用就是賦予初值
建議去看下類與對象相關概念
Ⅳ dijkstra演算法和bfs演算法的不同
dijkstra演算法是求單源點的最短路徑問題，要求權值不能為負
bfs演算法則是從某頂點出發按廣度優先的原則依次訪問各連通的頂點，圖可以無權值
Ⅳ bfs演算法是什麼
廣度優先搜索演算法（英語：Breadth-First Search，縮寫為BFS），又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。
簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。廣度優先搜索的實現一般採用open-closed表。
作法
BFS是一種暴力搜索演算法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能地址，徹底地搜索整張圖，直到找到結果為止。BFS並不使用經驗法則演算法。
從演算法的觀點，所有因為展開節點而得到的子節點都會被加進一個先進先出的隊列中。
一般的實現里，其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為open的容器中（例如隊列或是鏈表），而被檢驗過的節點則被放置在被稱為closed的容器中。
(5)bfs演算法擴展閱讀：
廣度優先搜索演算法的應用
廣度優先搜索演算法能用來解決圖論中的許多問題，例如：
1、查找圖中所有連接組件（ConnectedComponent）。一個連接組件是圖中的最大相連子圖。
2、查找連接組件中的所有節點。
3、查找非加權圖中任兩點的最短路徑。
4、測試一圖是否為二分圖。
5、（Reverse）Cuthill–McKee演算法
Ⅵ BFS求源代碼及思路
1、演算法用途：
是一種圖像搜索演演算法。用於遍歷圖中的節點，有些類似於樹的深度優先遍歷。這里唯一的問題是，與樹不同，圖形可能包含循環，因此我們可能會再次來到同一節點。
2、主要思想：
主要藉助一個隊列、一個布爾類型數組、鄰接矩陣完成（判斷一個點是否查看過，用於避免重復到達同一個點，造成死循環等），先將各點以及各點的關系存入鄰接矩陣。
再從第一個點開始，將一個點存入隊列，然後在鄰接表中找到他的相鄰點，存入隊列，每次pop出隊列頭部並將其列印出來（文字有些抽象，實際過程很簡單），整個過程有點像往水中投入石子水花散開。
4、復雜度分析：
演算法藉助了一個鄰接表和隊列，故它的空問復雜度為O(V）。 遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程，其耗費的時間取決於所採用結構。 鄰接表表示時，查找所有頂點的鄰接點所需時間為O(E)，訪問頂點的鄰接點所花時間為O（V）,此時，總的時間復雜度為O(V+E)。
Ⅶ 分別用DFS和BFS演算法給電腦設置AI(JAVA)
有必勝策略的吧。。狀態空間的上限是3^9也就是不到20000實際上沒有這么多。所以直接採用BFS標記會比較好。演算法的話就是填充表，把表（九個格子）填為必勝、必敗，己勝，開始的時候全部標為必敗，再從勝狀態開始向回BFS（或者DFS也可以），己勝狀態向回標的一定是敗狀態，必勝狀態的上一狀態為必敗態，必敗態的上一狀態可能是必敗或者必勝（這就是因為這傢伙走錯棋了所以要輸！）
我的習慣。不寫代碼。沒有意思。
Ⅷ 廣度優先搜索演算法
我以前做的一個光搜題，給你貼上吧，是一個關於素數變化的題目，輸入一對素數，每個是4位數，每次只能變化一位數，且變化後的數還是素數，求經過多少次變化，能變成另一個輸入的素數。程序有點復雜，慢慢看吧。
#include<iostream>
#include<cmath>
usingnamespacestd;
inttemp,temp2,i,j;
intf(intt)
{
temp2=sqrt(float(t))+1;
for(j=2;j<temp2;++j)
if(t%j==0)
return0;
return1;
}
intmain()
{
intprime[10000],qu[20000],result,k,h,num,tag[10000],sum,index,itag,d[10000],atag;
while(1)
{
for(i=1000;i<10000;++i){tag[i]=0,d[i]=0;}
cin>>num>>result;
k=0;h=1;qu[k]=num;index=0;itag=1;tag[num]=1;atag=0;
while(k!=h)
{
if(qu[k]==result)
{cout<<d[qu[k]]<<endl;break;}
if(qu[k]%2==0)continue;
temp=qu[k]-qu[k]%10+1;
for(i=0;i<5;i++,temp+=2)
if(f(temp)==1&&tag[temp]==0)
{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;
if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1)break;
temp=qu[k]-qu[k]%100/10*10;
for(i=0;i<10;++i,temp+=10)
if(f(temp)==1&&tag[temp]==0)
{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;
if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1)break;
temp=qu[k]-qu[k]%1000/100*100;
for(i=0;i<10;++i,temp+=100)
if(f(temp)==1&&tag[temp]==0)
{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;
if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1)break;
temp=qu[k]-qu[k]/1000*1000+1000;
for(i=0;i<8;++i,temp+=1000)
if(f(temp)==1&&tag[temp]==0)
{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;
if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1)break;
++k;
}
}
return1;
}
Ⅸ 求解關於DFS,BFS的演算法時間復雜度分析
記住就行了，DFS、BFS時間復雜度對於採用臨接矩陣存儲時是O(n)；對於採用臨接表時是O(n+e).
Ⅹ 廣度優先法(BFS)演算法
#include<stdio.h>#define MAX 10 int front=-1,rear=-1; struct node { int value; struct node *next; }; typedef struct node node; typedef node *link; struct graph_link { link first; //隊頭指針 link last; //隊尾指針 }; int run[9]={0}; int queue[MAX]; struct graph_link head[9]; void print(struct graph_link temp) { link current=temp.first; while (current!=NULL) { printf("[%d] ",current->value); current=current->next; } putchar('\n'); } void insert(struct graph_link *temp, int x) //鄰接表法存儲頂點 { link new_node; new_node=new node; new_node->value=x; new_node->next=NULL; if (temp->first==NULL) { temp->first=new_node; //新隊頭 temp->last=new_node; //當前尾指向頭 } else { temp->last->next=new_node; //原隊尾的結點接上新結點 temp->last=new_node; //將隊尾結點指向新結點 } } void enqueue(int value) //入隊 { if (rear>=MAX) return; queue[rear++]=value; } int dequeue() //出隊 { if (front==rear) return -1; front++; return queue[front]; } void bfs(int current) //廣度優先 { link tempnode; enqueue(current); //入隊 run[current]=1; printf("[%d] ",current); while (front!=rear) //判斷是否為空隊列 { current=dequeue(); //出隊 tempnode=head[current].first; //與i個頂點的鏈表頭指針 while (tempnode!=NULL) { if (run[tempnode->value]==0) //判斷以i個頂點連接的頂點是否被訪問過 { enqueue(tempnode->value); //入隊 run[tempnode->value]=1; //標記已訪問過 printf("[%d] ",tempnode->value); } tempnode=tempnode->next; } } } void main() { int data[20][2]={{1,2},{2,1},{1,3},{3,1},{2,4},{4,2}, {2,5},{5,2},{3,6},{6,3},{3,7},{7,3}, {4,5},{5,4},{6,7},{7,6},{5,8},{8,5}, {6,8},{8,6}}; int data_num,i,j; for (i=1; i<9; i++) { head[i].first=NULL; head[i].last=NULL; for (j=0; j<20; j++) { if (data[j][0]==i) { data_num=data[j][1]; insert(&head[i],data_num); } } } printf("Imgae Data:\n"); for (i=1; i<9; i++) { printf("peak[%d]=> ",i); link ptr=head[i].first; while (ptr!=NULL) { printf("[%d] ",ptr->value); ptr=ptr->next; } putchar('\n'); } putchar('\n'); bfs(1); putchar('\n'); }