廣度c語言演算法,深度廣度演算法

本文目錄一覽：

• 1、C語言實現圖的廣度優先搜索遍歷演算法
• 2、c語言常用演算法有哪些
• 3、c語言廣度優先演算法
• 4、廣度優先搜索C語言演算法
• 5、廣度搜索在C語言中是如何使用的
• 6、求一個廣度優先演算法的實例及其C語言程序（L-dequeue）

C語言實現圖的廣度優先搜索遍歷演算法

先寫個大題思路，樓主先自己想想，想不出來的話，2天後給代碼。

queuenode q;

q.push(start);

bool canVisit[][];

node cur;

while(!q.empty()){

cur = q.top();

q.pop();

foreach(node is connected by cur){

if(canVisit[node.x][node.y])

{

printf(“訪問結點(%d,%d)”,node.x,node.y);

canVisit[node.x][node.y]=false;

q.push(node);

}

}

}

c語言常用演算法有哪些

0） 窮舉法

窮舉法簡單粗暴，沒有什麼問題是搞不定的，只要你肯花時間。同時對於小數據量，窮舉法就是最優秀的演算法。就像太祖長拳，簡單，人人都能會，能解決問題，但是與真正的高手過招，就頹了。

1） 貪婪演算法

貪婪演算法可以獲取到問題的局部最優解，不一定能獲取到全局最優解，同時獲取最優解的好壞要看貪婪策略的選擇。特點就是簡單，能獲取到局部最優解。就像打狗棍法，同一套棍法，洪七公和魯有腳的水平就差太多了，因此同樣是貪婪演算法，不同的貪婪策略會導致得到差異非常大的結果。

2） 動態規劃演算法

當最優化問題具有重複子問題和最優子結構的時候，就是動態規划出場的時候了。動態規劃演算法的核心就是提供了一個memory來緩存重複子問題的結果，避免了遞歸的過程中的大量的重複計算。動態規劃演算法的難點在於怎麼將問題轉化為能夠利用動態規劃演算法來解決。當重複子問題的數目比較小時，動態規劃的效果也會很差。如果問題存在大量的重複子問題的話，那麼動態規劃對於效率的提高是非常恐怖的。就像斗轉星移武功，對手強它也會比較強，對手若，他也會比較弱。

3）分治演算法

分治演算法的邏輯更簡單了，就是一個詞，分而治之。分治演算法就是把一個大的問題分為若干個子問題，然後在子問題繼續向下分，一直到base cases，通過base cases的解決，一步步向上，最終解決最初的大問題。分治演算法是遞歸的典型應用。

4） 回溯演算法

回溯演算法是深度優先策略的典型應用，回溯演算法就是沿著一條路向下走，如果此路不同了，則回溯到上一個

分岔路，在選一條路走，一直這樣遞歸下去，直到遍歷萬所有的路徑。八皇后問題是回溯演算法的一個經典問題，還有一個經典的應用場景就是迷宮問題。

5） 分支限界演算法

回溯演算法是深度優先，那麼分支限界法就是廣度優先的一個經典的例子。回溯法一般來說是遍歷整個解空間，獲取問題的所有解，而分支限界法則是獲取一個解（一般來說要獲取最優解）。

c語言廣度優先演算法

既然b[i]記錄的是前驅城市。

那也就是通過i的前一個城市存在b[i]中，能保證從A到H是最短的。

廣度優先搜索C語言演算法

它沒有固定的寫法， 但是大框都差不多， 一定要使用隊列， 因為隊列的存在可以維護程序按照廣度優先的方式進行搜索。即層次遍歷

可以給你一份我作過的一個題的代碼，大體上就是這個樣子

/****************************************************\

*

* Title : Rescue

* From : HDU 1242

* AC Time : 2012.01.12

* Type : 廣度優先搜索求最短步數

* Method :從目標結點向回搜索，初始結點有多個

*

\****************************************************/

#include stdio.h

#include string.h

#define DATASIZE 201

#define QUEUESIZE 65536

typedef struct

{

int x,y;

}CPOINT;

int bfs(char map[][DATASIZE], int n, int m, CPOINT cpa);

int direction[][2] = {{1,0},{-1,0},{0,1},{0,-1}};

int main(void)

{

int m,n,i,j,res;

CPOINT cpa;

char map[DATASIZE][DATASIZE];

freopen(“c:\\in.data”,”r”,stdin);

while(scanf(“%d%d%*c”,n,m) != EOF) {

for(i = 0 ; i n ; i++) {

gets(map[i]);

for(j = 0 ; j m ; j++) {

if(map[i][j] == ‘a’) {

cpa.x = i;

cpa.y = j;

}

}

}

res = bfs(map, n, m, cpa);

if(res) {

printf(“%d\n”,res);

} else {

printf(“Poor ANGEL has to stay in the prison all his life.\n”);

}

}

return 0;

}

int bfs(char map[][DATASIZE], int n, int m, CPOINT cpa)

{

CPOINT q[QUEUESIZE],u,np;

int vis[DATASIZE][DATASIZE],step[DATASIZE][DATASIZE],i,front,rear,res;

memset(q, 0, sizeof(q));

memset(vis, 0, sizeof(vis));

memset(step, 0, sizeof(step));

front = rear = res = 0;

q[rear++] = cpa;

vis[cpa.x][cpa.y] = 1;

step[cpa.x][cpa.y] = 0;

while(front = rear) {

u = q[front++];

if(map[u.x][u.y] == ‘r’) {

res = step[u.x][u.y];

break;

}

for(i = 0 ; i 4; i++) {

np.x = u.x + direction[i][0];

np.y = u.y + direction[i][1];

if(np.x = 0 np.x n np.y = 0 np.y m !vis[np.x][np.y] map[np.x][np.y] != ‘#’ ) {

vis[np.x][np.y] = 1;

q[rear++] = np;

step[np.x][np.y] = step[u.x][u.y] + 1;

if(map[np.x][np.y] == ‘x’) {

++step[np.x][np.y];

}

}

}

}

return res;

}

