C语言实现图的广度优先搜索遍历算法
/* 程序1：邻接表的dfs,bfs 其中n是点的个数,m是边的个数,你需要输入m条有向边，如果要无向只需要反过来多加一遍即可。*/#include #include #define MAXM 100000#define MAXN 10000int next[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;void input_data(){ scanf("%d%d",&n,&m); int i,x,y; for (i=1;i#include #define MAXN 1000int n,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];void input_data(){ scanf("%d%d",&n,&m); int i; for (i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); w[x][0]++; w[x][w[x][0]]=y; }}void pre(){ memset(flag,0,sizeof(flag)); pd=0;}void dfs(int x){ flag[x]=1; if (!pd) { pd=1; printf("%d",x); }else printf(" %d",x); int i; for (i=1;i<=w[x][0];i++) { int y=w[x][i]; if (!flag[y]) dfs(y); }}void bfs(int t){ int head=0,tail=1; dl[1]=t;flag[t]=1; while (head<tail) { int x=dl[++head]; if (!pd) { pd=1; printf("%d",x); }else printf(" %d",x); int i; for (i=1;i<=w[x][0];i++) { int y=w[x][i]; if (!flag[y]) { flag[y]=1; dl[++tail]=y; } } }}int main(){ input_data(); printf("图的深度优先遍历结果:"); pre(); int i; for (i=1;i<=n;i++) if (!flag[i]) dfs(i); printf("
---------------------------------------------------------------
"); printf("图的广度优先遍历结果:"); pre(); for (i=1;i<=n;i++) if (!flag[i]) bfs(i); printf("
-----------------------------end--------------------------------
"); return 0;}
给你一个作为参考吧
#include
#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个顶点.
",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条弧.
",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=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("
广度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("
深度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G);
printf("
程序结束.
");
}
queue<node> q;
q.push(start);
bool canVisit[][];
node cur;
while(!q.empty()){
cur = q.top();
q.pop();
foreach(node is connected by cur){
if(canVisit[node.x][node.y])
{
printf("访问结点(%d,%d)",node.x,node.y);
canVisit[node.x][node.y]=false;
q.push(node);
}
}
}
...
编程实现以邻接表或邻接矩阵为存储结构,图的广度和深度优先搜索_百度...
\/ 图的遍历演示 以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历.以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集.\/ include<iostream> include <string.h> include <malloc.h> include <conio.h> using namespace std;int visited[30];define MAX_...
常见算法5、广度优先搜索 Breadth-First Search
若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即 广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形。例：假如你需要在你的人际关系网中寻找是否有职业为医生的人，图如下：而使用广度优先搜索工作原理大概如下 ：1、Python 3 ：...
深度优先和广度优先各有什么特点?
深度优先遍历（DFS）和广度优先遍历（BFS）是两种遍历图的方法，它们各自具有以下特点：
深度优先遍历（DFS）：1. 沿着一条路径一直向前，直到达到最深的顶点，然后回溯到上一个顶点，再选择另一条路径继续遍历。2. 采用递归和回溯的方式实现遍历过程。 3. 优先遍历深度较深的顶点，即先...
八数码问题 C语言 广度优先 其他也OK
nclude "stdio.h"typedef int datatype; \/*假定线性表元素的类型为整型*\/ define maxsize 1024 \/*假定线性表的最大长度为1024*\/ define n 100 \/* 图的顶点最大个数 *\/ typedef char VEXTYPE; \/* 顶点的数据类型 *\/ typedef float ADJTYPE; \/* 权值类型 *\/ typedef stru...
搜索算法三广度优先搜索
为了优化重复状态的检测，可以利用哈希表，通过二进制值映射状态，形成一个大小为2^16的表，来快速判断状态是否已存在，实现O(1)的判重。这种方法大大降低了时间复杂度。进一步考虑，可以采用双向广度优先搜索，即从初始状态和目标状态同时扩展，一旦遇到相同的扩展节点，就可以立即停止扩展，从而避免无用的...
请描述广度优先搜索的性质
3、广度优先搜索使用队列（Queue）数据结构来实现。在每一层中，它会将所有未被访问的顶点加入队列中，然后重复执行以下操作：从队列中取出一个顶点，访问它，并将其相邻的未访问过的顶点加入队列中。4、广度优先搜索可以用于寻找图中的最短路径问题，因为它会先访问离起始顶点最近的顶点，从而可以更快地...
C语言编写程序实现图的遍历操作
1.实现深度优先和广度优先两种遍历算法。2.要求输入图的顶点数,边数,边的偶对,建立图的邻接表。3.为了测试图的邻接表建立的是否正确,要求实现邻接表输出功能。4.输入用户指定的起... 1. 实现深度优先和广度优先两种遍历算法。 2. 要求输入图的顶点数,边数,边的偶对,建立图的邻接表。3. 为了测试图的邻接...
...采用邻接表结构存储,要求编写算法实现广度优先搜索策略遍历图中所...
include<stdio.h> include<stdlib.h> include<conio.h> include<math.h> define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define OVERFLOW -2 define NULL 0 typedef int Status;typedef struct Node { int elem;struct Node *next;}Node,*QNode;typedef struct { QNode front;Q...
图的深度优先遍历和广度优先遍历所得序列是否唯一?有实例最好,谢谢哈...
这个图的深度优先搜索结果可以是 ABEFCD或者ADCBFE就看你对于同一层的节点的优先顺序，不过一般默认的是从左到 右，所以一般会写ABEFCD 它的广度优先搜索结果可以是 ABCDEF 或者 ADCBFE也看对同一层节点的搜索顺序。一般的顺序也是从左到右，所以一般会写ABCDEF ...
图- 生成树和最小生成树 - 生成树
①图的广度优先生成树的树高不会超过该图其它生成树的高度 ②图的生成树不惟一 从不同的顶点出发进行遍历 可以得到不同的生成树 生成树的通用定义 若从图的某顶点出发 可以系统地访问到图中所有顶点 则遍历时经过的边和图的所有顶点所构成的子图 称作该图的生成树 (此 定义不仅仅适用于无向图 对...
公党琥乙： 深度优先遍历算法(Depth-first-search),重点关注的是图的连通性(connectivity),即从图中给定的一点都能访问到哪些点.不仅如此,在遍历这些点的过程中,通过记录访问次序,可以实现其他功能,比如测试该图是否有闭环等. 广度优先...
西岗区15595405843： 广度优先搜索C语言算法 - ？
公党琥乙： 它没有固定的写法, 但是大框都差不多, 一定要使用队列, 因为队列的存在可以维护程序按照广度优先的方式进行搜索.即层次遍历 可以给你一份我作过的一个题的代码,大体上就是这个样子/****************************************************\ * * ...
西岗区15595405843： c语言图的遍历,邻接表存储,深度,广度优先遍历 - ？
公党琥乙： (1) 图的建立,按采用邻接表作为存储结构. (2) 从指定顶点出发进行深度优先搜索遍历. (3) 从指定顶点出发进行广度优先搜索遍历.#include＂stdio.h＂ #include＂string.h＂ #include＂stdlib.h＂ #include＂math.h＂#define MAX_INT 1000 #...
西岗区15595405843： 求一个C语言编程,图的遍历,深度优先和广度优先搜索的程序.要浅显易懂的~~~~？
公党琥乙： 给你一个作为参考吧 #include <iostream> #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) //队列长度 using namespace std; bool *visited; //访问标志数组 //图的邻接矩阵存储结构 typedef struct...
西岗区15595405843： 图的广度优先遍历的C语言程序(有头文件的) - ？
公党琥乙： // bo7-2.cpp 图的邻接表存储(存储结构由c7-2.h定义)的基本操作(15个) int LocateVex(ALGraph G,VertexType u) { // 初始条件: 图G存在,u和G中顶点有相同特征 // 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 int i; ...
西岗区15595405843： C语言编程 图的创建与遍历 - ？
公党琥乙： 在C语言编程中,图的创建和遍历: #include<stdio.h> #define N 20 #define TRUE 1 #define FALSE 0 int visited[N]; typedef struct /*队列的定义*/ { int data[N]; int front,rear; }queue; typedef struct /*图的邻接矩e799bee5baa6e4b893e5b19e...
西岗区15595405843： 求c语言图的深度优先遍历算法 - ？
公党琥乙： //两个算法使用的全局变量 --- bool visited[MAX_VERTEX_NUM]; // 访问标志数62616964757a686964616fe59b9ee7ad9431333264663039组 Status (* VisitFunc)(int v); // 函数变量 void DFSTraverse(Graph G, Status (*Visit)(int v)) {// 对图G作...
西岗区15595405843： C语言图的创建和遍历算法,紧急 - ？
公党琥乙： 图的遍历是指按某条搜索路径访问图中每个结点,使得每个结点均被访问一次,而且仅被访问一次.图的遍历有深度遍历算法和广度遍历算法,最近阿杰做了关于图的遍历的算法,下面是图的遍历深度优先的算法(C语言程序): #include#...
西岗区15595405843： 急需建立无向图的邻接表,并实现该图的广度优先遍历(C语言代码) 如果可以运行追加分数？
公党琥乙： 我编写了一个你看看吧!应该没有什么问题. #include<stdio.h> #include<malloc.h> #define NULL 0 #define maxvernum 100 typedef struct node { int adjvex; struct node *next; }nodetype; typedef struct frontnode { int data; struct node *next...
西岗区15595405843： 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; //顶点...
