Ⅰ 图的遍历（c语言）完整上机代码
//图的遍历算法程序
//图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，程序如下：
#include <iostream>
//#include <malloc.h>
#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;i<G.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;i<G.vexnum;i++){ //初始化顶点
printf("输入顶点%d:",i);
scanf("%c",&G.vexs[i]);
temp=getchar(); //接收回车
}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条弧.\n",G.arcnum);
for(i=0;i<G.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 && k<G.vexnum){ //k合理
for(int i=0;i<G.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 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.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;i<G.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;i<G.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;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n深度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G);
printf("\n程序结束.\n");
}
输出结果为（红色为键盘输入的数据，权值都置为1）：
输入顶点数和弧数:8 9
输入8个顶点.
输入顶点0:a
输入顶点1:b
输入顶点2:c
输入顶点3:d
输入顶点4:e
输入顶点5:f
输入顶点6:g
输入顶点7:h
输入9条弧.
输入弧0:a b 1
输入弧1:b d 1
输入弧2:b e 1
输入弧3:d h 1
输入弧4:e h 1
输入弧5:a c 1
输入弧6:c f 1
输入弧7:c g 1
输入弧8:f g 1
广度优先遍历: a b d h e c f g
深度优先遍历: a b c d e f g h
程序结束.
已经在vc++内运行通过，这个程序已经达到要求了呀~
Ⅱ 广度优先搜索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;
}
Ⅲ A*搜寻算法的代码实现(C语言实现)
用C语言实现A*最短路径搜索算法，作者 Tittup frog(跳跳蛙)。 #include<stdio.h>#include<math.h>#defineMaxLength100 //用于优先队列（Open表）的数组#defineHeight15 //地图高度#defineWidth20 //地图宽度#defineReachable0 //可以到达的结点#defineBar1 //障碍物#definePass2 //需要走的步数#defineSource3 //起点#defineDestination4 //终点#defineSequential0 //顺序遍历#defineNoSolution2 //无解决方案#defineInfinity0xfffffff#defineEast(1<<0)#defineSouth_East(1<<1)#defineSouth(1<<2)#defineSouth_West(1<<3)#defineWest(1<<4)#defineNorth_West(1<<5)#defineNorth(1<<6)#defineNorth_East(1<<7)typedefstruct{ signedcharx,y;}Point;constPointdir[8]={ {0,1},//East {1,1},//South_East {1,0},//South {1,-1},//South_West {0,-1},//West {-1,-1},//North_West {-1,0},//North {-1,1}//North_East};unsignedcharwithin(intx,inty){ return(x>=0&&y>=0 &&x<Height&&y<Width);}typedefstruct{ intx,y; unsignedcharreachable,sur,value;}MapNode;typedefstructClose{ MapNode*cur; charvis; structClose*from; floatF,G; intH;}Close;typedefstruct//优先队列（Open表）{ intlength; //当前队列的长度 Close*Array[MaxLength]; //评价结点的指针}Open;staticMapNodegraph[Height][Width];staticintsrcX,srcY,dstX,dstY; //起始点、终点staticCloseclose[Height][Width];//优先队列基本操作voidinitOpen(Open*q) //优先队列初始化{ q->length=0; //队内元素数初始为0}voidpush(Open*q,Closecls[Height][Width],intx,inty,floatg){ //向优先队列（Open表）中添加元素 Close*t; inti,mintag; cls[x][y].G=g; //所添加节点的坐标 cls[x][y].F=cls[x][y].G+cls[x][y].H; q->Array[q->length++]=&(cls[x][y]); mintag=q->length-1; for(i=0;i<q->length-1;i++) { if(q->Array[i]->F<q->Array[mintag]->F) { mintag=i; } } t=q->Array[q->length-1]; q->Array[q->length-1]=q->Array[mintag]; q->Array[mintag]=t; //将评价函数值最小节点置于队头}Close*shift(Open*q){ returnq->Array[--q->length];}//地图初始化操作voidinitClose(Closecls[Height][Width],intsx,intsy,intdx,intdy){ //地图Close表初始化配置 inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { cls[i][j].cur=&graph[i][j]; //Close表所指节点 cls[i][j].vis=!graph[i][j].reachable; //是否被访问 cls[i][j].from=NULL; //所来节点 cls[i][j].G=cls[i][j].F=0; cls[i][j].H=abs(dx-i)+abs(dy-j); //评价函数值 } } cls[sx][sy].F=cls[sx][sy].H; //起始点评价初始值 // cls[sy][sy].G=0; //移步花费代价值 cls[dx][dy].G=Infinity;}voidinitGraph(constintmap[Height][Width],intsx,intsy,intdx,intdy){ //地图发生变化时重新构造地 inti,j; srcX=sx; //起点X坐标 srcY=sy; //起点Y坐标 dstX=dx; //终点X坐标 dstY=dy; //终点Y坐标 for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { graph[i][j].x=i;//地图坐标X graph[i][j].y=j;//地图坐标Y graph[i][j].value=map[i][j]; graph[i][j].reachable=(graph[i][j].value==Reachable); //节点可到达性 graph[i][j].sur=0;//邻接节点个数 if(!graph[i][j].reachable) { continue; } if(j>0) { if(graph[i][j-1].reachable) //left节点可以到达 { graph[i][j].sur|=West; graph[i][j-1].sur|=East; } if(i>0) { if(graph[i-1][j-1].reachable &&graph[i-1][j].reachable &&graph[i][j-1].reachable) //up-left节点可以到达 { graph[i][j].sur|=North_West; graph[i-1][j-1].sur|=South_East; } } } if(i>0) { if(graph[i-1][j].reachable) //up节点可以到达 { graph[i][j].sur|=North; graph[i-1][j].sur|=South; } if(j<Width-1) { if(graph[i-1][j+1].reachable &&graph[i-1][j].reachable &&map[i][j+1]==Reachable)//up-right节点可以到达 { graph[i][j].sur|=North_East; graph[i-1][j+1].sur|=South_West; } } } } }}intbfs(){ inttimes=0; inti,curX,curY,surX,surY; unsignedcharf=0,r=1; Close*p; Close*q[MaxLength]={&close[srcX][srcY]}; initClose(close,srcX,srcY,dstX,dstY); close[srcX][srcY].vis=1; while(r!=f) { p=q[f]; f=(f+1)%MaxLength; curX=p->cur->x; curY=p->cur->y; for(i=0;i<8;i++) { if(!(p->cur->sur&(1<<i))) { continue; } surX=curX+dir[i].x; surY=curY+dir[i].y; if(!close[surX][surY].vis) { close[surX][surY].from=p; close[surX][surY].vis=1; close[surX][surY].G=p->G+1; q[r]=&close[surX][surY]; r=(r+1)%MaxLength; } } times++; } returntimes;}intastar(){ //A*算法遍历 //inttimes=0; inti,curX,curY,surX,surY; floatsurG; Openq;//Open表 Close*p; initOpen(&q); initClose(close,srcX,srcY,dstX,dstY); close[srcX][srcY].vis=1; push(&q,close,srcX,srcY,0); while(q.length) { //times++; p=shift(&q); curX=p->cur->x; curY=p->cur->y; if(!p->H) { returnSequential; } for(i=0;i<8;i++) { if(!(p->cur->sur&(1<<i))) { continue; } surX=curX+dir[i].x; surY=curY+dir[i].y; if(!close[surX][surY].vis) { close[surX][surY].vis=1; close[surX][surY].from=p; surG=p->G+sqrt((curX-surX)*(curX-surX)+(curY-surY)*(curY-surY)); push(&q,close,surX,surY,surG); } } } //printf("times:%d ",times); returnNoSolution;//无结果}constintmap[Height][Width]={ {0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,1}, {0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1}, {0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1}, {0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1}, {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0}, {0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1}, {0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}};constcharSymbol[5][3]={"□","▓","▽","☆","◎"};voidprintMap(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { printf("%s",Symbol[graph[i][j].value]); } puts(""); } puts("");}Close*getShortest(){ //获取最短路径 intresult=astar(); Close*p,*t,*q=NULL; switch(result) { caseSequential: //顺序最近 p=&(close[dstX][dstY]); while(p) //转置路径 { t=p->from; p->from=q; q=p; p=t; } close[srcX][srcY].from=q->from; return&(close[srcX][srcY]); caseNoSolution: returnNULL; } returnNULL;}staticClose*start;staticintshortestep;intprintShortest(){ Close*p; intstep=0; p=getShortest(); start=p; if(!p) { return0; } else { while(p->from) { graph[p->cur->x][p->cur->y].value=Pass; printf("（%d，%d）→ ",p->cur->x,p->cur->y); p=p->from; step++; } printf("（%d，%d） ",p->cur->x,p->cur->y); graph[srcX][srcY].value=Source; graph[dstX][dstY].value=Destination; returnstep; }}voidclearMap(){ //ClearMapMarksofSteps Close*p=start; while(p) { graph[p->cur->x][p->cur->y].value=Reachable; p=p->from; } graph[srcX][srcY].value=map[srcX][srcY]; graph[dstX][dstY].value=map[dstX][dstY];}voidprintDepth(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { if(map[i][j]) { printf("%s",Symbol[graph[i][j].value]); } else { printf("%2.0lf",close[i][j].G); } } puts(""); } puts("");}voidprintSur(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { printf("%02x",graph[i][j].sur); } puts(""); } puts("");}voidprintH(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { printf("%02d",close[i][j].H); } puts(""); } puts("");}intmain(intargc,constchar**argv){ initGraph(map,0,0,0,0); printMap(); while(scanf("%d%d%d%d",&srcX,&srcY,&dstX,&dstY)!=EOF) { if(within(srcX,srcY)&&within(dstX,dstY)) { if(shortestep=printShortest()) { printf("从（%d，%d）到（%d，%d）的最短步数是:%d ", srcX,srcY,dstX,dstY,shortestep); printMap(); clearMap(); bfs(); //printDepth(); puts((shortestep==close[dstX][dstY].G)?"正确":"错误"); clearMap(); } else { printf("从（%d，%d）不可到达（%d，%d） ", srcX,srcY,dstX,dstY); } } else { puts("输入错误！"); } } return(0);}
Ⅳ C语言对于用bfs求最短路径的同时，如何记录路径
比如地图为二维数组map[n][m],记录起点到每个点的最短路径(这个bfs得到),那么可以从终点倒推,即若终点为x1,y1,dist[x1][y1]=d,(xi ,yi)为与(x1,y1)相连的点,若dist[xi][yi]==d-1,那么可以从(xi,yi)走到(x1,y1),然后继续找下去,直到找到起点.可以dfs实现.
Ⅳ 数据结构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语言编写三个算法，BFS或DFS，爬山算法，遗传算法实现八皇后问题
网络算法名，加上八皇后
比如
BFS 八皇后问题 C语言。
或者
遗传算法 八皇后问题 C语言
然后根据搜索结果 就可以得到算法和代码了。
Ⅶ c语言BFS、DFS函数代码
这个没有固定的形式
根据具体的情况来写
关键是思想
bfs是先扩展节点再增加深度
dfs是先增加深度,到底后返回再扩展节点
一个是使用大量空间 另一个则是遍历所有路径,相对的更费时间
Ⅷ 求大神帮写一个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语言编写程序实现图的遍历操作
楼主你好，下面是源程序！
/*/////////////////////////////////////////////////////////////*/
/* 图的深度优先遍历 */
/*/////////////////////////////////////////////////////////////*/
#include <stdlib.h>
#include <stdio.h>
struct node /* 图顶点结构定义 */
{
int vertex; /* 顶点数据信息 */
struct node *nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[9]; /* 图形顶点数组 */
int visited[9]; /* 遍历标记数组 */
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode; /*指向新节点的指针定义*/
graph ptr;
int from; /* 边的起点 */
int to; /* 边的终点 */
int i;
for ( i = 0; i < num; i++ ) /* 读取边线信息，插入邻接表*/
{
from = node[i][0]; /* 边线的起点 */
to = node[i][1]; /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入节点 */
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 记录已遍历过 */
printf("vertex[%d]\n",current); /* 输出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex); /* 递回遍历呼叫 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
void main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
clrscr();
for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 指针为空 */
visited[i] = 0; /* 设定遍历初始标志 */
}
creategraph(node,20); /* 建立邻接表 */
printf("Content of the gragh's ADlist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 印出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("\nThe end of the dfs are:\n");
dfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
puts(" Press any key to quit...");
getch();
}
/*//////////////////////////////////////////*/
/* 图形的广度优先搜寻法 */
/* ///////////////////////////////////////*/
#include <stdlib.h>
#include <stdio.h>
#define MAXQUEUE 10 /* 队列的最大容量 */
struct node /* 图的顶点结构定义 */
{
int vertex;
struct node *nextnode;
};
typedef struct node *graph; /* 图的结构指针 */
struct node head[9]; /* 图的顶点数组 */
int visited[9]; /* 遍历标记数组 */
int queue[MAXQUEUE]; /* 定义序列数组 */
int front = -1; /* 序列前端 */
int rear = -1; /* 序列后端 */
/***********************二维数组向邻接表的转化****************************/
void creategraph(int node[20][2],int num)
{
graph newnode; /* 顶点指针 */
graph ptr;
int from; /* 边起点 */
int to; /* 边终点 */
int i;
for ( i = 0; i < num; i++ ) /* 第i条边的信息处理 */
{
from = node[i][0]; /* 边的起点 */
to = node[i][1]; /* 边的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 顶点内容 */
newnode->nextnode = NULL; /* 设定指针初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入第i个节点的链表尾部 */
}
}
/************************ 数值入队列************************************/
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 current)
{
graph ptr;
/* 处理第一个顶点 */
enqueue(current); /* 将顶点存入队列 */
visited[current] = 1; /* 已遍历过记录标志置疑1*/
printf(" Vertex[%d]\n",current); /* 打印输出遍历顶点值 */
while ( front != rear ) /* 队列是否为空 */
{
current = dequeue(); /* 将顶点从队列列取出 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /*顶点没有遍历过*/
{
enqueue(ptr->vertex); /* 奖定点放入队列 */
visited[ptr->vertex] = 1; /* 置遍历标记为1 */
printf(" Vertex[%d]\n",ptr->vertex);/* 印出遍历顶点值 */
}
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
}
/*********************** 主程序 ************************************/
/*********************************************************************/
void main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边信息数组 */
{6, 3}, {3, 6},
{2, 4}, {4, 2},
{1, 5}, {5, 1},
{3, 7}, {7, 3},
{1, 7}, {7, 1},
{4, 8}, {8, 4},
{5, 8}, {8, 5},
{2, 8}, {8, 2},
{7, 8}, {8, 7} };
int i;
clrscr();
puts("This is an example of Width Preferred Traverse of Gragh.\n");
for ( i = 1; i <= 8; i++ ) /*顶点结构数组初始化*/
{
head[i].vertex = i;
head[i].nextnode = NULL;
visited[i] = 0;
}
creategraph(node,20); /* 图信息转换，邻接表的建立 */
printf("The content of the graph's allist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf(" vertex%d =>",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 打印输出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("The contents of BFS are:\n");
bfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
puts(" Press any key to quit...");
getch();
}
Ⅹ 正在学习C语言--数据结构，请大家来帮忙
既然有200分，肯定得花点功夫：
所有程序在win-tc和DEV-C++下都运行通过，代码简练，执行正确。
200分这多题，划得来啊。请送分，谢谢。
第一题：
http://..com/question/80603134.html
第三题:
http://www.programfan.com/club/showtxt.asp?id=234730
这里还有固定密码的详细注释程序：
http://..com/question/77796518.html
第四题：
程序超过10000字，无法上传(这一个程序得200分)若有需要，留邮箱密我
第六题：
http://..com/question/79338502.html
第九题：
http://..com/question/80048763.html
第十题：
http://..com/question/79375216.html
第五题：递归算法，不是你的要求。
第十二题：图的广度优先遍历
/*******************************************/
/* 图形的广度优先搜寻法 */
/*******************************************/
#include <stdlib.h>
#include <stdio.h>
#define MAXQUEUE 10 /* 队列的最大容量 */
struct node /* 图的顶点结构定义 */
{
int vertex;
struct node *nextnode;
};
typedef struct node *graph; /* 图的结构指针 */
struct node head[9]; /* 图的顶点数组 */
int visited[9]; /* 遍历标记数组 */
int queue[MAXQUEUE]; /* 定义序列数组 */
int front = -1; /* 序列前端 */
int rear = -1; /* 序列后端 */
/***********************二维数组向邻接表的转化****************************/
void creategraph(int node[20][2],int num)
{
graph newnode; /* 顶点指针 */
graph ptr;
int from; /* 边起点 */
int to; /* 边终点 */
int i;
for ( i = 0; i < num; i++ ) /* 第i条边的信息处理 */
{
from = node[i][0]; /* 边的起点 */
to = node[i][1]; /* 边的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 顶点内容 */
newnode->nextnode = NULL; /* 设定指针初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入第i个节点的链表尾部 */
}
}
/************************ 数值入队列************************************/
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 current)
{
graph ptr;
/* 处理第一个顶点 */
enqueue(current); /* 将顶点存入队列 */
visited[current] = 1; /* 已遍历过记录标志置疑1*/
printf(" Vertex[%d]\n",current); /* 打印输出遍历顶点值 */
while ( front != rear ) /* 队列是否为空 */
{
current = dequeue(); /* 将顶点从队列列取出 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /*顶点没有遍历过*/
{
enqueue(ptr->vertex); /* 奖定点放入队列 */
visited[ptr->vertex] = 1; /* 置遍历标记为1 */
printf(" Vertex[%d]\n",ptr->vertex);/* 印出遍历顶点值 */
}
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
}
/*********************** 主程序 ************************************/
/*********************************************************************/
int main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边信息数组 */
{6, 3}, {3, 6},
{2, 4}, {4, 2},
{1, 5}, {5, 1},
{3, 7}, {7, 3},
{1, 7}, {7, 1},
{4, 8}, {8, 4},
{5, 8}, {8, 5},
{2, 8}, {8, 2},
{7, 8}, {8, 7} };
int i;
clrscr();
puts("This is an example of Width Preferred Traverse of Gragh.\n");
for ( i = 1; i <= 8; i++ ) /*顶点结构数组初始化*/
{
head[i].vertex = i;
head[i].nextnode = NULL;
visited[i] = 0;
}
creategraph(node,20); /* 图信息转换，邻接表的建立 */
printf("The content of the graph's allist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf(" vertex%d =>",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 打印输出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("The contents of BFS are:\n");
bfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
puts(" Press any key to quit...");
getch();
return 0;
}
图的深度优先遍历
/***************************************************************/
/* 图的深度优先遍历 */
/***************************************************************/
#include <stdlib.h>
#include <stdio.h>
struct node /* 图顶点结构定义 */
{
int vertex; /* 顶点数据信息 */
struct node *nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[9]; /* 图形顶点数组 */
int visited[9]; /* 遍历标记数组 */
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode; /*指向新节点的指针定义*/
graph ptr;
int from; /* 边的起点 */
int to; /* 边的终点 */
int i;
for ( i = 0; i < num; i++ ) /* 读取边线信息，插入邻接表*/
{
from = node[i][0]; /* 边线的起点 */
to = node[i][1]; /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入节点 */
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 记录已遍历过 */
printf("vertex[%d]\n",current); /* 输出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex); /* 递回遍历呼叫 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
int main()
{
graph ptr; /* 边线数组 */
int node[20][2] = { {1, 2}, {2, 1},
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
clrscr();
for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 指针为空 */
visited[i] = 0; /* 设定遍历初始标志 */
}
creategraph(node,20); /* 建立邻接表 */
printf("Content of the gragh's ADlist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 印出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("\nThe end of the dfs are:\n");
dfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
puts(" Press any key to quit...");
getch();
return 0;
}