考研C语言数据结构-图(图的邻接矩阵实现 + 广度、深度优先遍历)

本文主要是介绍考研C语言数据结构-图(图的邻接矩阵实现 + 广度、深度优先遍历)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

图的结构如下：

图的邻接矩阵实现 + 广度(BFS)、深度(DFS)优先遍历：

#include<stdio.h>
#include<stdlib.h>

#define MAXVEXNUM 10

// 定义图的邻接矩阵存储结构
struct MGraph{

	int vex[MAXVEXNUM]; // 顶点集
	int edge[MAXVEXNUM][MAXVEXNUM]; // 边集
	int vexNum, arcNum;
};

// 初始化邻接矩阵
void initMGraph(MGraph& G) {

	for(int i = 0;i < 8;i++) {
	
		G.vex[i] = i + 1;
	}

	G.vexNum = 8;

	for(int i = 0;i < G.vexNum;i++) {
	
		for(int j = 0;j < G.vexNum;j++) {
		
			G.edge[i][j] = 0;
		}
	}

	G.edge[0][1] = G.edge[0][4] = 1;
	G.edge[1][0] = G.edge[1][5] = 1;
	G.edge[2][3] = G.edge[2][5] = G.edge[2][6] = 1;
	G.edge[3][2] = G.edge[3][6] = G.edge[3][7] = 1;
	G.edge[4][0] = 1;
	G.edge[5][1] = G.edge[5][2] = G.edge[5][6] = 1;
	G.edge[6][2] = G.edge[6][3] = G.edge[6][5] = G.edge[6][7] = 1;
	G.edge[7][3] = G.edge[7][6] = 1;

	G.arcNum = 10;
}

// 广度优先遍历

// ①定义队列数据结构
// 定义结点数据类型
typedef struct LNode {

	int data;
	struct LNode *next;
}LNode;

// 定义链队数据类型
typedef struct {

	LNode *front, *rear;
}LiQueue;

void initLiQueue(LiQueue &Q) {

	Q.front = Q.rear = (LNode *)malloc(sizeof(LNode));
	Q.front->next = NULL;
}

// 判断队列空
bool isEmpty(LiQueue Q) {

	if(Q.front == Q.rear)
		return true;

	return false;
}

// 入队操作
void enQueue(LiQueue &Q, int e) {

	LNode *p = (LNode *)malloc(sizeof(LNode));

	p->data = e;

	p->next = NULL;

	Q.rear->next = p;

	Q.rear = p;
}

// 出队操作
bool deQueue(LiQueue &Q, int &e) {

	if(isEmpty(Q))
		return false;

	LNode *p = Q.front->next;

	e = p->data;

	Q.front->next = p->next;

	// 如果出队元素是队列的最后一个元素,需要修改尾指针
	if(p == Q.rear)
		Q.rear = Q.front;

	free(p);

	return true;
}

// 定义访问数组，标记已访问顶点
bool visited[MAXVEXNUM];

// 获取顶点v的相邻顶点
int getFirstNeighbor(MGraph G, int v) {

	for(int i = 0;i < G.vexNum;i++) {
	
		if(G.edge[v - 1][i] != 0) // v-1因为数组是从0开始的，而顶点从1开始
			return i + 1;
	}

	return -1;// -1表示没有相邻顶点
}

// 获取顶点v除顶点u之外的相邻顶点
int getNextNeighbor(MGraph G, int v, int u) {

	for(int i = u;i < G.vexNum;i++) {
	
		if(G.edge[v - 1][i] != 0)
			return i + 1;
	}

	return -1;
}

void BFS(MGraph G, int v, LiQueue &Q) {

	printf("广度优先遍历顶点:%d\n", v);
	visited[v - 1] = true;
	enQueue(Q, v);

	while(!isEmpty(Q)) {
	
		deQueue(Q, v);
		for(int w = getFirstNeighbor(G, v);w >= 1;w = getNextNeighbor(G, v, w)) {
		
			if(!visited[w - 1]) {
			
				printf("广度优先遍历顶点:%d\n", w);
				visited[w - 1] = true;
				enQueue(Q, w);
			}
		}
	}
}

void BFSTraverse(MGraph G) {

	for(int i = 0;i < G.vexNum;i++) {
	
		visited[i] = false;
	}

	LiQueue Q;
	initLiQueue(Q);

	for(int i = 0;i < G.vexNum;i++) {
	
		if(!visited[i])
			BFS(G, G.vex[i], Q);
	}
}

// 深度优先遍历
void DFS(MGraph G, int v) {

	printf("深度优先遍历顶点:%d\n", v);
	visited[v - 1] = true;

	for(int w = getFirstNeighbor(G, v);w >= 1;w = getNextNeighbor(G, v, w)) {
	
		if(!visited[w - 1]) {
		
			DFS(G, w);
		}
	}
}

void DFSTravse(MGraph G) {

	for(int i = 0;i < G.vexNum;i++) {
	
		visited[i] = false;
	}

	for(int i = 0;i < G.vexNum;i++) {
	
		if(!visited[i])
			DFS(G, G.vex[i]);
	}
}

int main(void) {

	MGraph G;
	initMGraph(G);

	BFSTraverse(G);

	printf("\n");

	DFSTravse(G);
	system("pause");
	return 0;
}

这篇关于考研C语言数据结构-图(图的邻接矩阵实现 + 广度、深度优先遍历)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！