严蔚敏数据结构图的深度与广度优先遍历_数据结构严蔚敏c语言版图广度优先

 头文件Graph.h

#include <stdio.h>
#include <string.h>
#define OK 1
#define INFINITY 32767
#define MAX_VERTEX_NUM 30
#define MAXINFOLEN 30
#define ERROR 0
#define OVERFLOW -1
#define MAXVERTEXLEN 30
#define FALSE 0
#define TRUE 1
typedef int Status;
typedef enum { DG, DN, UDG, UDN }GraphKind;
typedef int VRType;
typedef int InfoType;
typedef char* VertexType;
typedef struct ArcCell
{
	VRType adj;
	InfoType* info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum, arcnum;
	GraphKind kind;
}MGraph;
Status CreatGraph(MGraph* G)
{
	printf("请输入图的类型\n");
	scanf("%d", &(G->kind));
	switch (G->kind)
	{
	case DG:return(CreatDG(G)); break;
	case DN:return(CreatDN(G)); break;
	case UDG:return(CreatUDG(G)); break;
	case UDN:return(CreatUDN(G)); break;
	default: return ERROR;
	}
}
Status CreatDG(MGraph* G)
{
	printf("请依次输入图的总结点数，弧数，以及是弧是否需要额外信息，无额外信息输入0，有额外信息输入1\n");
	int info;
	scanf("%d%d%d", &(G->vexnum), &(G->arcnum), &info);
	getchar();
	printf("请输入%d个顶点的描述\n", G->vexnum);
	for (int i = 0; i < G->vexnum; i++)
	{
		G->vexs[i] = (VertexType)malloc(sizeof(char) * MAXVERTEXLEN);
		if (!G->vexs[i]) exit(OVERFLOW);
		gets(G->vexs[i]);
	}
	for(int i=0;i<G->vexnum;i++)
		for (int j = 0; j < G->vexnum; j++)
		{
			G->arcs[i][j].adj = 0;
			G->arcs[i][j].info = NULL;
		}
	int tail, head;
	char* ch;
	ch = (char*)malloc(sizeof(char) * MAXVERTEXLEN);
	if (!ch) exit(OVERFLOW);
	for (int i = 0; i < G->arcnum; i++)
	{
		printf("请输入第%d个顶点关系\n", i + 1);
		printf("请输入它的弧尾顶点描述\n");
		gets(ch);
		for (int j = 0; j < G->vexnum; j++)
			if (strcmp(ch, G->vexs[j]) == 0)
			{
				tail = j;
				break;
			}
		printf("请输入它的弧头顶点描述\n");
		gets(ch);
		for (int j = 0; j < G->vexnum; j++)
			if (strcmp(ch, G->vexs[j]) == 0)
			{
				head = j;
				break;
			}
		G->arcs[tail][head].adj = 1;
		if (info)
		{
			G->arcs[tail][head].info = (InfoType*)malloc(sizeof(InfoType) * MAXINFOLEN);
			if (!G->arcs[tail][head].info) exit(OVERFLOW);
			printf("请输入其信息\n");
			gets(G->arcs[tail][head].info);
		}
	}
	return OK;
}
Status CreatDN(MGraph* G)
{
	printf("请依次输入图的总结点数，弧数，以及是弧是否需要额外信息，无额外信息输入0，有额外信息输入1\n");
	int info;
	scanf("%d%d%d", &(G->vexnum), &(G->arcnum), &info);
	getchar();
	printf("请输入%d个顶点的描述\n", G->vexnum);
	for (int i = 0; i < G->vexnum; i++)
	{
		G->vexs[i] = (VertexType)malloc(sizeof(char) * MAXVERTEXLEN);
		if (!G->vexs[i]) exit(OVERFLOW);
		gets(G->vexs[i]);
	}
	for (int i = 0; i < G->vexnum; i++)
		for (int j = 0; j < G->vexnum; j++)
		{
			G->arcs[i][j].adj = INFINITY;
			G->arcs[i][j].info = NULL;
		}
	int tail, head;
	char* ch;
	ch = (char*)malloc(sizeof(char) * MAXVERTEXLEN);
	if (!ch) exit(OVERFLOW);
	for (int i = 0; i < G->arcnum; i++)
	{
		printf("请输入第%d个顶点关系\n", i + 1);
		printf("请输入它的弧尾顶点描述\n");
		gets(ch);
		for (int j = 0; j < G->vexnum; j++)
			if (strcmp(ch, G->vexs[j]) == 0)
			{
				tail = j;
				break;
			}
		printf("请输入它的弧头顶点描述\n");
		gets(ch);
		for (int j = 0; j < G->vexnum; j++)
			if (strcmp(ch, G->vexs[j]) == 0)
			{
				head = j;
				break;
			}
		printf("请输入弧的权值\n");
		scanf("%d", &(G->arcs[tail][head]));
		getchar();
		if (info)
		{
			G->arcs[tail][head].info = (InfoType*)malloc(sizeof(InfoType) * MAXINFOLEN);
			if (!G->arcs[tail][head].info) exit(OVERFLOW);
			printf("请输入其信息\n");
			gets(G->arcs[tail][head].info);
		}
	}
	return OK;
}
Status CreatUDG(MGraph* G)
{
	printf("请依次输入图的总结点数，弧数，以及是弧是否需要额外信息，无额外信息输入0，有额外信息输入1\n");
	int info;
	scanf("%d%d%d", &(G->vexnum), &(G->arcnum), &info);
	getchar();
	printf("请输入%d个顶点的描述\n", G->vexnum);
	for (int i = 0; i < G->vexnum; i++)
	{
		G->vexs[i] = (VertexType)malloc(sizeof(char) * MAXVERTEXLEN);
		if (!G->vexs[i]) exit(OVERFLOW);
		gets(G->vexs[i]);
	}
	for (int i = 0; i < G->vexnum; i++)
		for (int j = 0; j < G->vexnum; j++)
		{
			G->arcs[i][j].adj = 0;
			G->arcs[i][j].info = NULL;
		}
	int vex1, vex2;
	char* ch;
	ch = (char*)malloc(sizeof(char) * MAXVERTEXLEN);
	if (!ch) exit(OVERFLOW);
	for (int i = 0; i < G->arcnum; i++)
	{
		printf("请输入第%d个顶点关系\n", i + 1);
		printf("请输入它所依附的第一个顶点的顶点描述\n");
		gets(ch);
		for (int j = 0; j < G->vexnum; j++)
			if (strcmp(ch, G->vexs[j]) == 0)
			{
				vex1 = j;
				break;
			}
		printf("请输入它所依附的第二个顶点的顶点描述\n");
		gets(ch);
		for (int j = 0; j < G->vexnum; j++)
			if (strcmp(ch, G->vexs[j]) == 0)
			{
				vex2 = j;
				break;
			}
		G->arcs[vex1][vex2].adj = 1;
		G->arcs[vex2][vex1].adj = 1;
		if (info)
		{
			G->arcs[vex1][vex2].info = (InfoType*)malloc(sizeof(InfoType) * MAXINFOLEN);
			if (!G->arcs[vex1][vex2].info) exit(OVERFLOW);
			printf("请输入其信息\n");
			gets(G->arcs[vex1][vex2].info);
			G->arcs[vex2][vex1].info = (InfoType*)malloc(sizeof(InfoType) * MAXINFOLEN);
			if (!G->arcs[vex2][vex1].info) exit(OVERFLOW);
			strcpy(G->arcs[vex2][vex1].info, G->arcs[vex1][vex2].info);
		}
	}
	return OK;
}
Status CreatUDN(MGraph* G)
{
	printf("请依次输入图的总结点数，弧数，以及是弧是否需要额外信息，无额外信息输入0，有额外信息输入1\n");
	int info;
	scanf("%d%d%d", &(G->vexnum), &(G->arcnum), &info);
	getchar();
	printf("请输入%d个顶点的描述\n", G->vexnum);
	for (int i = 0; i < G->vexnum; i++)
	{
		G->vexs[i] = (VertexType)malloc(sizeof(char) * MAXVERTEXLEN);
		if (!G->vexs[i]) exit(OVERFLOW);
		gets(G->vexs[i]);
	}
	for (int i = 0; i < G->vexnum; i++)
		for (int j = 0; j < G->vexnum; j++)
		{
			G->arcs[i][j].adj = INFINITY;
			G->arcs[i][j].info = NULL;
		}
	int vex1, vex2;
	char* ch;
	ch = (char*)malloc(sizeof(char) * MAXVERTEXLEN);
	if (!ch) exit(OVERFLOW);
	for (int i = 0; i < G->arcnum; i++)
	{
		printf("请输入第%d个顶点关系\n", i + 1);
		printf("请输入它所依附的第一个顶点的顶点描述\n");
		gets(ch);
		for (int j = 0; j < G->vexnum; j++)
			if (strcmp(ch, G->vexs[j]) == 0)
			{
				vex1 = j;
				break;
			}
		printf("请输入它所依附的第二个顶点的顶点描述\n");
		gets(ch);
		for (int j = 0; j < G->vexnum; j++)
			if (strcmp(ch, G->vexs[j]) == 0)
			{
				vex2 = j;
				break;
			}
		printf("请输入此弧权值\n");
		scanf("%d", &(G->arcs[vex1][vex2].adj));
		getchar();
		G->arcs[vex2][vex1].adj = G->arcs[vex1][vex2].adj;
		if (info)
		{
			G->arcs[vex1][vex2].info = (InfoType*)malloc(sizeof(InfoType) * MAXINFOLEN);
			if (!G->arcs[vex1][vex2].info) exit(OVERFLOW);
			printf("请输入其信息\n");
			gets(G->arcs[vex1][vex2].info);
			G->arcs[vex2][vex1].info = (InfoType*)malloc(sizeof(InfoType) * MAXINFOLEN);
			if (!G->arcs[vex2][vex1].info) exit(OVERFLOW);
			strcpy(G->arcs[vex2][vex1].info, G->arcs[vex1][vex2].info);
		}
	}
	return OK;
}
//孩子兄弟树的数据结构描述
typedef char* TElemType;
typedef struct CSNode
{
	TElemType data;
	struct CSNode* firstchild, * nextsibling;
}CSNode, * CSTree;
//队列函数
typedef CSTree QElemType;
typedef struct QNode
{
	QElemType data;
	struct QNode* next;
}QNode, * QueuePtr;
typedef struct
{
	QueuePtr front, rear;
}LinkQueue;
Status InitQueue(LinkQueue* Q)
{
	Q->front = (QNode*)malloc(sizeof(QNode));
	if (!Q->front) exit(OVERFLOW);
	Q->rear = Q->front;
	return OK;
}
Status EnQueue(LinkQueue* Q, QElemType e)
{
	QNode* p;
	p = (QNode*)malloc(sizeof(QNode));
	if (!p) exit(OVERFLOW);
	p->data = e;
	Q->rear->next = p;
	Q->rear = p;
	p->next = NULL;
	return OK;
}
Status DeQueue(LinkQueue* Q, QElemType* e)
{
	if (Q->front == Q->rear)
		return ERROR;
	*e = Q->front->next->data;
	if (Q->rear == Q->front->next)
		Q->rear = Q->front;
	QNode* p = Q->front->next;
	Q->front->next = p->next;
	free(p);
	return OK;
}
Status QueueEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)
		return TRUE;
	else
		return FALSE;
}
void PrintQueue(LinkQueue Q)
{
	QNode* p = Q.front->next;
	if (!p)
		printf("空\n");
	else
	{
		while (p)
		{
			printf("%d\t", p->data + 1);
			p = p->next;
		}
		printf("\n");
	}
}

