广度优先搜索c语言函数 广度优先搜索c语言函数

求一个C语言编程，图的遍历，深度优先和广度优先搜索的程序。要浅显易懂的~~~~

给你一个作为参考吧

为巴里坤哈萨克等地区用户提供了全套网页设计制作服务，及巴里坤哈萨克网站建设行业解决方案。主营业务为网站设计、做网站、巴里坤哈萨克网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

#include iostream

#define INFINITY 32767

#define MAX_VEX 20 //最大顶点个数

#define QUEUE_SIZE (MAX_VEX+1) //队列长度

using namespace std;

bool *visited; //访问标志数组

//图的邻接矩阵存储结构

typedef struct{

char *vexs; //顶点向量

int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵

int vexnum,arcnum; //图的当前顶点数和弧数

}Graph;

//队列类

class Queue{

public:

void InitQueue(){

base=(int *)malloc(QUEUE_SIZE*sizeof(int));

front=rear=0;

}

void EnQueue(int e){

base[rear]=e;

rear=(rear+1)%QUEUE_SIZE;

}

void DeQueue(int e){

e=base[front];

front=(front+1)%QUEUE_SIZE;

}

public:

int *base;

int front;

int rear;

};

//图G中查找元素c的位置

int Locate(Graph G,char c){

for(int i=0;iG.vexnum;i++)

if(G.vexs[i]==c) return i;

return -1;

}

//创建无向网

void CreateUDN(Graph G){

int i,j,w,s1,s2;

char a,b,temp;

printf("输入顶点数和弧数:");

scanf("%d%d",G.vexnum,G.arcnum);

temp=getchar(); //接收回车

G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目

printf("输入%d个顶点.\n",G.vexnum);

for(i=0;iG.vexnum;i++){ //初始化顶点

printf("输入顶点%d:",i);

scanf("%c",G.vexs[i]);

temp=getchar(); //接收回车

}

for(i=0;iG.vexnum;i++) //初始化邻接矩阵

for(j=0;jG.vexnum;j++)

G.arcs[i][j]=INFINITY;

printf("输入%d条弧.\n",G.arcnum);

for(i=0;iG.arcnum;i++){ //初始化弧

printf("输入弧%d:",i);

scanf("%c %c %d",a,b,w); //输入一条边依附的顶点和权值

temp=getchar(); //接收回车

s1=Locate(G,a);

s2=Locate(G,b);

G.arcs[s1][s2]=G.arcs[s2][s1]=w;

}

}

//图G中顶点k的第一个邻接顶点

int FirstVex(Graph G,int k){

if(k=0 kG.vexnum){ //k合理

for(int i=0;iG.vexnum;i++)

if(G.arcs[k][i]!=INFINITY) return i;

}

return -1;

}

//图G中顶点i的第j个邻接顶点的下一个邻接顶点

int NextVex(Graph G,int i,int j){

if(i=0 iG.vexnum j=0 jG.vexnum){ //i,j合理

for(int k=j+1;kG.vexnum;k++)

if(G.arcs[i][k]!=INFINITY) return k;

}

return -1;

}

//深度优先遍历

void DFS(Graph G,int k){

int i;

if(k==-1){ //第一次执行DFS时,k为-1

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

if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS

}

else{

visited[k]=true;

printf("%c ",G.vexs[k]); //访问第k个顶点

for(i=FirstVex(G,k);i=0;i=NextVex(G,k,i))

if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS

}

}

//广度优先遍历

void BFS(Graph G){

int k;

Queue Q; //辅助队列Q

Q.InitQueue();

for(int i=0;iG.vexnum;i++)

if(!visited[i]){ //i尚未访问

visited[i]=true;

printf("%c ",G.vexs[i]);

Q.EnQueue(i); //i入列

while(Q.front!=Q.rear){

Q.DeQueue(k); //队头元素出列并置为k

for(int w=FirstVex(G,k);w=0;w=NextVex(G,k,w))

if(!visited[w]){ //w为k的尚未访问的邻接顶点

visited[w]=true;

printf("%c ",G.vexs[w]);

Q.EnQueue(w);

}

}

}

}

//主函数

