实验四

---

一、实验题目：

图的存储和遍历

二、实验目的：

⑴ 掌握图的逻辑结构；
⑵ 掌握图的邻接矩阵存储结构和图的邻接表存储结构；
⑶ 验证图的邻接矩阵存储和邻接表的存储以及深度优先遍历和广度优先遍历操作的实现。

三、实验内容：

（1）建立无向图的邻接矩阵存储；
（2）对建立的无向图，进行深度优先遍历和广度优先遍历；
（3）建立有向图的邻接表存储；
（4）对建立的有向图，进行深度优先遍历和广度优先遍历。

1.建立无向图的邻接矩阵存储结构，进行深度优先遍历和广度优先遍历。

程序代码：

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10

int visited1[MaxSize]={0};
int visited2[MaxSize]={0};
typedef char DataType;
typedef struct
{
	DataType vertex[MaxSize];
	int edge[MaxSize][MaxSize];
	int vertexNum,edgeNum;
}MGraph;
void CreatGraph(MGraph *G,DataType a[],int n,int e);
void DFTravere(MGraph *G,int v);
void BFTraverse(MGraph *G,int v);

void CreatGraph(MGraph *G,DataType a[],int n,int e)
{
	int i,j,k;
	G->vertexNum=n;
	G->edgeNum=e;
	for(i=0;i<G->vertexNum;i++){
		G->vertex[i]=a[i];
	}
	for(i=0;i<G->vertexNum;i++){
		for(j=0;j<G->vertexNum;j++)
		  G->edge[i][j]=0;
	}
	for(k=0;k<G->edgeNum;k++){
	   scanf("%d %d",&i,&j);
		G->edge[i][j]=1;
		G->edge[j][i]=1;
	}
}

void DFTraverse(MGraph *G,int v)
{
	int j;
	printf("%c",G->vertex[v]);
	visited1[v]=1;
	for(j=0;j<G->vertexNum;j++)
	  if(G->edge[v][j]==1&&visited1[j]==0)
	    DFTraverse(G,j);
}

void BFTraverse(MGraph *G,int v)
{
	int i,j,Q[MaxSize];
	int front,rear;
	front=-1,rear=-1;
	printf("%c",G->vertex[v]);
	visited2[v]=1;
    Q[++rear]=v;
	while(front!=rear){
		v=Q[++front];
		for(j=0;j<G->vertexNum;j++){
			if(G->edge[v][j]==1&&visited2[j]==0)
			{
				printf("%c",G->vertex[j]);
				visited2[j]=1;
				Q[++rear]=j;
			}
		}
	}
}

int main()
{
	char ch[]={'A','B','C','D','E'}; 
	MGraph MG;
	CreatGraph(&MG,ch,5,6);
	 printf("深度优先遍历序列是：");
	 DFTraverse(&MG,0);
	 printf("\n广度优先遍历序列是：");
	 BFTraverse(&MG,0);
	return 0;
}

程序运行结果截图：

2.建立有向图的邻接表存储结构，进行深度优先遍历和广度优先遍历。

程序代码：

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
int visited1[MaxSize]={0};
int visited2[MaxSize]={0};
typedef char DataType;
typedef struct EdgeNode
{
	int adjvex;
	struct EdgeNode *next;
}EdgeNode;

typedef struct
{
	DataType vertex;
	EdgeNode *first;
}VertexNode;

typedef struct
{
	VertexNode adjlist[MaxSize];
	int vertexNum,edgeNum;
}ALGraph;

void CreateGraph(ALGraph *G,DataType a[],int n,int e){
	int i,j,k;
	EdgeNode *s=NULL;
	G->vertexNum=n;
	G->edgeNum=e;
	for(i=0;i<G->vertexNum;i++){
		G->adjlist[i].vertex=a[i];
		G->adjlist[i].first=NULL;
	}
	for(k=0;k<G->edgeNum;k++){
		scanf("%d %d",&i,&j);
		s=(EdgeNode*)malloc(sizeof(EdgeNode));
		s->adjvex=j;
		s->next=G->adjlist[i].first;
		G->adjlist[i].first=s;
	}
}
void DFTraverse(ALGraph *G,int v){
	EdgeNode *p=NULL;
	int j;
	printf("%c",G->adjlist[v].vertex);
	visited2[v]=1;
	p=G->adjlist[v].first;
	while(p!=NULL){
		j=p->adjvex;
		if(visited2[j]==0) DFTraverse(G,j);
		p=p->next;
	}
}
void BFTraverse(ALGraph *G,int v){
EdgeNode *p=NULL;
	int Q[MaxSize],front=-1,rear=-1,j;
	printf("%c",G->adjlist[v].vertex);
	visited1[v]=1;
	Q[++rear]=v;
	while(front!=rear){
		v=Q[++front];
		p=G->adjlist[v].first;
		while(p!=NULL){
			j=p->adjvex;
	    	if(visited1[j]==0)
			{
				printf("%c",G->adjlist[j].vertex);
				visited1[j]=1;
				Q[++rear]=j;
			}
			p=p->next;
		}
	}
}
int main(){
	char ch[]={'A','B','C','D','E'};
	ALGraph ALG;
	CreateGraph(&ALG,ch,5,6);
	  printf("广度优先遍历序列是：");
	BFTraverse(&ALG,0);
	 printf("\n深度优先遍历序列是：");
	DFTraverse(&ALG,0);
	return 0;
	}

程序运行结果截图：

四、实验心得体会

通过本次实验我掌握了图的逻辑结构；掌握了图的邻接矩阵存储结构和图的邻接表存储结构；验证了图的邻接矩阵存储和邻接表的存储以及深度优先遍历和广度优先遍历操作的实现，在这个过程中我的程序技能更加完善。