c文件：

#include "Graph.h"
Status PutString(VertexType v)
{
	puts(v);
	return OK;
}
//图的深度优先遍历，邻接矩阵存储图
int visited[MAX_VERTEX_NUM];
void DFS(MGraph G, int w, Status(*Visit)(VertexType e))
{
	visited[w] = TRUE;
	Visit(G.vexs[w]);
	for (int v = 0; v < G.vexnum; v++)
	{
		if (!visited[v] && G.arcs[w][v].adj == 1)
			DFS(G, v, Visit);
	}
}
void DFSTraverse(MGraph G, Status(*Visit)(VertexType e))
{
	for (int i = 0; i < G.vexnum; i++)
		visited[i] = FALSE;
	for (int i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
			DFS(G, i, Visit);
	}
	return OK;
}
//广度优先遍历邻接矩阵存储图
void BFSTraverse(MGraph G, Status(*Visit)(VertexType e))
{
	LinkQueue* Q;
	Q = (LinkQueue*)malloc(sizeof(LinkQueue));
	if (!Q) exit(OVERFLOW);
	InitQueue(Q);
	for (int i = 0; i < G.vexnum; i++)
		visited[i] = FALSE;
	for (int i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
		{
			Visit(G.vexs[i]);
			visited[i] = TRUE;
			EnQueue(Q, i);
			while (!QueueEmpty(*Q))
			{
				int k;
				DeQueue(Q, &k);
				for (int j = 0; j < G.vexnum; j++)
				{
					if (!visited[j] && G.arcs[k][j].adj)
					{
						EnQueue(Q, j);
						Visit(G.vexs[j]);
						visited[j] = TRUE;
					}
				}
			}
		}
	}
}
int main()
{
	MGraph G;
	CreatGraph(&G);
	printf("\t");
	for (int i = 0; i < G.vexnum; i++)
		printf("V%d\t", i + 1);
	printf("\n\n");
	for (int i = 0; i < G.vexnum; i++)
	{
		printf("V%d\t", i + 1);
		for (int j = 0; j < G.vexnum; j++)
			printf("%d\t", G.arcs[i][j].adj);
		printf("\n\n\n");
	}
	Status* Visit;
	Visit = PutString;
    printf("深度优先遍历结果为：\n");
	DFSTraverse(G, Visit);
    printf("广度优先遍历结果为：\n");
    BFSTraverse(G, Visit);
	return 0;
}

输入：

2
8 9 0
V1
V2
V3
V4
V5
V6
V7
V8
V1
V2
V1
V3
V2
V4
V2
V5
V4
V8
V5
V8
V3
V6
V3
V7
V6
V7

 原图：

 领接矩阵：

结果：