假设无向图采用邻接表结构表示。编程分别实现图的深度优先搜索算法和广度优先搜索算法。
假设无向图采用邻接表结构表示。编程分别实现图的深度优先搜索算法和广度优先搜索算法。
以下是我的程序，可是在输入中就出现了错误，顶点和弧的输入都有问题，顶点输入少一，弧的输入无法终止，请高手指点下。
#define Max 30
#define N 5
#include <stdlib.h>
typedef struct ArcNode
{int nextv;
struct ArcNode *nextarc;
}ArcNode;
typedef struct Vnode
{char data;
ArcNode *arc;
}Vnode;
typedef struct
{Vnode v[N];
int vnum,arcnum;
}Graph;
int Tag[N],queue[N],f,r;
Graph creat(Graph T)
{int i,j,k,flag[N];
char m,n;
ArcNode *stack[N],*p;
printf("Please input the number of vex:");
scanf("%d",&T.vnum);
printf("Please input the nuber of arc:");
scanf("%d",&T.arcnum);
printf("Please input the vex:\n");
for (i=0;i<T.vnum;i++)
{scanf("%c",&T.v[i].data);flag[i]=0;}
for (i=0;i<T.vnum;i++)
printf(" %c ",T.v[i].data);
printf("Please input the arc(a->b):\n");
for (i=0;i<T.arcnum;i++)
{scanf ("%c->%c",&m,&n);
for (i=0;i<T.vnum;i++)
{if(T.v[i].data==m) j=i;
if(T.v[i].data==n) k=i;
}
if (flag[j]==0)
{T.v[j].arc=(ArcNode *)malloc(sizeof(ArcNode));
T.v[j].arc->nextv=k; flag[j]=1;
T.v[j].arc->nextarc=NULL;
stack[j]=T.v[j].arc;
}
else {p=stack[j];
p->nextarc=(ArcNode *)malloc(sizeof(ArcNode));
p->nextv=k;
p->nextarc->nextarc=NULL;
stack[j]=p->nextarc;
}
if (flag[k]==0)
{T.v[k].arc=(ArcNode *)malloc(sizeof(ArcNode));
T.v[k].arc->nextv=j; flag[k]=1;
T.v[k].arc->nextarc=NULL;
stack[k]=T.v[k].arc;
}
else {p=stack[k];
p->nextarc=(ArcNode *)malloc(sizeof(ArcNode));
p->nextv=j;
p->nextarc->nextarc=NULL;
stack[k]=p->nextarc;
}
}
}
void DFStwo(Graph T,int n)
{ArcNode *p;int m;
Tag[n]=1; printf("%c",T.v[n].data);
p=T.v[n].arc;
while (p!=NULL)
{m=p->nextv;
if(Tag[m]==0) DFStwo(T,m);
p=p->nextarc;
}
}
void DFSone(Graph T,char v)
{int i,m;
for (i=0;i<T.vnum;i++)
{if (T.v[i].data==v) m=i;
Tag[i]=0;
}
DFStwo(T,m);
for (i=0;i<T.vnum;i++)
if(Tag[i]==0) DFStwo(T,i);
}
void BFStwo(Graph T,int n)
{ArcNode *p;int m;
Tag[n]=1;printf("%c",T.v[n].data);
p=T.v[n].arc;
while (p!=NULL)
{m=p->nextv;
if (Tag[m]==0) {printf("%c",T.v[m].data);
Tag[m]=1;queue[r++]=m;
}
p=p->nextarc;
}
while (f!=r)
{m=queue[f++];
BFStwo(T,m);
}
}
void BFSone(Graph T,char v)
{int i,m;
for (i=0;i<T.vnum;i++)
{if (T.v[i].data==v) m=i;
Tag[i]=0;
}
BFStwo(T,m);
for (i=0;i<T.vnum;i++)
if(Tag[i]==0) BFStwo(T,i);
}
main()
{Graph T;
char v;
T=creat(T);
printf("Please input the point you want to begin to search:");
scanf("%c",&v);
printf("\n");
DFSone(T,v);
printf("Please input the point you want to begin to search:");
scanf("%c",&v);
printf("\n");
BFSone(T,v);
getch();
}
[解决办法]
转：邻接表表示的图的深度优先搜索和广度优先搜索程序#include <stdio.h>#define maxvertexnum 100#define queuesize 100#define null 0typedef struct{ int front,rear,count,data[queuesize]; }cirqueue;//循环队列结构定义typedef int vertextype;//为了简单，设图中结点的数据为整型typedef struct node{ int adjvex;//存放邻接点序号 struct node *next;//指向下一个边结点 }edgenode;//图的邻接表的边结点定义typedef struct vnode{ vertextype vertex;//顶点数据域 edgenode *firstedge;//指向第一个边结点 }vertexnode;//图的邻接表表示的顶点结点定义typedef vertexnode adjlist[maxvertexnum];//用向量定义图的邻接表表示的顶点表typedef struct{ adjlist adjlist; int n;//图的顶点数 int e;//图的边数 }algraph;//定义图的邻接表typedef enum{FALSE,TRUE}boolean;boolean visited[maxvertexnum];//保存访问信息的布尔向量main()//主函数 {//建立图g，并进行深度优先搜索和广度优先搜索 algraph *g; g=(algraph*)malloc(sizeof(algraph));//申请图g的邻接表空间 createalgraph(g);//建立图g的邻接表表示 printf("the dfs is:");/ dfstraverse(g);//对图g进行深度优先搜索，并打印搜索序列 printf("the bfs is:"); bfstraverse(g);//对图g进行广度优先搜索，并打印搜索序列 }createalgraph(algraph *g) {//建立图g的邻接表表示 int i,j,k; int flag; edgenode *s; printf("\ncreat:\n")//选择建立有向图或无向图 printf("digraph--0\n"); printf("undigraph--1\n"); scanf("%d",&flag); printf("input n,e\n"); scanf("%d%d",&g->n,&g->e);//输入图g的顶点数和边数 printf("input nodes:\n"); for(i=0;i<g->n;i++){//构造一个只含n个顶点，边数为0的图 scanf("%d",&(g->adjlist[i].vertex)); //输入顶点的数据域（为了简单起见，输入为整数） g->adjlist[i].firstedge=null;//将顶点结点的firstedge域置为空 }//end for for(k=0;k<g->e;k++){ printf("input i,j(0~n-1):\n"); scanf("%d%d",&i,&j);//输入对应于一条边的顶点序号序偶对，要求顶点序号为0~n-1 s=(edgenode *)malloc(sizeof(edgenode));//申请一个边结点*s s->adjvex=j;//将序号j放入边结点*s的adjvex域 s->next=g->adjlist[i].firstedge; //将边结点*s作为第一个邻接点插入到序号为i的顶点的边表中 g->adjlist[i].firstedge=s; if (flag){//若要建立无向图 s=(edgenode *)malloc(sizeof(edgenode));申请一个边结点*s s->adjvex=i;//将序号i放入边结点*s的adjvex域 s->next=g->adjlist[j].firstedge; //将边结点*s作为第一个邻接点插入到序号为j的顶点的边表中 g->adjlist[j].firstedge=s; }//end of if }//end of for }//end of creatalgraphdfs(algraph *g,int i) {//对图g进行以序号为i的顶点作为出发点深度优先搜索 edgenode *p; printf("visit vertex:%d",g->adjlist[i].vertex);//打印序号为i的顶点信息 visited[i]=TRUE;//将序号为i的顶点设置已访问过标记 p=g->adjlist[i].firstedge;//设置寻找序号为i的第一个未访问过邻接点的扫描指针 while(p){ if (!visited[p->adjvex])//若*p边结点对应顶点（假设序号为j）未访问过 dfs(g,p->adjvex);//对图g进行以序号为j的顶点作为出发点进行深度优先搜索 p=p->next;//p顺着边表next指针，往后继续寻找 }//end of while }//end of dfsdfstraverse(algraph *g) {//对以邻接表表示的图g进行深度优先搜索 int i; for(i=0;i<g->n;i++)//将图g的所有顶点设置未访问过标记 visited[i]=FALSE; for(i=0;i<g->n;i++)//对图g调用dfs函数进行深度优先搜索 if(!visited[i]) dfs(g,i); printf("\n"); }//end of dfstraversebfs(algraph *g,int k) {//对图g进行以序号为k的顶点作为出发点广度优先搜索 int i,j; cirqueue *q;//设置循环队列指针 edgenode *p; q=(cirqueue *)malloc(sizeof(cirqueue));//申请循环队列空间 q->rear=q->front=q->count=0;//将循环队列置为空队 printf("visit vertex:%d",g->adjlist[k].vertex); visited[k]=TRUE;//将序号为k的顶点设置为已访问过 q->data[q->rear]=k;q->rear=(q->rear+1)%queuesize;q->count++;//将顶点序号k入队 while(q->count){//当队列非空时做以下操作 i=q->data[q->front];q->front=(q->front+1)%queuesize;q->count--;//将队首元素i出队 p=g->adjlist[i].firstedge;//设置寻找序号为i顶点的未访问过邻接点的扫描指针p while (p){//当*p不为空时，做以下操作 if(!visited[p->adjvex]){//若*p边结点对应顶点（假设序号为j）未访问过 printf("visit vertex:%d",g->adjlist[p->adjvex].vertex); //访问序号为j的顶点 visited[p->adjvex]=TRUE;//设置已访问过标记 q->data[q->rear]=p->adjvex;q->rear=(q->rear+1)%queuesize;q->count++; //将序号为j的顶点入队 }//end of if p=p->next;//p顺着边表next指针，往后继续寻找 }//end of while }//end of while }//end of bfsbfstraverse(algraph *g) {//对以邻接表表示的图g进行广度优先搜索 int i; for(i=0;i<g->n;i++)//将图g的所有顶点设置未访问过标记 visited[i]=FALSE; for(i=0;i<g->n;i++)//对图g调用bfs函数进行广度优先搜索 if(!visited[i]) bfs(g,i); printf("\n"); }