实验目的
    1. 深入了解图的逻辑结构特性及其基本操作
    2. 了解图的各种存储结构的特点与适用范围，熟练掌握在邻接矩阵和邻接表存储结构上深度优先和广度优先搜索算法的实现
    3. 掌握图的应用，如求解图的连通性问题，最小生成树，拓扑排序，关键路径和最短路径算法及其灵活应用
实验预习
    1. 深入了解图的邻接矩阵表示法与图的邻接矩阵表示法
    2. 在实验预习报告上设计，编写实验内容的源程序，给程序加上适当的注释，设计运行程序所需的测试数据
实验内容

1. 设计并验证如下算法：图采用邻接矩阵表示，实现无向图的深度优先搜索与有向图的广度优先搜索。

实验代码：

#include <stdio.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define INT_MAX
#define MAX_VERTEX_NUM 20
typedef int ElemType;
typedef int AdjMatrix;
typedef int Status;
int book[MAX_VERTEX_NUM]={0};
typedef struct{
	ElemType  vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int vexnum,arcnum;
}Gragh;
typedef ElemType QElemType;
typedef struct queue{
        QElemType *base;
        int front; //指示队头位置
        int rear;  //指示队尾位置
}SqQueue;

void initQueue(SqQueue *q){
	q->base = (QElemType*)malloc(100*sizeof(QElemType));
	q->front=q->rear=0;
}

void enQueue(SqQueue *q,QElemType e){
		q->base[q->rear]=e;
		if(q->rear+1==100){
			q->rear=0;
		}else
			q->rear++;
}

void deQueue(SqQueue *q,QElemType *e){
		*e=q->base[q->front];
		if(q->front+1==100){
			q->front=0;
		}else
			q->front++;
}

void initGragh(Gragh *g){
	g->vexnum=0;
	g->arcnum=0; 
	for(int i=0;i<MAX_VERTEX_NUM;i++){
		g->vexs[i]=0;
		for(int j=0;j<MAX_VERTEX_NUM;j++){
			g->arcs[i][j]=0;
		}
	}
}
int local(Gragh g,int n){//值为n的点在定点向量中的下标 
	for(int i=1;i<=g.vexnum;i++){
		if(g.vexs[i]==n||g.vexs[i]==0)
			return i;
		else if(i==g.vexnum-1){
			return g.vexnum;
		}
	}
}
void set(Gragh *g,int a){//赋值 
	for(int i=1;i<=g->vexnum;i++){
		if(g->vexs[i]==0||g->vexs[i]==a){
			g->vexs[i]=a;
			return;
		}	
	}
}
void createGragh(Gragh *g){
	printf("请分别输入图的顶点个数，边数：\n");
	int n,m,a,b;
	scanf("%d %d",&n,&m);

	g->vexnum=n;
	g->arcnum=m;
	for(int i=1;i<=m;i++){
		scanf("%d %d",&a,&b);
		set(g,a);
		set(g,b);
		g->arcs[local(*g,a)][local(*g,b)]=1;//无向图 
		g->arcs[local(*g,b)][local(*g,a)]=1;
	}
} 
void print(Gragh g){//打印图 
	printf("\n----------------------\n");
	printf("顶点数： %d\n",g.vexnum);
	printf("边数： %d\n",g.arcnum);
	printf("邻接矩阵：\n   "); 
	for(int j=1;j<=g.vexnum;j++){
			printf("%d ",g.vexs[j]);
	}
	printf("\n   ");
	for(int j=1;j<=g.vexnum;j++){
			printf("* ");
			
	}
	printf("\n");
	for(int i=1;i<=g.vexnum;i++){
			printf("%d *",g.vexs[i]);
		for(int j=1;j<=g.vexnum;j++){
			printf("%d ",g.arcs[i][j]);
		}
		printf("\n");
	}
	printf("----------------------\n");
}
/*深度优先遍历*/ 
void dfs(Gragh g,int n,int a){
	int m=local(g,a);
	printf("%d ",g.vexs[m]);
	book[m]=1;
	if(n==g.vexnum+1) return;
	for(int i=1;i<=g.vexnum;i++){
		if(book[i]==0&&g.arcs[m][i]==1){
			book[i]=1;
			dfs(g,++n,g.vexs[i]);
		}
	}
}
/*广度优先遍历*/ 
void bfs(Gragh g,int a){
	SqQueue Q;
	int n,book[100]={0};
	initQueue(&Q);
	enQueue(&Q,local(g,a));
	book[local(g,a)]=1;
	while(Q.front!=Q.rear){
		deQueue(&Q,&n);
		printf("%d ",g.vexs[n]);
		for(int i=1;i<=g.vexnum;i++){
			if(g.arcs[n][i]==1&&book[i]==0){
				book[i]=1;
				enQueue(&Q,i);
			}
		}
	}
}

int main(){
	Gragh g;
	initGragh(&g);
	createGragh(&g);
	printf("\n----------------------\n深度优先遍历：\n");
	dfs(g,1,1);// g：图 1：第一步  1：从顶点值为1的地方开始遍历 
	printf("\n----------------------\n广度优先遍历：\n"); 
	bfs(g,1);// g:图   1:从定点值为1的地方开始遍历 
	print(g);
	return 0;
}
/*
样例输入： 
8 9
4 9
1 2
3 6
1 3
2 7
6 7
1 5
5 6
2 4
*/

运行结果：