实验项目名称： 图的遍历
一、实验目的
应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。
二、实验内容
问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。
三、实验仪器与设备
计算机，Code::Blocks。
四、实验原理
用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。
五、实验程序及结果
#define INFINITY 10000 /*无穷大*/
#define MAX_VERTEX_NUM 40
#define MAX 40
#include<stdlib.h>
#include<stdio.h>
#include<conio.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("No.%d:",i+1);
scanf("%s",G->vexs[i].name);}
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);
if(i>=0&&j>=0){
//G->arcs[i][j].adj=w;
G->arcs[j][i]=G->arcs[i][j];
}}
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;
}
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;
}
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);
printf("%d ",G->arcs[v][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 vexnum;
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(0);
Q->front->next=NULL;
return 1;
}
void EnQueue(LinkQueue *Q,int a )
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)exit(0);
p->vexnum=a;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
int DeQueue(LinkQueue *Q,int *v)
{ QueuePtr p;
if(Q->front==Q->rear)
{printf("结点不存在!\n");exit(0);}
p=Q->front->next;
*v=p->vexnum;
Q->front->next=p->next;
if(Q->rear==p)
Q->front=Q->rear;
return *v;
}
int QueueEmpty(LinkQueue *Q)
{
if(Q->rear==Q->front)
return 0;
return 1;
}
int Visited[MAX];
void BFSTraverse(MGraph *G,char *str)//广度优先遍历
{int w,u,v,k;
LinkQueue Q,q;
for(v=0;v<G->vexnum;v++) Visited[v]=0;
InitQueue(&Q);InitQueue(&q);
k=LocateVex(G,str);
for(v=k;v>=0;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,v);
EnQueue(&Q,w);
}
}
}
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,v);
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);
getch();
}
六、实验总结
实验要求输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。在设计中其中用邻接表表示的节点的值只能是数字，但用邻接矩阵表示的节点的值可以是字母。但用邻接表形式要相对简单一些。
深度优先采取的递归思想。首先，将从起点，沿某条边，顺势遍历下去，直到不能继续遍历下去。这时，又从起点的另一结点开始，遍历下去。如此往复，知道将所有结点遍历完。
广度优先得使用队列。首先，将起点入队，并标为已访问。进入循环，当队列不为空时，出队，输出，并将与出队的元素相邻的且未访问的结点全部放入队列，标为已访问。一次循环，只有一个结点出队，大于等于0个结点入队。
实验程序中大量使用了循环，使时间复杂度加大了很多，因此此程序比较适合于密集图，应用于稀疏图中就有点浪费时间了。
第二篇：数据结构 图的四种遍历
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/****图的存储结构定义及实现 *************/
#define MaxVerNum 30 /* 最大顶点个数 */
#define Vextype char
#define InfoType int
#define Edgetype int
#define INFINITE 999
#define MAXSIZE 100
typedef struct
{
Vextype vexs[MaxVerNum]; /* 顶点表 */
Edgetype edges[MaxVerNum][MaxVerNum]; /* 邻接矩阵,即边表 */
int n,e; /*顶点数和边数*/
}MGragh; /*MGragh是以邻接矩阵存储的图类型*/
typedef struct node
{ /* 表结点 */
int adjvex; /* 邻接点域,一般是放顶点对应的序号或在表头向量中的下标 */
InfoType Info; /*与边(或弧)相关的信息*/
struct node * next; /* 指向下一个邻接点的指针域 */
}EdgeNode;
typedef struct vnode
{ /* 顶点结点 */
Vextype vertex; /* 顶点域 */
EdgeNode* firstedge; /* 边表头指针 */
}VertexNode;
typedef struct
{
VertexNode adjlist[MaxVerNum]; /* 邻接表 */
int n,e; /* 顶点数和边数 */
}ALGraph; /* ALGraph是以邻接表方式存储的图类型 */
void CreatGraph(MGragh *G) /*建立图G的邻接矩阵 */
{
int i,j,k,w;
} char ch; printf("输入图的顶点数和边数,如m,n...\n"); scanf("%d,%d",&(G->n),&(G->e));/* 输入顶点数和边数 */ printf("请逐个输入图的顶点：\n"); for (i=0;i<G->n;i++) { // } for (i=0;i<G->n;i++) { for (j=0;j<G->n;j++) { if(i==j) G->edges[i][j]=0; //对角线元素为0 } else G->edges[i][j]=INFINITE; //其它元素元素为无穷大 //G->edges[i][j]=0; /* 初始化邻接矩阵 */ scanf("%c",&ch); while(ch=='\n') //处理读取回车符的异常情况 scanf("%c",&ch); G->vexs[i]=ch; scanf("%c",&(G->vexs[i])); /* 输入顶点信息,建立顶点表 */ } printf("请逐个输入图的边：如i,j:w...(索引下标从0开始)\n"); for (k=0;k<G->e;k++) { scanf("%d,%d:%d",&i,&j,&w); /* 输入e条边,建立邻接矩阵 */ // // } G->edges[i][j]=w; scanf("%d,%d",&i,&j); /* 输入e条边,建立邻接矩阵 */ G->edges[i][j]=1; /* 若加入G->edges[j][i]=1,则为无向图的邻接矩阵*/
//打印图
void printGragp(MGragh *G) {
printf("顶点如下：\n"); for(int i=0;i<G->n;i++) {
} printf("%c\t",G->vexs[i]); } printf("\n邻接矩阵如下：\n"); for(int i=0;i<G->n;i++) { } for(int j=0;j<G->n;j++) { } printf("%d\t",G->edges[i][j]); printf("\n");
/* 根据图的邻接矩阵存储建立图的邻接表存储 */ void CreateALGraph(MGragh *G,ALGraph *alG) {
alG->n=G->n;
alG->e=G->e;
}
void printALGragp(ALGraph *alG)
{
printf("邻接表如下:\n"); for(int i=0;i<alG->n;i++) for(int i=0;i<alG->n;i++) { } alG->adjlist[i].vertex=G->vexs[i]; alG->adjlist[i].firstedge=NULL; EdgeNode* p; for(int j=0;j<G->n;j++) { } if(G->edges[i][j]!=0&&G->edges[i][j]!=INFINITE) { p=(EdgeNode*)malloc(sizeof(EdgeNode)); } p->adjvex=j; p->Info=G->edges[i][j]; p->next=alG->adjlist[i].firstedge; alG->adjlist[i].firstedge=p;
} { } printf("%c:",alG->adjlist[i].vertex); EdgeNode* edge=alG->adjlist[i].firstedge; while(edge) { } printf("%\n"); printf("-->"); printf("%d:%d\t",edge->adjvex,edge->Info); edge=edge->next;
/************************栈的定义与算法*********************************/
typedef struct
{
int data[MAXSIZE];
int top;
}SeqStack, *PSeqStack;
PSeqStack Init_SeqStack(void)
{ /*创建一顺序栈，入口参数无，返回一个指向顺
序栈的指针，为零表示分配空间失败*/
PSeqStack S;
S=(PSeqStack)malloc(sizeof(SeqStack));
if (S)
S->top= -1;
return S;
}
void Destroy_SeqStack (PSeqStack * SeqStackPoint)
{/*销毁顺序栈，入口参数：为要销毁的顺序栈指针地址*/
if (*SeqStackPoint)
free (*SeqStackPoint) ;
* SeqStackPoint =NULL;
return ;
}
int Empty_SeqStack(PSeqStack S)
{/*判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空*/
if (S->top== -1)
return 1;
else
return 0;
}
int Push_SeqStack (PSeqStack S, int x)
{ /*入口参数：顺序栈，返回值：1表示入栈成功，0 表示失败。*/
if (S->top==MAXSIZE-1)
return 0; /*栈满不能入栈*/
else { } S->top++; S->data[S->top]=x; return 1;
}
int Out_SeqStack(PSeqStack S, int *x)
{/*取出栈顶元素， 入口参数：顺序栈，被取出的元素指针，这里用
指针带出栈顶值返回值：1表示成功，0表示失败。*/
if ( Empty_SeqStack ( S ) ) return 0; /*栈空*/ else { *x= S->data[S->top--]; /*栈顶元素存入*x中*/ return (1);
}
}
int GetStackTop( PSeqStack stack )
{
return stack->top;
}
/************************队列的定义与算法*********************************/ typedef struct
{
int data[MAXSIZE]; /*队列的存储空间*/
int front, rear; /*队头队尾指针*/
}SeqQueue,*PSeqQueue;
PSeqQueue Init_SeqQueue( )
{ /*返回值：新顺序队列指针，null表示失败*/ PSeqQueue Q;
Q=( PSeqQueue )malloc(sizeof(SeqQueue));
if (Q) {
Q->front=0;
Q->rear=0;
}
return Q;
}
void Destroy_SeqQueue(PSeqQueue *Q)
{
if (*Q)
free(*Q);
*Q=NULL;
}
int Empty_SeqQueue(PSeqQueue Q)
/*返回值：1表示为空，0表示非空*/
{ if (Q && Q->front==Q->rear)
return (1);
else
return (0);
}
int In_SeqQueue ( PSeqQueue Q , int x)
{ /*返回值：1表示成功，－1表示队满溢出*/ if ((Q->rear+1)%MAXSIZE==Q->front) {
printf("队满");
return -1; /*队满不能入队*/
}
else
{ Q->rear=(Q->rear+1) % MAXSIZE; Q->data[Q->rear]=x;
return 1; /*入队完成*/
}
}
int Out_SeqQueue(PSeqQueue Q,int *x)
{ /*返回值：1表示成功，－1表示队空,出队的元素保存到*x if (Empty_SeqQueue(Q))
{
printf("队空"); */
return -1; /*队空不能出队*/ }
else
{
Q->front=(Q->front+1) % MAXSIZE; *x=Q->data[Q->front];
return 1; /*出队完成*/
}
}
int Front_SeqQueue(PSeqQueue Q,int *x)
{ /*返回值：1表示成功，－1表示队空*/
if (Q->front==Q->rear) { printf("队空"); return -1; /*队空不能得到队头元素*/ } else { *x=Q->data[(Q->front+1)%MAXSIZE]; return 1; /*取队头元素操作完成*/ }
}
/****图的遍历*************/
int visited[MaxVerNum];
//深度 邻接矩阵
void DFS(MGragh g,int v)
{
printf("%c ",g.vexs[v]); visited[v]=1; for(int i=0;i<g.n;i++) { } if(g.edges[v][i]!=0&&g.edges[v][i]!=INFINITE) { } if(!visited[i]) DFS(g,i);
}
void DFSTranverseForMG(MGragh g) {
} printf("\n邻接矩阵的深度遍历结果：\n"); for(int i=0;i<g.n;i++) visited[i]=0; for(int j=0;j<g.n;j++) { } if(!visited[j]) DFS(g,j);
//广度 邻接矩阵
void BFS(MGragh g,int v) {
}
void BFSTranverseForMG(MGragh g) {
printf("\n邻接矩阵的广度遍历结果：\n"); PSeqQueue Q; Q=Init_SeqQueue(); printf("%c ",g.vexs[v]); visited[v]=1; In_SeqQueue(Q,v); int i; while(!Empty_SeqQueue(Q)) { Out_SeqQueue(Q,&i); } for(int j=0;j<g.n;j++) { } if(g.edges[i][j]!=0&&g.edges[i][j]!=INFINITE) { if(!visited[j]) } { } printf("%c visited[j]=1; In_SeqQueue(Q,j); ",g.vexs[j]);
} for(int i=0;i<g.n;i++) visited[i]=0; for(int j=0;j<g.n;j++) { } if(!visited[j]) BFS(g,j);
//深度 邻接表
void DFS2(ALGraph g,int v)
{
} EdgeNode* p; int w; printf("%c ",g.adjlist[v].vertex); visited[v]=1; for(p=g.adjlist[v].firstedge;p;p=p->next) { } w=p->adjvex; if(!visited[w]) DFS2(g,w);
void DFSTranverseForALG(ALGraph g) {
printf("\n邻接表的深度遍历结果：\n");
} for(int i=0;i<g.n;i++) visited[i]=0; for(int j=0;j<g.n;j++) { } if(!visited[j]) DFS2(g,j);
//广度 邻接表
void BFS2(ALGraph g,int v)
{
}
EdgeNode* p; PSeqQueue Q; Q=Init_SeqQueue(); printf("%c ",g.adjlist[v].vertex); visited[v]=1; In_SeqQueue(Q,v); int i,w; while(!Empty_SeqQueue(Q)) { } Out_SeqQueue(Q,&i); for(p=g.adjlist[i].firstedge;p;p=p->next) { } w=p->adjvex; if(!visited[w]) { } printf("%c ",g.adjlist[w].vertex); visited[w]=1; In_SeqQueue(Q,w);
void BFSTranverseForALG(ALGraph g) {
printf("\n邻接表的广度遍历结果：\n");
}
/****main函数*************/
int main()
{
MGragh mG; for(int i=0;i<g.n;i++) visited[i]=0; for(int j=0;j<g.n;j++) { if(!visited[j]) BFS2(g,j); }
} CreatGraph(&mG); //打印邻接矩阵信息 //printf("图G的邻接矩阵如下:"); printGragp(&mG); ALGraph alG; CreateALGraph(&mG,&alG); //打印邻接表信息 //printf("图G的邻接表如下:"); printALGragp(&alG); //图的遍历 DFSTranverseForMG(mG); BFSTranverseForMG(mG); DFSTranverseForALG(alG); BFSTranverseForALG(alG); getchar();