广度优先搜索与深度优先搜索

广度优先搜索

typedef struct { int que[MaxVertexNum]; int rear,front; }Queue;//广度优先搜索队列的存储结构 int visit[MaxVertexNum];//全局变量数组 void BFS(MGraph &M,int v){ printf("广度优先搜索:"); Queue q; int v1; for(int i=0;i<MaxVertexNum;i++){ visit[i]=0; } q.rear=0; q.front=0; q.que[q.rear++]=v; visit[v]=1; visited(v); while(q.front!=q.rear){ v1=q.que[q.front++]; for(int j=0;j<M.vertexnum;j++){ if(M.Edge[v1][j]!=0&&visit[j]==0){ q.que[q.rear++]=j; visited(j); visit[j]=1; } } } }

深度优先搜索

一.递归深度优先搜索

int visit[MaxVertexNum];//全局变量数组 void DFSTraverse(){ for(int i=0;i<MaxVertexNum;i++){ visit[i]=0;//访问标记数组重置 } printf("递归深度优先搜索:"); } void DFS1(MGraph &M,int v){ visited(v); visit[v]=1; for(int i=0;i<M.vertexnum;i++){ if(M.Edge[v][i]!=0&&visit[i]==0){ DFS1(M,i); } } }

二.非递归深度优先搜索

int visit[MaxVertexNum];//全局变量数组 void DFS1(MGraph &M,int v){ visited(v); visit[v]=1; for(int i=0;i<M.vertexnum;i++){ if(M.Edge[v][i]!=0&&visit[i]==0){ DFS1(M,i); } } }//递归实现深度优先搜索 void DFS2(MGraph &M,int v){ printf("非递归深度优先搜索:"); int flag=0; for(int i=0;i<MaxVertexNum;i++){ visit[i]=0; } visited(v); visit[v]=1; flag++; while(flag!=M.vertexnum){//若flag等于图的点数表示，所有节点已访问完毕 int j; for(j=0;j<M.vertexnum;j++){ if(M.Edge[v][j]!=0&&visit[j]==0){ visited(j); visit[j]=1; flag=flag+1;//若成功访问一次则标志位加1 break; } } v=j; } }

 

转载于:https://www.cnblogs.com/Yshun/p/11374038.html

相关资源：JAVA上百实例源码以及开源项目