bfs演算法c語言

① 求圖的深度優先遍歷程序 c語言版

鄰接表表示的圖：#include"stdio.h"
#include"stdlib.h"#define MaxVertexNum 50 //定義最大頂點數typedef struct node{ //邊表結點
int adjvex; //鄰接點域
struct node *next; //鏈域
}EdgeNode;
typedef struct vnode{ //頂點表結點
char vertex; //頂點域
EdgeNode *firstedge; //邊表頭指針
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是鄰接表類型
typedef struct {
AdjList adjlist; //鄰接表
int n,e; //圖中當前頂點數和邊數
} ALGraph; //圖類型//=========建立圖的鄰接表=======
void CreatALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s; //定義邊表結點
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //讀入頂點數和邊數
fflush(stdin); //清空內存緩沖
printf("Input Vertex string:");
for(i=0;i<G->n;i++) //建立邊表
{
scanf("%c",&a);
G->adjlist[i].vertex=a; //讀入頂點信息
G->adjlist[i].firstedge=NULL; //邊表置為空表
}
printf("Input edges,Creat Adjacency List\n");
for(k=0;k<G->e;k++) { //建立邊表
scanf("%d%d",&i,&j); //讀入邊（Vi，Vj）的頂點對序號
s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成邊表結點
s->adjvex=j; //鄰接點序號為j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s; //將新結點*S插入頂點Vi的邊表頭部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //鄰接點序號為i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s; //將新結點*S插入頂點Vj的邊表頭部
}
}
//=========定義標志向量，為全局變數=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度優先遍歷的遞歸演算法======
void DFSM(ALGraph *G,int i)
{//以Vi為出發點對鄰接鏈表表示的圖G進行DFS搜索
EdgeNode *p;
printf("%c",G->adjlist[i].vertex); //訪問頂點Vi
visited[i]=TRUE; //標記Vi已訪問
p=G->adjlist[i].firstedge; //取Vi邊表的頭指針
while(p) { //依次搜索Vi的鄰接點Vj，這里j=p->adjvex
if(! visited[p->adjvex]) //若Vj尚未被訪問
DFSM(G,p->adjvex); //則以Vj為出發點向縱深搜索
p=p->next; //找Vi的下一個鄰接點
}
}
void DFS(ALGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未訪問過
DFSM(G,i); //以Vi為源點開始DFS搜索
} //==========BFS：廣度優先遍歷=========
void BFS(ALGraph *G,int k)
{ //以Vk為源點對用鄰接鏈表表示的圖G進行廣度優先搜索
int i,f=0,r=0; EdgeNode *p;
int cq[MaxVertexNum]; //定義FIFO隊列
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<=G->n;i++)
cq[i]=-1; //初始化標志向量
printf("%c",G->adjlist[k].vertex); //訪問源點Vk
visited[k]=TRUE;
cq[r]=k; //Vk已訪問，將其入隊。注意，實際上是將其序號入隊
while(cq[f]!=-1) { // 隊列非空則執行
i=cq[f]; f=f+1; //Vi出隊
p=G->adjlist[i].firstedge; //取Vi的邊表頭指針
while(p) { //依次搜索Vi的鄰接點Vj（令p->adjvex=j）
if(!visited[p->adjvex]) { //若Vj未訪問過
printf("%c",G->adjlist[p->adjvex].vertex); //訪問Vj
visited[p->adjvex]=TRUE;
r=r+1; cq[r]=p->adjvex; //訪問過的Vj入隊
}
p=p->next; //找Vi的下一個鄰接點
}
}//endwhile
}
//==========主函數===========
void main()
{
//int i;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
printf("Print Graph DFS: ");
DFS(G);
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3);
printf("\n");
}鄰接矩陣表示的圖：
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定義最大頂點數
typedef struct{
char vexs[MaxVertexNum]; //頂點表
int edges[MaxVertexNum][MaxVertexNum]; //鄰接矩陣，可看作邊表
int n,e; //圖中的頂點數n和邊數e
}MGraph; //用鄰接矩陣表示的圖的類型
//=========建立鄰接矩陣=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //輸入頂點數和邊數
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i<G->n;i++)
{
scanf("%c",&a);
G->vexs[i]=a; //讀入頂點信息，建立頂點表
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0; //初始化鄰接矩陣
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;k<G->e;k++) { //讀入e條邊，建立鄰接矩陣
scanf("%d%d",&i,&j); //輸入邊（Vi，Vj）的頂點序號
G->edges[i][j]=1;
G->edges[j][i]=1; //若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句
}
}
//=========定義標志向量，為全局變數=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度優先遍歷的遞歸演算法======
void DFSM(MGraph *G,int i)
{ //以Vi為出發點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣
int j;
printf("%c",G->vexs[i]); //訪問頂點Vi
visited[i]=TRUE; //置已訪問標志
for(j=0;j<G->n;j++) //依次搜索Vi的鄰接點
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未訪問過，故Vj為新出發點
}
void DFS(MGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未訪問過
DFSM(G,i); //以Vi為源點開始DFS搜索
}
//===========BFS：廣度優先遍歷=======
void BFS(MGraph *G,int k)
{ //以Vk為源點對用鄰接矩陣表示的圖G進行廣度優先搜索
int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定義隊列
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
cq[i]=-1; //隊列初始化
printf("%c",G->vexs[k]); //訪問源點Vk
visited[k]=TRUE;
cq[r]=k; //Vk已訪問，將其入隊。注意，實際上是將其序號入隊
while(cq[f]!=-1) { //隊非空則執行
i=cq[f]; f=f+1; //Vf出隊
for(j=0;j<G->n;j++) //依次Vi的鄰接點Vj
if(!visited[j] && G->edges[i][j]==1) { //Vj未訪問
printf("%c",G->vexs[j]); //訪問Vj
visited[j]=TRUE;
r=r+1; cq[r]=j; //訪問過Vj入隊
}
}
}
//==========main=====
void main()
{
//int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //為圖G申請內存空間
CreatMGraph(G); //建立鄰接矩陣
printf("Print Graph DFS: ");
DFS(G); //深度優先遍歷
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3); //以序號為3的頂點開始廣度優先遍歷
printf("\n");
}

