您的位置:

c语言广度遍历,广度遍历深度遍历

本文目录一览:

数据结构C语言版 图的广度优先遍历和深度优先遍历 急急急 会查重

#include iostream

#include string

#include queue

using namespace std;

int FirstAdjVex(int v);

int NextAdjVex(int v, int w);

void DFS(int v); //从顶点v开始对图做深度优先遍历, v是顶点数组的下标

void BFS(int v); //从顶点v开始对图做广度优先遍历,v是顶点数组的下标

int find(string a,int n);

int visited[10]={0};

int traver[10][10]={0};

string name[10];

int main()

{

int n,m,i,j,k;

string a,b;

//freopen("Traver.txt","r",stdin);

cinn;

cinm;

for(i=0; in; i++)

{

cina;

name[i] = a;

}

for(i=0; im;i++){

cina;

cinb;

j = find(a,n);

k = find(b,n);

traver[j][k] = 1;

traver[k][j] = 1;

}

for(i=0; in; i++){

if(visited[i] == 0)

DFS(i);

}

cout"\n";

for(i=0; in; i++){

visited[i] = 0;

}

for(i=0; in; i++){

if(visited[i] == 0)

BFS(i);

}

cout"\n";

return 0;

}

//寻找函数

int find(string a,int n){

int i;

for(i=0; in; i++){

if(a == name[i])

return i;

}

return -1;

}

int FirstAdjVex(int v)

{

int i;

//从编号大的邻接点开始访问

for (i = 9; i = 0; i--)

{

if (traver[v][i] == 1)

return i;

}

return -1;

}

int NextAdjVex(int v, int w)

{

int i;

for (i = w - 1; i = 0; i--)

{

if (traver[v][i] == 1)

return i;

}

return -1;

}

void DFS(int v)

{

int w;

//访问顶点v(输出顶点v的名字)

coutname[v]" ";

visited[v] = 1;

//找到顶点v的第一个邻接点w

for (w = FirstAdjVex(v); w = 0; w = NextAdjVex(v, w))

{

//如果w没有访问过,对顶点w做深度优先搜索

if (visited[w] == 0)

DFS(w);

}

}

void BFS(int v) //从顶点v开始对图做广度优先遍历,v是顶点数组的下标

{

int w, u;

queueint myqueue; //定义一个队列,元素是顶点的下标

//把顶点v入队

myqueue.push(v);

coutname[v]" ";

visited[v] = 1;

while (!myqueue.empty())

{//当队列不为空时进入循环

//取队头元素

u = myqueue.front();

//队头元素出队

myqueue.pop();

//把u的所有邻接点入队

w = FirstAdjVex(u);

while (w = 0)

{

if (visited[w] == 0)

{

//访问w

coutname[w]" ";

visited[w] = 1;

//w入队

myqueue.push(w);

}

w = NextAdjVex(u, w);

}

}

}

c语言图的遍历,邻接表存储,深度,广度优先遍历

(1) 图的建立,按采用邻接表作为存储结构。

(2) 从指定顶点出发进行深度优先搜索遍历。

(3) 从指定顶点出发进行广度优先搜索遍历。

#include"stdio.h"

#include"string.h"

#include"stdlib.h"

#include"math.h"

#define MAX_INT 1000

#define MAX_VERTEX_NUM 20

#define MAX_QUEUE_NUMBER 20

typedef struct ArcNode

{

int adjvex;

double adj;

struct ArcNode *nextarc;

}ArcNode;

typedef struct VexNode

{

char szName[40];

ArcNode *firstarc;

}VexNode,AdjList[MAX_VERTEX_NUM];

typedef struct

{

AdjList vexs;

int vexnum,arcnum;

}Net;

//定义队列

typedef struct{

int *elem;

int front, rear;

}Queue;

void InitQueue(Queue Q)

{

Q.elem = new int[MAX_QUEUE_NUMBER];

Q.front = Q.rear = 0;

}

int EmptyQueue(Queue Q)

{

if(Q.front==Q.rear)

return 0;

else

return 1;

}

void DestroyQueue(Queue Q){

delete []Q.elem;

Q.front = Q.rear = 0;

}

void EnterQueue(Queue Q, int e)

{

if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)

Q.elem[Q.rear ] = e;

else

printf("队列满!\n");

Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;

}

void LeaveQueue(Queue Q, int e)

{

if(Q.rear != Q.front)

e = Q.elem[Q.front];

else

printf("队列空!\n");

Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;

}

int LocateVex(Net ga,char *name)

{

int i;

for(i=0;iga.vexnum;i++)

if(strcmp(name,ga.vexs[i].szName)==0)

return i;

return -1;

}

void crt_net(Net ga)

