2023王道C语言督学营（图的邻接表-深度及广度优先遍历）

#include
#include
#include
#include
#define MAX 100
#define isLetter(a) ((((a)>='a')&&((a)<='z'))||(((a)>='A')&&((a)<='Z')))
#define LENGTH(a) (sizeof(a)/sizeof(a[0]))

typedef struct _ENode //邻接表中表对应的链表顶点
{
	int ivex;//该边所指向的顶点的位置
	struct _ENode* next_edge;//指向下一条弧的指针
}ENode,*PENode;

typedef struct _VNode//邻接表中表的顶点
{
	char data;//顶点的信息
	ENode* first_Edge;//指向第一条依附该顶点的弧

}VNode;
typedef struct _LGraph //邻接表
{
	int vexnum;//图的顶点的数目
	int edgnum;//图的边的数目
	VNode vexs[MAX];//结构体数组
}LGraph;

//创建邻接表对应的图（用已经提供的数据），无向图
LGraph* create_example_lgraph()
{
	char c1, c2;
	//事先创建一个邻接表
	char vexs[] = { 'A','B','C','D','E','F','G' };//图的顶点
	char edges[][2] = {//图的边
		{'A','C'},
		{'A','D'},
		{'A','F'},
		{'B','C'},
		{'C','D'},
		{'E','G'},
		{'F','G'} };
	int vlen = LENGTH(vexs);
	int elen = LENGTH(edges);
	//上面类似一个邻接矩阵存储
	int i, p1, p2;
	ENode* node1, * node2;
	LGraph* pG;//pG表示图
	if ((pG = (LGraph*)malloc(sizeof(LGraph))) == NULL)
		return NULL;
	//(申请空间的起始地址，0，空间大小)
	memset(pG, 0, sizeof(LGraph));//就是把申请的空间内初始化为0
	
	//初始化顶点数和边数
	pG->vexnum = vlen;
	pG->edgnum = elen;
	//初始化邻接表的顶点
	for (i = 0; i < pG->vexnum; i++)
	{
		pG->vexs[i].data = vexs[i];
		pG->vexs[i].first_Edge = NULL;
		
	}
	//初始化邻接表的边
	for (i = 0; i < pG->edgnum; i++)
	{
		边的顺序依赖与你创建的顺序
		//读取边的起始顶点和结束顶点
		c1 = edges[i][0];
		c2 = edges[i][1];

		//不需要对结构体做出改变所以直接传的是结构体而不是结构体指针
		p1 = get_position(*pG, c1);//p1对应起始顶点下表位置
		p2 = get_position(*pG, c2);//p2对应结束顶点下标位置

		//初始化node1
		//功能：在内存分配一个n倍size字节的存储区。调用结果为新分配的存储区的首地址，是一个void类型指针
		node1 = (ENode*)calloc(1, sizeof(ENode));
		//所指向顶点的位置
		node1->ivex = p2;
		//将node1连接到p1所在链表的表尾
		if (pG->vexs[p1].first_Edge == NULL)
			pG->vexs[p1].first_Edge = node1;
		else
			link_last(pG->vexs[p1].first_Edge, node1);

		//初始化node2 无向图有反向
		node2 = (ENode*)calloc(1, sizeof(ENode));
		node2->ivex = p1;
		//将p2连接到“p2所在的表尾”
		if (pG->vexs[p2].first_Edge == NULL)
			pG->vexs[p2].first_Edge = node2;
		else
			link_last(pG->vexs[p2].first_Edge, node2);
		
	}
	return pG;

}

get_position():

static int get_position(LGraph g, char ch)
{
//结构体数组中
	int i;
	for (i = 0; i < g.vexnum; i++)//在顶点结构体数组中遍历每个顶点
		if (g.vexs[i].data == ch)
			return i;//返回的是对应顶点的下标
	return -1;
}

void print_lgraph(LGraph G)
{
	int i;
	ENode* node;

	printf("List Graph:n");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%d(%c): ", i, G.vexs[i].data);
		node = G.vexs[i].first_Edge;
		while (node != NULL)//把每个顶点周围的节点都输出一下
		{
			printf("%d(%c): ",node->ivex,G.vexs[node->ivex].data);
			node = node->next_edge;
		}
		printf("n");
	}
}

打印无向图:

//深度优先搜索遍历图
void DFSTraverse(LGraph G)
{
	int i;
	int visited[MAX];//顶点访问标记

	//初始化所有顶点都没有被访问
	for (int i = 0; i < G.vexnum; i++)
	{
		visited[i] = 0;
	}
	printf("DFS: ");
	//从A开始深度优先遍历
	for (i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
			DFS(G, i, visited);
	}
	printf("n");
}

DFS()函数

static void DFS(LGraph G, int i, int* visited)
{
	ENode* node;
	visited[i] = 1;
	printf("%c ", G.vexs[i].data);
	node = G.vexs[i].first_Edge;//拿当前节点的下一个节点
	while (node != NULL)
	{
		if (!visited[node->ivex])//只要对应顶点没访问过深入下一个顶点访问
			DFS(G, node->ivex, visited);
		node = node->next_edge;//某个顶点的下一条边

	}
}

//BFS
void BFS(LGraph G)
{
	int head = 0;
	int rear = 0;
	int queue[MAX];//辅助队列
	int visited[MAX];//顶点访问标记
	int i, j, k;
	ENode* node;

	//每个顶点未被访问
	for (i = 0; i < G.vexnum; i++)
	{
		visited[i] = 0;
	}
	//从零号顶点开始遍历
	printf("BFS: ");
	for (i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])//如果没访问过就打印，同时入队，最初是A
		{
			visited[i] = 1;
			printf("%c ", G.vexs[i].data);
			queue[rear++] = i;//入队列
		}
		while (head != rear)//第一个进来的是A，遍历A的每一条边，入队成功
		{
			j = queue[head++];//出队列
			node = G.vexs[j].first_Edge;
			while (node != NULL)
			{
				k = node->ivex;
				if (!visited[k])
				{
					visited[k] = 1;
					printf("%c ", G.vexs[k].data);
					queue[rear++] = k;//类似于树的层次遍历，遍历到的同时入队
				}
				node = node->next_edge;
			}
		}
	}
}

int main()
{
	LGraph* pG;
	pG = create_example_lgraph();

	print_lgraph(*pG);
	//基于无向图的邻接链表
	DFSTraverse(*pG);//深度优先遍历
	BFS(*pG);//广度优先遍历
	system("pause");


}