void main(){

int i;

Graph G;

CreateUDN(G);

visited=(bool *)malloc(G.vexnum*sizeof(bool));

printf("\n广度优先遍历: ");

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

visited[i]=false;

DFS(G,-1);

printf("\n深度优先遍历: ");

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

visited[i]=false;

BFS(G);

printf("\n程序结束.\n");

}

C语言广度优先搜索，代码

#include stdio.h

static char map[][20]={

"1111111111",

"1011111111",

"1000011111",

"1101010111",

"1101000111",

"1101111111",

"1100000001",

"1111111111",

};

static int min=100;

void func(int s, int i, int j)

{

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

int n;

if(i==6j==8)

{

if(smin)

min=s;

return;

}

for(n = 0; n  4; n ++)

{

if(map[i+next[n][0]][j+next[n][1]] == '0')

{

map[i+next[n][0]][j+next[n][1]] = '1';

func(s+1, i+next[n][0], j+next[n][1]);

map[i+next[n][0]][j+next[n][1]] = '0';

}

}

}

int main()

{

func(0,1,1);

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

return 0;

}

广度优先搜索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语言程序

这是我们老师给我们上数据结构课的课件

#include "stdio.h"

typedef int datatype; /*假定线性表元素的类型为整型*/

#define maxsize 1024 /*假定线性表的最大长度为1024*/

# define n 100 /* 图的顶点最大个数 */

typedef char VEXTYPE; /* 顶点的数据类型 */

typedef float ADJTYPE; /* 权值类型 */

typedef struct

{ VEXTYPE vexs[n] ; /* 顶点信息数组 */

ADJTYPE arcs[n][n] ; /* 边权数组 */

int num ; /* 顶点的实际个数 */

}GRAPH;

/***********************1。置空图**********************/

void GraphInit(GRAPH *L)

{

L-num=0;

}

/***********************2。求结点数**********************/

int GraphVexs(GRAPH *L)

{

return(L-num);

}

/***********************3。创建图**********************/

void GraphCreate(GRAPH *L)

{

int i,j;

GraphInit(L);

printf("请输入顶点数目：");

scanf("%d",L-num);

printf("请输入各顶点的信息(单个符号）：");

for(i=0;iL-num;i++)

{

fflush(stdin);

scanf("%c",L-vexs[i]);

}

printf("请输入边权矩阵的信息：");

for(i=0;iL-num;i++)

{

for(j=0;jL-num;j++)

{

scanf("%f",L-arcs[i][j]);

}

}

printf("图已经创建完毕！");

}

/***********************4。图的输出**********************/

void GraphOut(GRAPH L)

{

int i,j;

printf("\n图的顶点数目为：%d",L.num);

printf("\n图的各顶点的信息为：\n");

for(i=0;iL.num;i++)

printf("%c ",L.vexs[i]);

printf("\n图的边权矩阵的信息为：\n");

for(i=0;iL.num;i++)

{

for(j=0;jL.num;j++)

{

printf("%6.2f ",L.arcs[i][j]);

}

printf("\n");

}

printf("图已经输出完毕！");

}

/***********************5。图的深度周游**********************/

void DFS(GRAPH g,int qidian,int mark[])

//从第qidian个点出发深度优先周游图g中能访问的各个顶点

{

int v1;

mark[qidian]=1;

printf("%c ",g.vexs[qidian]);

for(v1=0;v1g.num;v1++)

{

if(g.arcs[qidian][v1]!=0mark[v1]==0)

DFS(g,v1,mark);

}

}

/***********************6。图的深度周游**********************/

void GraphDFS(GRAPH g)

//深度优先周游图g中能访问的各个顶点

{

int qidian,v,v1,mark[maxsize];

printf("\n深度周游：");

printf("\n请输入起点的下标：");

scanf("%d",qidian);

for(v=0;vg.num;v++)

{

mark[v]=0;

}

for(v=qidian;vg.num+qidian;v++)

{

//printf("v=%d ",v);

v1=v%g.num;

if(mark[v1]==0)

DFS(g,v1,mark);

}

}

typedef int DATATYPE; //队列元素的数据类型

typedef struct

{

DATATYPE data[maxsize]; //队中元素

int front,rear; //队头元素下标、队尾元素后面位置的下标

} SEQQUEUE;

/*****************************************************************************/

