廣度演算法
Ⅰ 關於廣度優先搜索演算法
廣度優先搜索演算法，是按層遍歷各個結點，以求出最短或最優的解，
常用於計算路徑的最短距離，和最佳通路。
例如：迷宮的最短路徑計算，推箱子的移動最小步數等小游戲，都是按廣度搜索來進行的。
這個演算法是教程中很經典的，有很多例子和代碼。你可以好好研究！
如下是一段迷宮的最佳路徑求解演算法。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;
void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}
int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx<5)&&(ny>=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}
Ⅱ c語言廣度優先演算法
既然b[i]記錄的是前驅城市。
那也就是通過i的前一個城市存在b[i]中，能保證從A到H是最短的。
Ⅲ 廣度優先演算法和深度優先演算法哪個可以求無向圖的所有連通分量，具體什麼原理
你好，廣度優先和深度優先都可以求出無向圖的所有連通分量，他們的原理都是遍歷，一個是先按廣度進行遍歷，另外一個是先按深度進行遍歷。
Ⅳ 廣度優先 演算法，各位幫幫。。急
個人對廣度優先演算法的理解是每次優先遍歷父結點下的直接子結點，遍歷完這些直接子結點之後再從這些子結點開始遍歷他們的直接子結點，以此類推下去，直到找到終點。所以，此處肯定是需要使用到迭代了。在此我想寫出我的思路來與樓主交流下。
1.確定startway點和endway點以後，找到startway點，並對該點下的子結點進行遍歷。如你此處選擇的startway是牧野草原04 即位置在ab(04)，endway是牧野草原15，那麼ab(04)下的直接子結點可認為是牧野草原06、牧野草原08和牧野草原10。我們開始按照廣度優先演算法遍歷到牧野草原15。
2.首先我們遍歷完04的子結點（06，08，10），發現沒有15。
3.接下來我們遍歷結點06的子結點（04，05，03），發現沒有15.
4.然後，我們開始遍歷結點08的子結點（4，15，16），發現15，於是整個遍歷結束。
PS:對於迴路的子結點不應該考慮遍歷，比如06中04的迴路。
Ⅳ 廣度優先法(BFS)演算法
//圖定義
typedef int InfoType;
#define INF 65536
#define MAXV 100 //最大頂點個數
//以下定義鄰接矩陣類型
typedef struct
{ int no; //頂點編號
InfoType info; //頂點其他信息
} VertexType; //頂點類型
typedef struct //圖的定義
{ int edges[MAXV][MAXV]; //鄰接矩陣
int vexnum,arcnum; //頂點數，弧數
VertexType vexs[MAXV]; //存放頂點信息
} MGraph; //圖的鄰接矩陣類型
//以下定義鄰接表類型
typedef struct ANode //弧的結點結構類型
{ int adjvex; //該弧的終點位置
struct ANode *nextarc; //指向下一條弧的指針
InfoType info; //該弧的相關信息,這里用於存放權值
} ArcNode;
typedef int Vertex;
typedef struct Vnode //鄰接表頭結點的類型
{ Vertex data; //頂點信息
ArcNode *firstarc; //指向第一條弧
} VNode;
typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型
typedef struct
{ AdjList adjlist; //鄰接表
int n,e; //圖中頂點數n和邊數e
} ALGraph; //圖的鄰接表類型
int visited[MAXV]; //全局數組
//廣度優先搜索
void BFS(ALGraph *G,int v)
{
ArcNode *p;
int queue[MAXV], front=0, rear=0; //定義循環隊列並初始化
int visited[MAXV]; //定義存放結點的訪問標志的數組
int w, i;
for (i=0; i<G->n; i++)
{
visited[i]=0; //訪問標志數組初始化
}
printf("%3d",v); //輸出被訪問頂點的編號
visited[v]=1; //置已訪問標記
rear = (rear+1)%MAXV;
queue[rear] = v; //v進隊
while (front != rear) //若隊列不空時循環
{
front = (front+1)%MAXV;
w = queue[front]; //出隊並賦給w
p = G->adjlist[w].firstarc; //找與頂點w鄰接的第一個頂點
while (p != NULL)
{
if (visited[p->adjvex] == 0) //若當前鄰接頂點未被訪問
{
printf("%3d", p->adjvex); //訪問相鄰頂點
visited[p->adjvex] = 1; //置該頂點已被訪問的標志
rear = (rear+1)%MAXV; //該頂點進隊
queue[rear] = p->adjvex;
}
p = p->nextarc; //找下一個鄰接頂點
}
}
printf("\n");
}
Ⅵ 怎樣理解深度優先演算法和廣度優先演算法
胡說八道.... 深度優先:前序遍歷 廣度優先:按層遍歷
Ⅶ 廣度優先演算法的特性
空間復雜度 因為所有節點都必須被儲存，因此BFS的空間復雜度為 O(|V| + |E|)，其中 |V| 是節點的數目，而 |E| 是圖中邊的數目。註：另一種說法稱BFS的空間復雜度為O(B)，其中 B 是最大分支系數，而 M 是樹的最長路徑長度。由於對空間的大量需求，因此BFS並不適合解非常大的問題。 若所有邊的長度相等，廣度優先搜索演算法是最佳解——亦即它找到的第一個解，距離根節點的邊數目一定最少；但對一般的圖來說，BFS並不一定回傳最佳解。這是因為當圖形為加權圖（亦即各邊長度不同）時，BFS仍然回傳從根節點開始，經過邊數目最少的解；而這個解距離根節點的距離不一定最短。這個問題可以使用考慮各邊權值，BFS的改良演算法成本一致搜尋法（en:uniform-cost search）來解決。然而，若非加權圖形，則所有邊的長度相等，BFS就能找到最近的最佳解。
Ⅷ 廣度優先演算法的簡介
由圖一可以知道，這樣形成的一棵樹叫搜索樹。初始狀態對應著根結點，目標狀態對應著目標結點。排在前的結點叫父結點，其後的結點叫子結點，同一層中的結點是兄弟結點，由父結點產生子結點叫擴展。完成搜索的過程就是找到一條從根結點到目標結點的路徑，找出一個最優的解。這種搜索演算法的實現類似於圖或樹的遍歷，通常可以有兩種不同的實現方法，即深度優先搜索（DFS——Depth First search）和廣度優先搜索（BFS——Breadth First Search）。
Ⅸ 廣度優先演算法（寬搜）pascal
下面是一段delphi代碼：
演算法核心代碼，為增強演算法通用性，將窗體的一個treeview和ADOQuery引用到局部變數中，作為對象引用，不創建，也不釋放，相當於別名
procere Tfrm.FmtTree();
var
i,j :integer;
leafList,leafListPlus: TList;
leaf,subNode: TTreeNode;
tv: TTreeView;//引用窗體控制項
qry: TADOQuery;//引用窗體控制項
begin
//初始化
leafList:=TList.Create;
leafListPlus:=TList.Create;
tv:=tvw1;
tv.Items.Clear;
qry:=qry1;
subNode:=tv.Items.AddChild(nil,'月夜風箏(我)的公司');
leafList.Add(subNode);
//處理
while leafList.Count > 0 do
begin
leafListPlus.Clear;
for i:=0 to leafList.Count-1 do
begin
leaf:=leafList[i];
if leaf.Level = 0 then
qry.SQL.Text:=Format('select code,name,belong from TB where belong = ''%s''',['--'])
else
qry.SQL.Text:=Format('select code,Name,belong from TB where belong = ''%d''',[leaf.StateIndex]);
qry.Open;
for j:= 0 to qry.RecordCount-1 do
begin
subNode:=tv.Items.AddChild(leaf,qry.FieldByName('name').AsString);
subNode.ImageIndex:=subNode.Level;
subNode.StateIndex:=StrToInt(qry.FieldByName('code').AsString);
leafListPlus.Add(subNode);
qry.Next;
end;
end;
leafList.Assign(leafListPlus);
end;
//清理
tv.FullExpand;
leafListPlus.Free;
leafList.Free;
end;
說明：
用TList類型模擬實現了廣度優先演算法的隊列－－先進先出－－實際上，本演算法不需要那麼嚴格，只要按批先進先出就行了。leafList用於當前循環，leafListPlus用於下一輪循環，其中保存的都是樹節點類型，以方便在treeview上直接插入子節點，就省了查找父結點的演算法，節點的編號緩存在節點的StateIndex屬性中，編號可轉為整數型這是最方便的，如果編號不能保證可轉為整數，可以使用data屬性，可保萬無一失
希望對你有幫助~
Ⅹ 廣度優先法(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'); }