Ⅰ 求大神幫寫一個c語言圖的深度優先遍歷，和廣度優先遍歷
/*深度優先*/
#include<stdio.h>
#include<stdlib.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;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[start]);/*設置指針位置*/
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;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 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[start]); /*設置指針位置*/
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語言演算法
它沒有固定的寫法， 但是大框都差不多， 一定要使用隊列， 因為隊列的存在可以維護程序按照廣度優先的方式進行搜索。即層次遍歷
可以給你一份我作過的一個題的代碼，大體上就是這個樣子
/****************************************************\
*
* 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語言程序（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;k<G.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;i<G.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;i<G.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;
}
}
}
Ⅳ C語言廣度優先搜索遍歷圖的演算法
visited[v]=_________; FAULT
EnQueue(Q,w);