void QueueInit(SEQQUEUE *sq)

//将顺序循环队列sq置空（初始化）

{

sq-front=0;

sq-rear=0;

}

/*****************************************************************************/

int QueueIsEmpty(SEQQUEUE sq)

//如果顺序循环队列sq为空，成功返回1，否则返回0

{

if (sq.rear==sq.front)

return(1);

else

return(0);

}

/*****************************************************************************/

int QueueFront(SEQQUEUE sq,DATATYPE *e)

//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0

{

if (QueueIsEmpty(sq))

{ printf("queue is empty!\n");return 0;}

else

{ *e=sq.data[(sq.front)]; return 1;}

}

/*****************************************************************************/

int QueueIn (SEQQUEUE *sq,DATATYPE x)

//将元素x入队列sq的队尾，成功返回1，失败返回0

{

if (sq-front==(sq-rear+1)%maxsize)

{

printf("queue is full!\n");

return 0;

}

else

{

sq-data[sq-rear]=x;

sq-rear=(sq-rear+1)%maxsize;

return(1);

}

}

/*****************************************************************************/

int QueueOut(SEQQUEUE *sq)

//将队列sq队首元素出队列，成功返回1,失败返回0

{

if (QueueIsEmpty(*sq))

{

printf("queue is empty!\n");

return 0;

}

else

{

sq-front=(sq-front+1)%maxsize;

return 1;

}

}

/***********************7。图的广度周游**********************/

void BFS(GRAPH g,int v,int mark[])

//从v出发广度优先周游图g中能访问的各个顶点

{

int v1,v2;

SEQQUEUE q;

QueueInit(q);

QueueIn(q,v);

mark[v]=1;

printf("%c ",g.vexs[v]);

while(QueueIsEmpty(q)==0)

{

QueueFront(q,v1);

QueueOut(q);

for(v2=0;v2g.num;v2++)

{

if(g.arcs[v1][v2]!=0mark[v2]==0)

{

QueueIn(q,v2);

mark[v2]=1;

printf("%c ",g.vexs[v2]);

}

}

}

}

/***********************8。图的广度周游**********************/

void GraphBFS(GRAPH g)

//深度优先周游图g中能访问的各个顶点

{

int qidian,v,v1,mark[maxsize];

printf("\n广度周游：");

printf("\n请输入起点的下标：");

scanf("%d",qidian);

for(v=0;vg.num;v++)

{

mark[v]=0;

}

for(v=qidian;vg.num+qidian;v++)

{

v1=v%g.num;

if(mark[v1]==0)

BFS(g,v1,mark);

}

}

/***********************主函数**********************/

void main()

{

GRAPH tu;

GraphCreate(tu);

GraphOut(tu);

GraphDFS(tu);

GraphBFS(tu);

}

求大神帮写一个c语言图的深度优先遍历，和广度优先遍历??

/*深度优先*/

#includestdio.h

#includestdlib.h

struct node/*图的顶点结构*/

{

int vertex;

int flag;

struct node *nextnode;

};

typedef struct node *graph;

struct node vertex_node[10];

void creat_graph(int *node,int n)

{

graph newnode,p;/*定义一个新结点及指针*/

int start,end,i;

for(i=0;in;i++)

{

start=node[i*2];/*边的起点*/

end=node[i*2+1];/*边的终点*/

newnode=(graph)malloc(sizeof(struct node));

newnode-vertex=end;/*新结点的内容为边终点处顶点的内容*/

newnode-nextnode=NULL;

p=(vertex_node);/*设置指针位置*/

while(p-nextnode!=NULL)

p=p-nextnode;/*寻找链尾*/

p-nextnode=newnode;/*在链尾处插入新结点*/

}

}

void dfs(int k)

{

graph p;

vertex_node[k].flag=1;/*将标志位置1，证明该结点已访问过*/

printf("vertex[%d]",k);

p=vertex_node[k].nextnode;/*指针指向下个结点*/

while(p!=NULL)

{

if(vertex_node[p-vertex].flag==0)/*判断该结点的标志位是否为0*/

dfs(p-vertex);/*继续遍历下个结点*/

p=p-nextnode;/*若已遍历过p指向下一个结点*/

}

}

main()