廣度搜索在C語言中是如何使用的

用一個隊列來實現。。。

首先把所有初始狀態入隊。。。然後把隊首元素出隊。。執行你需要進行的操作。。同時把出隊的元素所派生出來的符合你題目要求的狀態入隊。。

一直不停的循環。。下面我給你個非常簡單的例子：

Problem:求能被n整出的，求只有0和1構成的正十進位整數是多少（輸入：一個數N。當N=0是代表輸入結束。。。

源代碼如下：

#inlcude “stdio.h”

#include “string.h”

typedef struct QUEUE//建立一個隊列

{

int queue[1000];

int top;//尾

int low;//頭

}ST;

void main()

{

ST Queue;

int n;

while(scanf(“%d”,n)n)//當N為0是代表輸入結束

{

memset(Queue,0,sizeof(Queue));//隊列清零(memset()包含在string.h頭文件中）

Queue.queue[Queue.top=Queue.low=0]=1;//從一開始搜索

Queue.top++;

while(Queue.lowQueue.top)//當隊列不為空時，繼續循環

{

int s=Queue.queue[Queue.low++];//出隊列

if(!(s%n))

{

printf(“%d\n”,s);

break;

}

else //如果沒找到。。後面的數入隊列

{

Queue.queue[Queue.top++]=10*s;

Queue.queue[Queue.top++]=10*s+1;

}

}

}

}

這是一個很簡單也會一個很典型的廣度優先搜索。。。

因為這只是給你介紹一個概念。。所有就舉了最簡單的例子。。。

廣度優先其實很複雜。。還有各種優化。。。

先有個這樣的概念你以後在去學吧。。至於上面一個人的回答。你可以直接無視。。

他說的是關於廣度優先比價複雜的（雖然原理是一樣的）。。

改說的我都說了。。

給我分啊

我要分 。。。

求一個廣度優先演算法的實例及其C語言程序（L-dequeue）

#include stdio.h

#define max 100

typedef struct anode

{

int adjvex; //邊的終點位置

struct anode *nextarc;

}arcnode;

typedef struct node

{

int data;

arcnode *firstout;

}vnode;

typedef struct

{

vnode adjlist[max];

int n;

int e;

}Agraph;

static int visit[max];

//深度遍歷

void DFS(Agraph G,int v) //v為初始頂點編號

{

int k;

arcnode *p;

for(k=0;kG.n;k++)

visit[k]=0;

printf(“%d “,v);

p=G.adjlist[v].firstout;

while(p)

{

if(!visit[p-adjvex])

DFS(G,p-adjvex);

p=p-nextarc;

}

}

void BFS(Agraph G,int v)

{

arcnode *p;

int q[max];

int front=0;

int rear=0;

int w,i;

for(i=0;iG.n;i++)

visit[i]=0;

printf(“%d “,v);

visit[v]=1;

rear=(rear+1)%max;

q[rear]=v;

while(front!=rear)

{

front=(front+1)%max;

w=q[front];

p=G.adjlist[w].firstout;

while(p)

{

if(!visit[p-adjvex])

{

printf(“%d “,p-adjvex);

visit[p-adjvex]=1;

rear=(rear+1)%max;

q[rear]=p-adjvex;

}

p=p-nextarc;

}

printf(“\n”);

}

}

//層序遍歷二叉樹

struct btnode

{

int data;

btnode *lchild,*rchild;

};

void level(struct btnode *bt)

{

if(!bt)

return;

btnode *q[max];

int front,rear;

front=0;

rear=0;

printf(“%d “,bt-data);

rear=(rear+1)%max;

q[rear]=bt;

while(front!=rear)

{

front=(front+1)%max;

bt=q[front];

if(bt-lchild)

{

printf(“%d “,bt-lchild-data);

rear=(rear+1)%max;

q[rear]=bt-lchild;

}

if(bt-rchild)

{

printf(“%d “,bt-rchild-data);

rear=(rear+1)%max;

q[rear]=bt-rchild;

}

}

}

void DFS1(Agraph G,int v)

{

arcnode *p;

printf(“%d “,v);

visit[v]=1;

p=G.adjlist[v].firstout;

while(p)

{

if(!visit[p-adjvex])

{

DFS1(G,p-adjvex);

}

p=p-nextarc;

}

}

void level1(struct btnode *bt)

{

if(!bt)

return;

printf(“%d “,bt-data);

struct btnode *q[max];

int front=0;

int rear=0;

rear=(rear+1)%max;

q[rear]=bt;

while(front!=rear)

{

front=(front+1)%max;

bt=q[front];

if(bt-lchild)

{

printf(“%d “,bt-lchild-data);

rear=(rear+1)%max;

q[rear]=bt-lchild;

}

if(bt-rchild)

{

printf(“%d “,bt-rchild-data);

rear=(rear+1)%max;

q[rear]=bt-rchild;

}

}

}

void BFS1(Agraph G,int v)

{

int q[max];

int front=0;

int rear=0;

int i;

for(i=0;iG.n;i++)

visit[i]=0;

printf(“%d “,v);

visit[v]=1;

rear=(rear+1)%max;

q[rear]=v;

arcnode *p;

while(front!=rear)

{

front=(front+1)%max;

i=q[front];

p=G.adjlist[i].firstout;

while(p)

{

if(!visit[p-adjvex])

{

printf(“%d “,p-adjvex);

visit[p-adjvex]=1;

rear=(rear+1)%max;

q[rear]=p-adjvex;

}

p=p-nextarc;

}

}

}