实验名称 图的应用

实验内容

基本内容：

算法1：输入图的类型、顶点数、狐（边）数、顶点信息、狐（边）信息，建立相应的图(具体类型可以是无向图、有向图、无向网、有向网，采用邻接矩阵存储结构)；分别按深度优先搜索和广度优先搜索遍历图；按某种形式输出图及遍历结果。

此处画出你计划遍历的图及所采用的存储结构

   

实验代码

#include 
#include 
#define FLASE 0
#define ERROR 0
#define OK 1
#define OVERFLOW -1
#define MAX_VEX_NUM 20
#define INFINITY 10000
#define TURE 1
#define FALSE 0
typedef int Boole; //布尔类型存储TURE FLASE 
Boole visited[MAX_VEX_NUM];   //访问标志数组 
typedef struct
{
	char vertex[MAX_VEX_NUM];  //顶点信息
	int arcs[MAX_VEX_NUM][MAX_VEX_NUM];   //边信息
	int vex_num, arc_num;
}Mgraph;
//队的链式存储结构 
typedef struct QNode
{
	int data;
	struct QNode* next;
}QNode, * Queueptr;
typedef struct {
	Queueptr front;  //队头指针
	Queueptr rear;  //队尾指针 
}LinkQueue;
//定位函数
int LocateVex(Mgraph g, int v)
{
	int i;
	for (i = 0; i < g.vex_num; i++)
	{
		if (g.vertex[i] == v)
			return i;
	}
	return -1;
}
void create_UDG(Mgraph& g)
{
	int i, j, k;
	char v1, v2;
	int cost;
	printf("请输入顶点个数，边的个数:n");
	scanf("%d,%d", &g.vex_num, &g.arc_num);
	getchar();
	printf("请输入顶点信息:n");
	//构造顶点向量
	for (i = 0; i < g.vex_num; i++)
	{
		scanf("%c", &g.vertex[i]);
		getchar();
	}
	//初始化邻接矩阵
	for (i = 0; i < g.vex_num; ++i)
		for (j = 0; j < g.vex_num; ++j)
			g.arcs[i][j] = INFINITY;
	printf("请输入边的信息:n");
	//构造邻接矩阵
	for (k = 0; k < g.arc_num; ++k)
	{
		//输入一条边依附的顶点
		scanf("%c,%c,%d", &v1, &v2, &cost);
		getchar();       //吃点垃圾字符
		//确定v1和v2在G中位置
		i = LocateVex(g, v1);
		j = LocateVex(g, v2);
		if (i == -1 || j == -1)return;
		g.arcs[i][j] = cost;
		g.arcs[j][i] = g.arcs[i][j];
	}
}
void out_UDG(Mgraph g)
{
	int i, j;
	printf("图的顶点是:n");
	for (i = 0; i < g.vex_num; i++)
	{
		printf("%8c", g.vertex[i]);
	}
	printf("n");
	printf("图的邻接矩阵是:n");
	for (i = 0; i < g.vex_num; i++)
	{
		for (j = 0; j < g.vex_num; j++)
			printf("%8d", g.arcs[i][j]);
		printf("n");
	}
}
int first_adj(Mgraph g, int v)
{
	int w = 0;
	while ((w < g.vex_num) && (g.arcs[v][w] == 10000))w++;
	if (w == g.vex_num)return -1;
	else return w;
}
int next_adj(Mgraph g, int v, int w)
{
	int u = w + 1;
	while ((u < g.vex_num) && (g.arcs[v][u] == 10000))
		u++;
	if (u == g.vex_num)return -1;
	else return u;
}
//深度优先搜索
void depth_first(Mgraph g, int v)
{
	int w;
	visited[v] = TURE;
	printf("%c", g.vertex[v]);
	for (w = first_adj(g, v); w >= 0; w = next_adj(g, v, w))
		if (!visited[w]) depth_first(g, w);
}
void depth_first_traverse(Mgraph g)
{
	//如果图不连通，再选一个点，遍历剩下的 
	int v;
	for (v = 0; v < g.vex_num; v++) visited[v] = 0;
	for (v = 0; v < g.vex_num; v++)
		if (!visited[v])depth_first(g, v);
}
int InitQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (Queueptr)malloc(sizeof(QNode));
	if (!Q.front)exit(OVERFLOW);
	Q.front->next = NULL;
	return OK;
}
//判断队列是否为空
int QueueEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)
		return 0;
	else return 1;
}
//销毁链队列
int DestoryQueue(LinkQueue& Q)
{
	while (Q.front) {
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
	return OK;
}
//入队
int EnQueue(LinkQueue& Q, int e)
{
	Queueptr p;
	p = (Queueptr)malloc(sizeof(QNode));
	if (!p)exit(OVERFLOW);
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
}

//出队
int DeQueue(LinkQueue& Q, int& e)
{
	Queueptr p;
	if (Q.front == Q.rear)return ERROR;
	p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if (Q.rear == p)Q.rear = Q.front;
	free(p);
	return e;
}
//广度优先搜索
void breadth_first_traverse(Mgraph g)
{
	int u, v, w, e;
	LinkQueue Q;
	for (v = 0; v < g.vex_num; v++)
		visited[v] = FLASE;
	for (v = 0; v < g.vex_num; v++)
		if (!visited[v]) {
			visited[v] = TURE;
			printf("%c", g.vertex[v]);
			EnQueue(Q, v);
			while (!QueueEmpty(Q)) {
				u = DeQueue(Q, e);
				for (w = first_adj(g, u); w >= 0; w = next_adj(g, u, w))
					if (!visited[w]) {
						visited[w] = TURE;
						printf("%c", g.vertex[w]);
						EnQueue(Q, e);
					}
			}
		}
	DestoryQueue(Q);
}
int main()
{
	int i, j, v;

	Mgraph g;
	create_UDG(g);   //用邻接表创建无向图 
	out_UDG(g);
	scanf("%d", &v);
	depth_first_traverse(g);  //深度优先遍历图 
	breadth_first_traverse(g);  //广度优先遍历图 
	return 0;
}