本文目录一览:
- 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;
}
}
}