② 用C語言編寫三個演算法，BFS或DFS，爬山演算法，遺傳演算法實現八皇後問題

網路演算法名，加上八皇後
比如
BFS 八皇後問題 C語言。
或者
遺傳演算法 八皇後問題 C語言

然後根據搜索結果 就可以得到演算法和代碼了。

③ 數據結構C語言版 圖的遍歷 DFS和BFS演算法，用鄰接矩陣儲存 急阿在線等 求大神指點

#include <iostream>
#include<string.h>
#include<stack>
#include<queue>
const int Max=100;
const int VISITED=101010;
const int UNVISITED=111111;
const int AFFINITY=101010;
const int INFINITY=111111;
using namespace std;
class Edge
{
public:
int start;
int end;
int weight;

Edge(int st=0,int en=0,int w=0):start(st),end(en),weight(w){}
bool operator>(Edge oneEdge){return weight>oneEdge.weight?true:false;}
bool operator<(Edge oneEdge){return weight<oneEdge.weight?true:false;}
bool operator!=(Edge oneEdge)
{
if(weight!=oneEdge.weight||start!=oneEdge.start||end!=oneEdge.end)
return true;
return false;
}

};

class AdjGraf
{
private:
int verticesNum;
int edgeNum;

int **matrix;

int *Mark;
public:

AdjGraf(int vert)
{
int i=0,j=0;
verticesNum=vert;
matrix=(int**)new int*[vert];
for(i=0;i<vert;i++)
matrix[i]=new int[vert];

Mark=new int[vert];
for(i=0;i<vert;i++)
for(j=0;j<vert;j++)
{
matrix[i][j]=0;

}
for( int m=0;m<verticesNum;m++)

Mark[m]=UNVISITED;

}

~AdjGraf();
//返回與頂點oneVertex相關聯的第一條邊
Edge FirstEdge(int oneVertex);
//返回與邊PreEdge有相同關聯頂點oneVertex的下一條邊
Edge NextEdge( Edge preEdge);

//添加一條邊
void setEdge(int fromVertex,int toVertex,int weight);
//刪一條邊
void delEdge(int fromVertex,int toVertex);
//如果oneEdge是邊則返回TRUE，否則返回FALSE
bool IsEdge( Edge oneEdge)
{
if(oneEdge.start>=0&&oneEdge.start<verticesNum&&
oneEdge.end>=0&&oneEdge.end<verticesNum)
return true;
else return false;
}
//返回邊oneEdge的始點
int FromVertex(Edge oneEdge){return oneEdge.start;}
//返回邊oneEdge的終點
int ToVertex(Edge oneEdge){return oneEdge.end;}
//返回邊oneEdge的權
int Weight(Edge oneEdge){return oneEdge.weight;}
void visit(int i){cout<<i+1<<" ";}
void BFS(int i=1);
void DFS(int i);
void DFSTraverse(int v);
void DFSNoReverse(int f=1);

Edge UNVISITEDEdge(int f);
};