{

ArcNode *p;

char name1[40],name2[40];

int i,j,k;

double w;

printf("请输入顶点数和弧数:");

scanf("%d%d",ga.vexnum,ga.arcnum);

printf("请依次输入顶点名:\n");

for(i=0;iga.vexnum;i++)

{

scanf("%s",ga.vexs[i].szName);

ga.vexs[i].firstarc=NULL;

}

for(k=0;kga.arcnum;k++)

{

printf("请输入相邻的两个定点和权值:");

scanf("%s%s%lf",name1,name2,w);

i=LocateVex(ga,name1);

j=LocateVex(ga,name2);

p=new ArcNode;

p-adjvex=j;

p-adj=w;

p-nextarc=ga.vexs[i].firstarc;

ga.vexs[i].firstarc=p;

}

}

void DFS(Net ga,char *name,int *visited)

{

int v,w;

ArcNode *p;

v=LocateVex(ga,name);

visited[v]=1;

printf("%s ",ga.vexs[v].szName);

p=ga.vexs[v].firstarc;

while(p!=NULL)

{

w=p-adjvex;

if(visited[w]==0)

DFS(ga,ga.vexs[w].szName,visited);

p=p-nextarc;

}

}

void DFSTravel(Net ga,char *name)

{

int v,k=0;

int visited[20];

for(v=0;vga.vexnum;v++)

visited[v]=0;

for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))

{

if(v+1==LocateVex(ga,name))

k++;

if(visited[v]==0)

DFS(ga,ga.vexs[v].szName,visited);

}

}

void BFSTravel(Net ga,char *name)

{

ArcNode *p;

int v,w,u,k=0;

Queue Q;

int visited[20];

for(v=0;vga.vexnum;v++)

visited[v]=0;

InitQueue(Q);

for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))

{

if(v+1==LocateVex(ga,name))

k++;

if(visited[v]==0)

{

visited[v]=1;

printf("%s ",ga.vexs[v].szName);

EnterQueue(Q,v);

while(EmptyQueue(Q)!=0)

{

LeaveQueue(Q,u);

p=ga.vexs[u].firstarc;

while(p!=NULL)

{

w=p-adjvex;

if(visited[w]==0)

{

printf("%s ",ga.vexs[w].szName);

visited[w]=1;

EnterQueue(Q,w);

}

p=p-nextarc;

}

}

}

}

}

void main()

{

char name[40];

Net ga;

crt_net(ga);

printf("请输入深度优先遍历开始点的名:");

scanf("%s",name);

printf("深度优先遍历:");

DFSTravel(ga,name);

printf("\n");

printf("请输入广度优先遍历开始点的名:");

scanf("%s",name);

printf("广度优先遍历:");

BFSTravel(ga,name);

printf("\n");

}

c语言关于图的广度优先遍历

深度优先是沿着一条路走到底,走不通了或到头了,再回溯,再搜索。而广搜是先搜离得最近的,再慢慢搜索远的,队列就是按顺序存,所以开头存的近的,末尾存远的,说白了队列就是从近到远保存数据的,说的不好,希望对你会点帮助。

求助大神,C语言!数据结构 怎么用广度遍历解决任务分配问题,在广度

广度优先搜索要借助于队列来实现,无论图的储存结构是什么。具体算法:1将所有节点标注为未访问状态2从任意一个节点开始,访问该节点(并同时标注为已访问),访问后将该节点入队。3检查队列是否为空,若不空,出队,检查和这个节点有路径并且未被访问的节点,访问,再入队……(回到第二步)广度优先类似于树的层序遍历具体代码:boolvisited[MAX];//该数组用来表示是否下标为i的节点访问过,访问过为true,否则为falsestructAdjNode//边表节点结构{intadj;//邻接点的下标intweigth;//边权值structAdjNode*pNext;};structVertexNode//顶点节点结构{chardata;//数据类型根据需求更改structAdjNode*first;//储存第一个边表节点};typedefstructGraph{intnumE,numV;//当前图的顶点数和边数structVertexNodeVer[MAX];//顶点表}Graph;voidBFSTraverse(GraphG)//G为用邻接表储存的图{for(inti=0;iadj]){printf("%c",G.Ver[p-adj].data);//访问visited[p-adj]=true;//标注为访问过enQueue(q,p-adj);//入队}p=p-pNext;//指针指向下一个邻接点}}}}}

求大神帮写一个c语言图的深度优先遍历,和广度优先遍历??

/*深度优先*/

#includestdio.h

#includestdlib.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;in;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);/*设置指针位置*/

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;i4*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); /*设置指针位置*/

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 "stdio.h"

typedef int datatype; /*假定线性表元素的类型为整型*/

#define maxsize 1024 /*假定线性表的最大长度为1024*/

# define n 100 /* 图的顶点最大个数 */

typedef char VEXTYPE; /* 顶点的数据类型 */

typedef float ADJTYPE; /* 权值类型 */

typedef struct

{ VEXTYPE vexs[n] ; /* 顶点信息数组 */

ADJTYPE arcs[n][n] ; /* 边权数组 */

int num ; /* 顶点的实际个数 */

}GRAPH;

/***********************1。置空图**********************/

void GraphInit(GRAPH *L)

{

L-num=0;

}

/***********************2。求结点数**********************/

int GraphVexs(GRAPH *L)

{

return(L-num);

}

/***********************3。创建图**********************/

void GraphCreate(GRAPH *L)