{

graph p;

int node[100],i,sn,vn;

printf("please input the number of sides:\n");

scanf("%d",sn);/*输入无向图的边数*/

printf("please input the number of vertexes\n");

scanf("%d",vn);

printf("please input the vertexes which connected by the sides:\n");

for(i=0;i4*sn;i++)

scanf("%d",node[i]);/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/

for(i=1;i=vn;i++)

{

vertex_node[i].vertex=i;/*将每个顶点的信息存入数组中*/

vertex_node[i].nextnode=NULL;

}

creat_graph(node,2*sn);/*调用函数创建邻接表*/

printf("the result is:\n");

for(i=1;i=vn;i++)/*将邻接表内容输出*/

{

printf("vertex%d:",vertex_node[i].vertex);/*输出顶点内容*/

p=vertex_node[i].nextnode;

while(p!=NULL)

{

printf("-%3d",p-vertex);/*输出邻接顶点的内容*/

p=p-nextnode;/*指针指向下个邻接顶点*/

}

printf("\n");

}

printf("the result of depth-first search is:\n");

dfs(1);/*调用函数进行深度优先遍历*/

printf("\n");

}

/***************************广度优先*******************************/

#include stdio.h

#include stdlib.h

struct node

{

int vertex;

struct node *nextnode;

};

typedef struct node *graph;

struct node vertex_node[10];

#define MAXQUEUE 100

int queue[MAXQUEUE];

int front = - 1;

int rear = - 1;

int visited[10];

void creat_graph(int *node, int n)

{

graph newnode, p; /*定义一个新结点及指针*/

int start, end, i;

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

{

start = node[i *2]; /*边的起点*/

end = node[i *2+1]; /*边的终点*/

newnode = (graph)malloc(sizeof(struct node));

newnode-vertex = end; /*新结点的内容为边终点处顶点的内容*/

newnode-nextnode = NULL;

p = (vertex_node); /*设置指针位置*/

while (p-nextnode != NULL)

p = p-nextnode;

/*寻找链尾*/

p-nextnode = newnode; /*在链尾处插入新结点*/

}

}

int enqueue(int value) /*元素入队列*/

{

if (rear = MAXQUEUE)

return - 1;

rear++; /*移动队尾指针*/

queue[rear] = value;

}

int dequeue() /*元素出队列*/

{

if (front == rear)

return - 1;

front++; /*移动队头指针*/

return queue[front];

}

void bfs(int k) /*广度优先搜索*/

{

graph p;

enqueue(k); /*元素入队*/

visited[k] = 1;

printf("vertex[%d]", k);

while (front != rear)

/*判断是否对空*/

{

k = dequeue(); /*元素出队*/

p = vertex_node[k].nextnode;

while (p != NULL)

{

if (visited[p-vertex] == 0)

/*判断其是否被访问过*/

{

enqueue(p-vertex);

visited[p-vertex] = 1; /*访问过的元素置1*/

printf("vertex[%d]", p-vertex);

}

p = p-nextnode; /*访问下一个元素*/

}

}

}

main()

{

graph p;

int node[100], i, sn, vn;

printf("please input the number of sides:\n");

scanf("%d", sn); /*输入无向图的边数*/

printf("please input the number of vertexes\n");

scanf("%d", vn);

printf("please input the vertexes which connected by the sides:\n");

for (i = 0; i 4 *sn; i++)

scanf("%d", node[i]);

/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/

for (i = 1; i = vn; i++)

{

vertex_node[i].vertex = i; /*将每个顶点的信息存入数组中*/

vertex_node[i].nextnode = NULL;

}

creat_graph(node, 2 *sn); /*调用函数创建邻接表*/

printf("the result is:\n");

for (i = 1; i = vn; i++)

/*将邻接表内容输出*/

{

printf("vertex%d:", vertex_node[i].vertex); /*输出顶点内容*/

p = vertex_node[i].nextnode;

while (p != NULL)

{

printf("-%3d", p-vertex); /*输出邻接顶点的内容*/

p = p-nextnode; /*指针指向下个邻接顶点*/

}

printf("\n");

}

printf("the result of breadth-first search is:\n");

bfs(1); /*调用函数进行深度优先遍历*/

printf("\n");

}

求一个广度优先算法的实例及其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;

}

}

}