AdjGraf::~AdjGraf()
{
for(int i=0;i<verticesNum;i++)
delete[]matrix[i];
delete[]matrix;
}

Edge AdjGraf::FirstEdge(int oneVertex)
{ int i;
Edge tempEdge;
tempEdge.start=oneVertex;
for( i=0;i<verticesNum;i++)
if(matrix[oneVertex][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[oneVertex][i];
return tempEdge;
}

Edge AdjGraf ::NextEdge( Edge preEdge)
{
Edge tempEdge;
tempEdge.start=preEdge.start;
int i=0;
for(i=preEdge.end+1;i<verticesNum;i++)
if(matrix[preEdge.start][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[preEdge.start][i];

return tempEdge;

}

void AdjGraf::setEdge(int fromVertex,int toVertex,int weight)
{
if(matrix[fromVertex-1][toVertex-1]==0)

edgeNum++;
matrix[fromVertex-1][toVertex-1]=weight;

}

void AdjGraf::delEdge(int fromVertex,int toVertex)
{
if(matrix[fromVertex][toVertex]==0)
edgeNum--;
matrix[fromVertex][toVertex]=0;

}
/*************遞歸實現深度優先****************/
void AdjGraf::DFS(int i)
{

visit(i);
Mark[i]=VISITED;
for(Edge e=FirstEdge(i);IsEdge(e);e=NextEdge(e))
if(Mark[ToVertex(e)] == UNVISITED)
DFS(ToVertex(e));

}
void AdjGraf::DFSTraverse(int v)
{
v--;
int i;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
for(i=v;i<v+verticesNum;i++)
if (Mark[i]== UNVISITED)
DFS(i);
}

Edge AdjGraf::UNVISITEDEdge(int f)
{ int i;

for( Edge e=FirstEdge(f);IsEdge(e);e=NextEdge(e))
if(Mark[e.end]==UNVISITED)
return e;

return Edge(verticesNum,verticesNum,0) ;

}
/*************非遞歸實現深度優先**************/
void AdjGraf::DFSNoReverse(int f)
{
f--;
int i,counter=0,j,flag;
stack<int>Temp;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
flag=f;
while(counter<12)
{

while(flag!=verticesNum&&IsEdge(UNVISITEDEdge(flag))||!Temp.empty())
{
// Edge tempEdge=UNVISITEDEdge(j);
while(flag!=verticesNum&&Mark[flag]==UNVISITED)
{

visit(flag);
Mark[flag]=VISITED;
Temp.push(flag);
flag=UNVISITEDEdge(flag).end;
}

if(!Temp.empty())
{

flag=UNVISITEDEdge(Temp.top()).end;
Temp.pop();
}

}

if(Mark[counter]==UNVISITED) flag=counter;
else counter++;
}
}

/*************非遞歸實現廣度優先**************/
void AdjGraf::BFS(int v)
{
int i;
v--;
for( i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;

queue<int>tempqueue;
i=0;
/*********v先從指定位置開始，然後從v=0,1,2......
依次檢查是否有孤立結點*****************/
while(i<verticesNum)
{
tempqueue.push(v);
while(!tempqueue.empty())
{
v=tempqueue.front();
tempqueue.pop();
if(Mark[v]==UNVISITED)
{
visit(v);
Mark[v]=VISITED;

for(Edge e=FirstEdge(v);IsEdge(e);e=NextEdge(e))
{
v=ToVertex(e);
tempqueue.push(v);

}

}

}
/***********防止出現孤立點****************/
if(Mark[i]==VISITED) i++;
else v=i;
}

}

int main()
{
AdjGraf Graph(12);
Graph.setEdge(1,2,1);
Graph.setEdge(2,1,1);
Graph.setEdge(1,3,5);
Graph.setEdge(3,1,5);/** V1 V12 V11 */
Graph.setEdge(2,4,3);/** / \ / \ */
Graph.setEdge(4,2,3);/** v2 v3 V10 V9 */
Graph.setEdge(2,5,7);/** / \ / \ */
Graph.setEdge(5,2,7);/** v4 v5 v6-v7 */
Graph.setEdge(4,8,4);/** \ / */
Graph.setEdge(8,4,4);/** v8 */
Graph.setEdge(5,8,3);
Graph.setEdge(8,5,3);
Graph.setEdge(3,6,2);
Graph.setEdge(6,3,2);
Graph.setEdge(3,7,1);
Graph.setEdge(7,3,1);
Graph.setEdge(6,7,6);
Graph.setEdge(7,6,6);
Graph.setEdge(12,9,6);
Graph.setEdge(9,12,6);
Graph.setEdge(12,10,6);
Graph.setEdge(10,12,6);
Graph.setEdge(11,11,6);
cout<<"DFSTraverse:"<<endl;
Graph.DFSTraverse(3);
cout<<endl;
cout<<"DFSNoReverse:"<<endl;
Graph.DFSNoReverse(3);
cout<<endl;
cout<<"BFS:"<<endl;
Graph.BFS(3);
cout<<endl;

return 0;

}

以上代碼運行環境codeblocks 程序採用DFS遞歸演算法 DFS非遞歸演算法 BFS非遞歸演算法
望採納~

④ 演算法上機實驗如圖所示，用c語言實現

#include<stdio.h>

#include<stdlib.h>

struct node {

int data;//數據域

struct node *R;//左孩子

struct node *L;//右孩子

};

int a[] = {1, 2, 3, -1, -1, -1, 4, 5,7,-1,-1,-1,6,-1,-1};//二叉樹序列

int k = 0;

node* buildTree(node *tree) {//創建二叉樹

int data=a[k++];//

if (data== - 1) {//-1代表空結點

tree = NULL;

}

else {//非空結點

tree = (node*)malloc(sizeof(node));//分配內存

tree->data = data;//數據域賦值

tree->L = tree->R = NULL;//左右孩子賦空

tree->L=buildTree(tree->L);//前往左孩子

tree->R=buildTree(tree->R);//前往右孩子

}

return tree;//返回根結點地址

}

void dfs1(node *tree) {//前序遍歷

if (tree) {

printf("%d ", tree->data);

dfs1(tree->L);

dfs1(tree->R);

}

}

void dfs2(node *tree) {//中序

if (tree) {

dfs2(tree->L);

printf("%d ", tree->data);

dfs2(tree->R);

}

}

void dfs3(node *tree) {//後序

if (tree) {

dfs3(tree->L);

dfs3(tree->R);

printf("%d ", tree->data);

}

}

void level(node *tree){

//層次遍歷，類似與bfs(廣度優先搜索)

//需要一個隊列作為輔助數據結構

node* q[100];//隊列

int f=0,r=0;//頭，尾指針

q[r++]=tree;//根結點入隊

while(f!=r){

node *t=q[f++];//出隊

printf("%d ",t->data);//輸出

if(t->L!=NULL){//非空左孩子入隊

q[r++]=t->L;

}

if(t->R!=NULL){//非空右孩子入隊

q[r++]=t->R;

}

}

}

int count(node *tree){

if(tree==NULL){

return 0;

}

else{

int n,m;

n=count(tree->L);//左子樹結點個數

m=count(tree->R);//右子樹結點個數

return n+m+1;//返回左右子樹結點個數之和

}

}

int main() {

node *tree = NULL;

tree=buildTree(tree);

printf(" 前序遍歷： ");

dfs1(tree);

printf(" 中序遍歷： ");

dfs2(tree);

printf(" 後序遍歷： ");

dfs3(tree);

printf(" 層次遍歷： ");

level(tree);

printf(" 二叉樹結點個數：%d",count(tree));

return 0;

}