{

int i,j;

GraphInit(L);

printf("请输入顶点数目:");

scanf("%d",L-num);

printf("请输入各顶点的信息(单个符号):");

for(i=0;iL-num;i++)

{

fflush(stdin);

scanf("%c",L-vexs[i]);

}

printf("请输入边权矩阵的信息:");

for(i=0;iL-num;i++)

{

for(j=0;jL-num;j++)

{

scanf("%f",L-arcs[i][j]);

}

}

printf("图已经创建完毕!");

}

/***********************4。图的输出**********************/

void GraphOut(GRAPH L)

{

int i,j;

printf("\n图的顶点数目为:%d",L.num);

printf("\n图的各顶点的信息为:\n");

for(i=0;iL.num;i++)

printf("%c ",L.vexs[i]);

printf("\n图的边权矩阵的信息为:\n");

for(i=0;iL.num;i++)

{

for(j=0;jL.num;j++)

{

printf("%6.2f ",L.arcs[i][j]);

}

printf("\n");

}

printf("图已经输出完毕!");

}

/***********************5。图的深度周游**********************/

void DFS(GRAPH g,int qidian,int mark[])

//从第qidian个点出发深度优先周游图g中能访问的各个顶点

{

int v1;

mark[qidian]=1;

printf("%c ",g.vexs[qidian]);

for(v1=0;v1g.num;v1++)

{

if(g.arcs[qidian][v1]!=0mark[v1]==0)

DFS(g,v1,mark);

}

}

/***********************6。图的深度周游**********************/

void GraphDFS(GRAPH g)

//深度优先周游图g中能访问的各个顶点

{

int qidian,v,v1,mark[maxsize];

printf("\n深度周游:");

printf("\n请输入起点的下标:");

scanf("%d",qidian);

for(v=0;vg.num;v++)

{

mark[v]=0;

}

for(v=qidian;vg.num+qidian;v++)

{

//printf("v=%d ",v);

v1=v%g.num;

if(mark[v1]==0)

DFS(g,v1,mark);

}

}

typedef int DATATYPE; //队列元素的数据类型

typedef struct

{

DATATYPE data[maxsize]; //队中元素

int front,rear; //队头元素下标、队尾元素后面位置的下标

} SEQQUEUE;

/*****************************************************************************/

void QueueInit(SEQQUEUE *sq)

//将顺序循环队列sq置空(初始化)

{

sq-front=0;

sq-rear=0;

}

/*****************************************************************************/

int QueueIsEmpty(SEQQUEUE sq)

//如果顺序循环队列sq为空,成功返回1,否则返回0

{

if (sq.rear==sq.front)

return(1);

else

return(0);

}

/*****************************************************************************/

int QueueFront(SEQQUEUE sq,DATATYPE *e)

//将顺序循环队列sq的队头元素保存到e所指地址,成功返回1,失败返回0

{

if (QueueIsEmpty(sq))

{ printf("queue is empty!\n");return 0;}

else

{ *e=sq.data[(sq.front)]; return 1;}

}

/*****************************************************************************/

int QueueIn (SEQQUEUE *sq,DATATYPE x)

//将元素x入队列sq的队尾,成功返回1,失败返回0

{

if (sq-front==(sq-rear+1)%maxsize)

{

printf("queue is full!\n");

return 0;

}

else

{

sq-data[sq-rear]=x;

sq-rear=(sq-rear+1)%maxsize;

return(1);

}

}

/*****************************************************************************/

int QueueOut(SEQQUEUE *sq)

//将队列sq队首元素出队列,成功返回1,失败返回0

{

if (QueueIsEmpty(*sq))

{

printf("queue is empty!\n");

return 0;

}

else

{

sq-front=(sq-front+1)%maxsize;

return 1;

}

}

/***********************7。图的广度周游**********************/

void BFS(GRAPH g,int v,int mark[])

//从v出发广度优先周游图g中能访问的各个顶点

{

int v1,v2;

SEQQUEUE q;

QueueInit(q);

QueueIn(q,v);

mark[v]=1;

printf("%c ",g.vexs[v]);

while(QueueIsEmpty(q)==0)

{

QueueFront(q,v1);

QueueOut(q);

for(v2=0;v2g.num;v2++)

{

if(g.arcs[v1][v2]!=0mark[v2]==0)

{

QueueIn(q,v2);

mark[v2]=1;

printf("%c ",g.vexs[v2]);

}

}

}

}

/***********************8。图的广度周游**********************/

void GraphBFS(GRAPH g)

//深度优先周游图g中能访问的各个顶点

{

int qidian,v,v1,mark[maxsize];

printf("\n广度周游:");

printf("\n请输入起点的下标:");

scanf("%d",qidian);

for(v=0;vg.num;v++)

{

mark[v]=0;

}

for(v=qidian;vg.num+qidian;v++)

{

v1=v%g.num;

if(mark[v1]==0)

BFS(g,v1,mark);

}

}

/***********************主函数**********************/

void main()

{

GRAPH tu;

GraphCreate(tu);

GraphOut(tu);

GraphDFS(tu);

GraphBFS(tu);

}