图的深度/广度优先遍历C语言程序

Question

求一个深度或广度优先遍历的C语言程序,
图的深度遍历
任务：对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索遍历。
图的广度遍历
任务：图的广度遍历：对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。
能说明下你的程序么

Answer 1

这是我们老师给我们上数据结构课的课件

#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;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}
printf("请输入边权矩阵的信息：");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->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;i<L.num;i++)
printf("%c ",L.vexs[i]);
printf("\n图的边权矩阵的信息为：\n");
for(i=0;i<L.num;i++)
{
for(j=0;j<L.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;v1<g.num;v1++)
{
if(g.arcs[qidian][v1]!=0&&mark[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;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.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;v2<g.num;v2++)
{
if(g.arcs[v1][v2]!=0&&mark[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;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.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);
}

Answer 2

#define INFINITY 10000 //无穷大
#define MAX_VERTEX_NUM 40
#define MAX 40
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
typedef struct ArCell{
int adj;
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
char name[20];
}infotype;
typedef struct
{
infotype vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;

int LocateVex(MGraph *G,char* v)
{ int c=-1,i;

for(i=0;i<G->vexnum;i++)
if(strcmp(v,G->vexs[i].name)==0)
{c=i;break;}
return c;
}
MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入
{
int i,j,k,w;
char v1[20],v2[20];
printf("请输入图的顶点数和弧数:");
scanf("%d,%d",&G->vexnum,&G->arcnum);
printf("请依次输入图的顶点\n");
for(i=0;i<G->vexnum;i++){
printf("G.vexs[%d] : ",i);
scanf("%s",G->vexs[i].name);
getchar();
} // 构造顶点向量
for(i=0;i<G->vexnum;i++) //初始化邻接矩阵
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
printf("请输入一条边依附的两个顶点和权值:\n");
for(k=0;k<G->arcnum;k++) //构造邻接矩阵
{
printf("第%d条边:\n",k+1);
printf("起始结点:");
scanf("%s",v1);
printf("结束结点:");
scanf("%s",v2);
printf("边的权值:");
scanf("%d",&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2); // 确定v1和v2在G中位置
if(i>=0&&j>=0){
G->arcs[i][j].adj=w;
G->arcs[j][i]=G->arcs[i][j]; //置<v1,v2>的对称弧<v2,v1>
}
}
return G;
}

int FirstAdjVex(MGraph *G,int v)
{
int i;
if(v>=0 &&v<G->vexnum)
{ //v合理
for(i=0;i<G->vexnum;i++)
if(G->arcs[v][i].adj!=INFINITY)
{return i;break;}
}
return -1;
}

void VisitFunc(MGraph *G,int v)
{
printf("%s ",G->vexs[v].name);

}
int NextAdjVex(MGraph *G,int v,int w)
{
int k;
if(v>=0 && v<G->vexnum && w>=0 && w<G->vexnum) //v,w合理
{
for( k=w+1;k<G->vexnum;k++)
if(G->arcs[v][k].adj!=INFINITY)
{return k;break;}
}
return -1;
}
int visited[MAX];
void DFS(MGraph *G,int v)//从第v个顶点出发递归地深度优先遍历图G
{
int w;
visited[v]=1;
VisitFunc(G,v);//访问第v个结点
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
if(!visited[w]){
DFS(G,w);
}
}
void DFSTraverse(MGraph *G,char *s)//深度优先遍历
{int v,k;
for(v=0;v<G->vexnum;v++)
visited[v]=0;
k=LocateVex(G,s);
if(k>=0&&k<G->vexnum){
for(v=k;v>=0;v--){
if(!visited[v])
DFS(G,v);}
for(v=k+1;v<G->vexnum;v++)
if(!visited[v])
DFS(G,v);
}
}
typedef struct QNode {
int data;
struct QNode *next;
}QNode,*Queueptr;
typedef struct {
Queueptr front;
Queueptr rear;
}LinkQueue;
int InitQueue (LinkQueue &Q){
Q.front=Q.rear=(Queueptr)malloc(sizeof(QNode));
if(!Q.front)exit(-1);
Q.front->next=NULL;
return 1;
}
int EnQueue(LinkQueue &Q,int e){
Queueptr p;
p=(Queueptr)malloc(sizeof(QNode));
if(!p)exit(-1);
p->data=e; p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return 1;
}
int DeQueue (LinkQueue &Q,int &e){
Queueptr p;
if(Q.front==Q.rear)return(-1);
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return 1;
}
int QueueEmpty(LinkQueue Q)
{

if(Q.rear==Q.front)
return 1;
return 0;
}
int Visited[MAX];
void BFSTraverse(MGraph *G,char *str) { //广度优先遍历
int w,u,v,k;
LinkQueue Q;
for(v=0;v<G->vexnum;v++) Visited[v]=0;
InitQueue(Q);
k=LocateVex(G,str);
for(v=k;v>=0;v--)
//for(v=0;v<G->vexnum;++v)
{
if(!Visited[v])
{
Visited[v]=1;
VisitFunc(G,v);
EnQueue(Q,v); //v入队
while(!QueueEmpty(Q))
{
DeQueue(Q,u); //出队
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
if(!Visited[w])
{
Visited[w]=1;
VisitFunc(G,w);
EnQueue(Q,w);
}
} //while
}
}

for(v=k+1;v<G->vexnum;v++)
if(!Visited[v])
{
Visited[v]=1;
VisitFunc(G,v);
EnQueue(Q,v);//v入队
while(!QueueEmpty(Q))
{
DeQueue(Q,u);//出队
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
if(!Visited[w])
{
Visited[w]=1;
VisitFunc(G,w);
EnQueue(Q,w);
}
}
}
}

void main()
{
MGraph *G,b;

char v[10];
G=CreatUDN(&b);
printf("请输入开始遍历的起始结点名称:");
scanf("%s",v);
printf("\n深度优先遍历(输出结点序列）:\n");
DFSTraverse(G,v);
printf("\n广度优先遍历(输出结点序列）:\n");
BFSTraverse(G,v);

}
这个程序我刚写好，可以运行出结果的，你先运行一下试试.