408 数据结构图算法

标签：VertexType start int ++ 算法 printf 顶点数据结构 408

第五章图

5.1图的邻接矩阵存储

//无向图的邻接矩阵存储
#define MAXSIZE 16		//图的最大顶点个数
typedef int VertexType;	//顶点类型
typedef int EdgeType;	//边类型

typedef struct {
	VertexType Vex[MAXSIZE];		//图的顶点集
	EdgeType Edge[MAXSIZE][MAXSIZE];	//图的边集
	int verNum;		//实际顶点的数量
	int edgeNum;	//实际边的数量
}Graph;

//图的初始化
void initGraph(Graph& G) {
	//给顶点集设置初始值
	for (int i = 0; i < MAXSIZE; i++) {
		G.Vex[i] = 0;
	}
	//给边集设置初始值
	for (int i = 0; i < MAXSIZE; i++) {
		for (int j = 0; j < MAXSIZE; j++) {
			G.Edge[i][j] = 0;
		}
	}
	//初始化顶点和边的个数都为0
	G.verNum = 0;
	G.edgeNum = 0;
}


//添加顶点
void addVertex(Graph& G, VertexType v) {
	if (G.verNum >= MAXSIZE) {
		printf("顶点集已满\n");
		return;
	}
	G.Vex[G.verNum++] = v;
}
//查找顶点v在图G的顶点集中的下标
int verIsExist(Graph G, VertexType v) {
	for (int i = 0; i < G.verNum; i++) {
		if (G.Vex[i] == v) {
			return i;
		}
	}
	return -1;
}

//添加边集
void addEdge(Graph& G, VertexType v1,VertexType v2,EdgeType weight) {
	//查找v1和v2顶点在图G顶点集中的下标索引
	int index1 = verIsExist(G, v1);		
	int index2 = verIsExist(G, v2);
	if (index1 == -1 ||index2 == -1) {
		return;
	}
	//给边集设置权重，因为是无向图所以要进行双向设置
	G.Edge[index1][index2] = weight;
	G.Edge[index2][index1] = weight;	//如果是有向图把这一句去掉就行然后创建时所有的边都要输入就行
	G.edgeNum++;
}

//打印图
void printGraph(Graph G) {
	printf("图G的顶点集：\n");
	for (int i = 0; i < G.verNum; i++) {
		printf("%d ", G.Vex[i]);
	}
	printf("\n");
	printf("图G的边集：\n\t");
	for (int i = 0; i < G.verNum; i++) {
		printf("v%d\t", G.Vex[i]);
	}
	printf("\n");
	for (int i = 0; i < G.verNum; i++) {
		printf("v%d\t", G.Vex[i]);
		for (int j = 0; j < G.verNum; j++) {
			printf("%d\t", G.Edge[i][j]);
		}
		printf("\n\n");
	}
	printf("\n");
}

//创建图的顶点集和边集
void createGraph(Graph& G) {
	VertexType v;
	printf("请输入要创建图G的顶点集：\n");
	scanf("%d", &v);
	while (v != 999) {
		addVertex(G, v);
		scanf("%d", &v);
	}
	printf("请输入要创建图G的边集（v1 v2 weight）：\n");
	VertexType v1, v2;
	EdgeType weight;
	scanf("%d%d%d", &v1, &v2, &weight);
	while (weight != 0) {
		addEdge(G,v1, v2, weight);
		scanf("%d%d%d", &v1, &v2, &weight);
	}
}
//针对无向图
//找顶点x的度
int degree(Graph G, VertexType x) {
	int index = verIsExist(G, x);
	if (index == -1) {
		return 0;
	}
	int count = 0;	//用来记录下顶点x的度数
	for (int i = 0; i < G.verNum; i++) {
		if (G.Edge[index][i] != 0) {
			count++;
		}
		/*if (G.Edge[i][index] != 0) {
			count++;
		}*/
	}
	return count;
}

//针对有向图
//找顶点x的入度
int inDegree(Graph G, VertexType x) {
	int index = verIsExist(G, x);
	if (index == -1) {
		return 0;
	}
	int count = 0;	//用来记录下顶点x的度数
	for (int i = 0; i < G.verNum; i++) {
		if (G.Edge[i][index] != 0) {
			count++;
		}
	}
	return count;
}

//找顶点x的出度
int outDegree(Graph G, VertexType x) {
	int index = verIsExist(G, x);
	if (index == -1) {
		return 0;
	}
	int count = 0;	//用来记录下顶点x的度数
	for (int i = 0; i < G.verNum; i++) {
		/*if (G.Edge[i][index] != 0) {
			count++;
		}*/
		if (G.Edge[index][i] != 0) {
			count++;
		}
	}
	return count;
}

5.2图的邻接表存储

#define MAXSIZE 16
typedef int VertexType;	//顶点类型
//边表结点
typedef struct ArcNode {
	int adjVex;		//理解成顶点的data域
	ArcNode* next;	//指向下一个边表中的结点
}ArcNode;
//顶点表
typedef struct VNode {
	VertexType data;	//顶点信息
	ArcNode* first;		//指向边表
}VNode,adjList[MAXSIZE];

//图的邻接表存储
typedef struct {
	adjList vertices;	//邻接表
	int vexNum;		//顶点数
	int arcNum;		//边数
}Graph;


//初始化图
void initGraph(Graph& G) {
	for (int i = 0; i < MAXSIZE; i++) {
		G.vertices[i].data = 0;
		G.vertices[i].first = NULL;
	}
	G.arcNum = 0;
	G.vexNum = 0;
}
//添加顶点
void addVertex(Graph& G, VertexType vertex) {
	if (G.vexNum >= MAXSIZE) {
		printf("顶点集已满\n");
		return;
	}
	G.vertices[G.vexNum++].data = vertex;
}
//如果顶点在图中存在范围其在顶点表中的下标，不存在返回-1
int verIsExist(Graph G, VertexType v) {
	for (int i = 0; i < G.vexNum; i++) {
		if (G.vertices[i].data == v) {
			return i;
		}
	}
	return -1;
}

//添加边
void addEdge(Graph& G, VertexType v1, VertexType v2) {
	int index1 = verIsExist(G, v1);
	int index2 = verIsExist(G, v2);
	if (index1 == -1 || index2 == -1) {
		return;
	}
	/*//头插法创建
	//创建v1的边表结点
	ArcNode* node1 = (ArcNode *)malloc(sizeof(ArcNode));
	node1->adjVex = v2;
	node1->next = G.vertices[index1].first;
	G.vertices[index1].first = node1;
	//创建v2的边表结点
	ArcNode* node2 = (ArcNode*)malloc(sizeof(ArcNode));
	node2->adjVex = v1;
	node2->next = G.vertices[index2].first;
	G.vertices[index2].first = node2;
	G.arcNum++;*/
    
	//尾插法创建
	// 创建v1的边表结点
	ArcNode* node1 = (ArcNode*)malloc(sizeof(ArcNode));
	node1->adjVex = v2;
	node1->next = NULL;
	if (G.vertices[index1].first == NULL) {
		G.vertices[index1].first = node1;
	}
	else {
		ArcNode* tail = G.vertices[index1].first;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = node1;
	}
	// 创建v2的边表结点
	ArcNode* node2 = (ArcNode*)malloc(sizeof(ArcNode));
	node2->adjVex = v1;
	node2->next = NULL;

	if (G.vertices[index2].first == NULL) {
		G.vertices[index2].first = node2;
	}
	else {
		ArcNode* tail = G.vertices[index2].first;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = node2;
	}

	G.arcNum++;
	
}
//打印图
void printGraph(Graph G) {
	printf("图G的邻接表存储：\n");
	for (int i = 0; i < G.vexNum; i++) {
		printf("%d：", G.vertices[i].data);
		ArcNode* cur = G.vertices[i].first;
		while (cur) {
			printf("%d->", cur->adjVex);
			cur = cur->next;
		}
		printf("\n");
	}
}
//创建图的顶点集和边集
void createGraph(Graph& G) {
	VertexType v;
	printf("请输入要创建图G的顶点集：\n");
	scanf("%d", &v);
	while (v != 999) {
		addVertex(G, v);
		scanf("%d", &v);
	}
	printf("请输入要创建图G的边集（v1 v2）：\n");
	VertexType v1, v2;
	scanf("%d%d", &v1, &v2);
	while (v1!=999||v2!=999) {
		addEdge(G, v1, v2);
		scanf("%d%d", &v1, &v2);
	}
}

//判断图G中v1、v2是否有边
bool adjacent(Graph G, VertexType v1, VertexType v2) {
	int index1 = verIsExist(G, v1);
	int index2 = verIsExist(G, v2);
	if (index1 == -1 || index2 == -1) {
		return false;
	}
	ArcNode* cur = G.vertices[index1].first;	//拿到v1顶点在页表中的第一个节点
	while (cur) {
		if (cur->adjVex == v2) {
			return true;
		}
		cur = cur->next;
	}
	return false;
}

//列出图G中与所有x邻接的顶点
void findAllNeighbors(Graph G, VertexType x, VertexType neighbors[]) {
	int index = verIsExist(G, x);
	if (index == -1) {
		printf("顶点%d不存在\n", x);
		return;
	}
	int count = 0;
	ArcNode* cur = G.vertices[index].first;
	while (cur) {
		neighbors[count++] = cur->adjVex;
		cur = cur->next;
	}
}

//求图G中顶点x的第一个邻接点，若有则返回顶点，没有返回-1
VertexType FirstNeighbor(Graph G, VertexType x) {
	int index = verIsExist(G, x);
	if (index == -1) {
		printf("顶点%d不存在\n",x);
		return -1;
	}
	ArcNode* cur = G.vertices[index].first;
	return cur ? cur->adjVex : -1;
}
//假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点，如y是x的最后一个顶点，返回-1
VertexType nextNeighbor(Graph G, VertexType x, VertexType y) {
	int index = verIsExist(G, x);
	if (index == -1) {
		printf("顶点%d不存在\n", x);
		return -1;
	}
	ArcNode* cur = G.vertices[index].first;
	while (cur && cur->adjVex != y) {
		cur = cur->next;
	}
	if (cur && cur->next) {
		return cur->next->adjVex;
	}
	return -1;
}

//找x顶点的入度
int inDegree(Graph G, VertexType x) {
	int count = 0;
	for (int i = 0; i < G.vexNum; i++) {
		ArcNode* cur = G.vertices[i].first;
		while (cur) {
			if (cur->adjVex == x) {
				count++;
			}
			cur = cur->next;
		}
	}
	return count;
}

//找x顶点的出度
int outDegree(Graph G, VertexType x) {
	int index = verIsExist(G, x);
	if (index == -1) {
		return 0;
	}
	ArcNode* cur = G.vertices[index].first;
	int count = 0;
	while (cur) {
		count++;
		cur = cur->next;
	}
	return count;
}

5.3图的广度优先遍历

//从起始顶点start开始对图G进行广度优先遍历
void bfs(Graph G,VertexType start) {
	Queue Q;
	initQueue(Q);
	bool visited[MAXSIZE] = { false };//用来表示顶点是否访问过了
	enQueue(Q, start);	//起始结点入队
	visited[verIsExist(G, start)] = true;	//将起始结点标志为已访问
	while (!isEmpty(Q)) {
		VertexType poll = deQueue(Q);	
		printf("%d ", poll);
		VertexType neigbhors[MAXSIZE];	
		findAllNeighbors(G, poll, neigbhors);	//拿到出队结点的所有邻居结点
		for (int i = 0; i < outDegree(G, poll); i++) {	
			//如果没有访问过当前结点才进行入队操作，并设置为已访问
			if (!visited[verIsExist(G, neigbhors[i])]) {
				visited[verIsExist(G, neigbhors[i])] = true;
				enQueue(Q, neigbhors[i]);
			}
		}
	}
}

5.4图的深度优先遍历

//从起始顶点start开始对图G进行深度优先遍历（递归）
bool visit[MAXSIZE] = { false };
void dfs(Graph G, VertexType start) {
	visit[verIsExist(G, start)] = true;
	printf("%d ", start);
	VertexType neigbhors[MAXSIZE];
	findAllNeighbors(G, start, neigbhors);
	for (int i = 0; i < outDegree(G, start); i++) {
		if (!visit[verIsExist(G, neigbhors[i])]) {
			dfs(G, neigbhors[i]);
		}
	}
}
//从起始顶点start开始对图G进行深度优先遍历（非递归）
void dfs2(Graph G, VertexType start) {
	Stack S;
	initStack(S);
	bool visited[MAXSIZE] = { false };//用来表示顶点是否访问过了
	push(S, start);
    printf("%d ", start);
	visited[verIsExist(G, start)] = true;
	while (!isEmpty(S)) {
		VertexType poll = pop(S);
		VertexType neigbhors[MAXSIZE];
		findAllNeighbors(G, poll, neigbhors);	//拿到出队结点的所有邻居结点
		for (int i = 0; i < outDegree(G, poll); i++) {
			if (!visited[verIsExist(G, neigbhors[i])]) {
				push(S, neigbhors[i]);
                 printf("%d ", neigbhors[i]);
				visited[verIsExist(G, neigbhors[i])] = true;            
			}
		}
	}
}

5.5单源最短路径（Dijkstra）不能解决带负权边问题

1 2 7
1 3 9
1 6 14
2 4 15
3 6 2
3 4 11
4 5 6
6 5 9
0 0 0

初始化准备：

set数组用来记录顶点是否被访问过

dist数组用来记录源点到各个顶点的距离

path数组用来记录当前节点的前驱结点（即从何而来）

算法步骤：

将所有顶点标记为未访问，因此需要有一个数组set来记录当前结点是否被访问过
为每个顶点分配一个临时距离值。
1. 对于我们初始化顶点，将其设置为0（单独设置）
2. 对于其他所有顶点，将其设置为无穷大
先将与起始点相连的顶点距离进行更新，即更新dist数组
每次选取最小临时距离的未访问顶点，更新dist数组，同时将最小值顶点标记为已访问
更新每次与最小值相邻的顶点的距离值并且记录从何而来

1 2 10
1 5 5
2 5 2
2 3 1
3 4 4
4 1 7
4 3 6
5 2 3
5 4 2
5 3 9
0 0 0

负权图

#define INF 65535
bool set[MAXSIZE] = { false };//记录已求得的最短路径的顶点
int dist[MAXSIZE] = {INF };//记录了从源点start到其他各顶点当前的最短路径长度

VertexType path[MAXSIZE];//path[i]表示从源点到顶点i之间的最短路径的前驱结点

void dijkstra(Graph G, VertexType start) {
	int index = verIsExist(G, start);
	for (int i = 0; i < G.verNum; i++) {
		dist[i] = G.Edge[index][i];
		if (dist[i] < INF) {
			path[i] = start;
		}
		else {
			path[i] = -1;	//表示顶点v不可达
		}
	}
	//set[start] = true;  错误写法（书上这么写是默认规定顶点的值和序号是一一对应的了，实际这么写有问题的）
	//比如一共3个顶点，100,1000,10000。你总不能set[10000]吧
	set[index] = true;
	dist[index] = 0;
	for (int i = 1; i < G.verNum; i++) {
		int min = INF;
		int minIndex;
		for (int w = 0; w < G.verNum; w++) {
			if (!set[w] && dist[w] < min) {
				min = dist[w];
				minIndex = w;
			}
		}
		set[minIndex] = true;
		for (int w = 0; w < G.verNum; w++) {
			if (!set[w] && min + G.Edge[minIndex][w] < dist[w]) {
				dist[w] = min + G.Edge[minIndex][w];
				path[w] = G.Vex[minIndex];
			}
		}
	}
}

void printDijkStraInfo(Graph G) {
	for (int i = 0; i < G.verNum; i++) {
		printf("%d\t", G.Vex[i]);
	}
	printf("\n");
	printf("dist数组：\n");
	for (int i = 0; i < G.verNum; i++) {
		printf("%d\t", dist[i]);
	}
	printf("\n");
	printf("path数组：\n");
	for (int i = 0; i < G.verNum; i++) {
		printf("%d\t", path[i]);
	}
	printf("\n");
}

5.6 多源最短路径（Floyd）

算法思想：

定义dist数组，用来存储最短路径权值信息，初始时将图的邻接矩阵赋值给dists
定义paths数组，用来存储最短路径，初始化将矩阵paths中元素全部设置为-1
依次借助顶点v1,v2...,vn，比较比较dists【i】【j】与dists【i】【k】+dists【k】【j】的值，修改dists数组与paths数组

算法代码

#define RED "\x1B[31m"
#define GREEN "\x1B[32m"
#define YELLOW "\x1B[33m"
#define BLUE "\x1B[34m"
#define RESET "\x1B[0m"


#define INF 65535
int dists[MAXSIZE][MAXSIZE];	//存储最短路径长度，初始时将图的邻接矩阵赋值给dists
VertexType paths[MAXSIZE][MAXSIZE];//存储最短路径，将矩阵Path中元素全部设置为-1

void floyd(Graph G) {
	//初始化dists和paths
	for (int i = 0; i < G.verNum; i++) {
		for (int j = 0; j < G.verNum; j++) {
			dists[i][j] = G.Edge[i][j];
			paths[i][j] = -1;	//初始化路径为-1
		}
	}
	/*
		 初始化              k=0 借助v1顶点到达其他顶点
		 v1 v2 v3 v4			v1 v2 v3 v4
	  v1 0  ∞ -2 ∞		 v1 0  ∞ -2 ∞
	  v2 4  0  3  ∞         v2 4  0  2  ∞
	  v3 ∞ ∞ 0  2          v3 ∞ ∞ 0  2
	  v4 ∞ -1 ∞ 0          v4 ∞ -1 ∞ 0

							 k=1 借助v2顶点到达其他顶点
								v1 v2 v3 v4
							 v1 0  ∞ -2 ∞
							 v2 4  0  2  ∞
							 v3 ∞ ∞ 0  2
							 v4 3 -1  1  0

							 k=2 借助v3顶点到达其他顶点
								v1 v2 v3 v4
							 v1 0  ∞ -2 0
							 v2 4  0  2  4
							 v3 ∞ ∞ 0  2
							 v4 3 -1  1  0

							 k=3 借助v4顶点到达其他顶点
								v1 v2 v3 v4
							 v1 0  -1 -2 0
							 v2 4  0  2  4
							 v3 5  1  0  2
							 v4 3 -1  1  0

	*/
	//看能否借路到达其他顶点
	/*
	*	v2借助v1到其他顶点去
		v2->v1           v1->v?
		dists[1][0]  +   dists[0][0]
		dists[1][0]  +   dists[0][1]
		dists[1][0]  +   dists[0][2]
		dists[1][0]  +   dists[0][3]
	*/
	for (int k = 0; k < G.verNum; k++) {
		for (int i = 0; i < G.verNum; i++) {
			for (int j = 0; j < G.verNum; j++) {
				if (dists[i][k] != INF &&
					dists[k][j] != INF &&
					dists[i][k] + dists[k][j] < dists[i][j]) {
					dists[i][j] = dists[i][k] + dists[k][j];
					paths[i][j] = G.Vex[k]; // 记录路径上的中间顶点 k
				}
			}
		}
	}
}
void printShortestPaths(Graph G) {
	printf("最短路径长度矩阵:\n");
	printf("\t");
	for (int i = 0; i < G.verNum; i++) {
		printf(RED"%d\t" RESET, G.Vex[i]);
	}
	printf("\n");
	for (int i = 0; i < G.verNum; ++i) {
		printf(RED"%d\t" RESET, G.Vex[i]);
		for (int j = 0; j < G.verNum; ++j) {
			if (dists[i][j] == INF) {
				printf("∞\t");
			}
			else {
				printf("%d\t", dists[i][j]);
			}
		}
		printf("\n");
	}

	printf("\n最短路径矩阵:\n");
	printf("\t");
	for (int i = 0; i < G.verNum; i++) {
		printf(GREEN"%d\t" RESET, G.Vex[i]);
	}
	printf("\n");
	for (int i = 0; i < G.verNum; ++i) {
		printf(GREEN "%d\t" RESET, G.Vex[i]);
		for (int j = 0; j < G.verNum; ++j) {
			printf("%d\t", paths[i][j]);
		}
		printf("\n");
	}
}

5.7 并查集

typedef int ElemType;

//并查集
typedef struct {
	ElemType* info;
	ElemType* size;
}DisjoinSet;

//初始化
void initDisjoinSet(DisjoinSet& set, int size) {
	set.info = (ElemType*)malloc(sizeof(ElemType) * size);
	set.size = (ElemType*)malloc(sizeof(ElemType) * size);
	for (int i = 0; i < size; i++) {
		set.info[i] = i;
		set.size[i] = 1;
	}
}

//找老大
int find(DisjoinSet& set, int x) {
	if (x == set.info[x]) {
		return x;
	}
	return find(set, set.info[x]);
}

//找老大（路径压缩）
int find2(DisjoinSet& set, int x) {
	if (x == set.info[x]) {
		return x;
	}
	return set.info[x] = find2(set, set.info[x]);
}

//让两个集合相交，即选出新老大，x,y是原老大索引
void unions(DisjoinSet& set, int x, int y) {
	set.info[y] = x;
}

//合并优化
void unions2(DisjoinSet& set, int x, int y) {
	if (set.size[x] < set.size[y]) {
		//y 老大 x小弟
		set.info[x] = y;
		set.size[y] = set.size[x] + set.size[y];	//更新老大个数
	}
	else {
		// x老大，y小弟
		set.info[y] = x;
		set.size[x] = set.size[x] + set.size[y];
	}
	//下面写法一样
	//if (set.size[x] < set.size[y]) {
	//	int temp = x;
	//	x = y;
	//	y = temp;
	//}
	//// x老大，y小弟
	//set.info[y] = x;
	//set.size[x] = set.size[x] + set.size[y];
}

//打印并查集
void printSet(DisjoinSet set, int size) {
	printf("内容：[");
	int i = 0;
	for (; i < size-1; i++) {
		printf("%d,", set.info[i]);
	}
	printf("%d]\n", set.info[i]);

	printf("大小：[");
	int i = 0;
	for (; i < size - 1; i++) {
		printf("%d,", set.size[i]);
	}
	printf("%d]\n", set.size[i]);
    printf("\n");
}

5.8Kruskal算法（克鲁斯卡尔算法）

算法思想：

Kruskal算法是一种用于构建最小生成树的贪心算法。最小生成树是一个包含图中所有节点的树，且树中边的权重之和最小。Kruskal算法的主要思想是通过不断选择图中权重最小的边，并确保所选择的边不形成环，逐步构建最小生成树。
算法步骤：

1.将每个节点看作是一个独立的树（单节点树），将所有边按权重从小到大排序，创建一个小根堆即可。
2.从排序后的边集中选择权重最小的边 (u, v)。
3.如果边 (u, v) 不形成环，即节点 u 和节点 v 不在同一棵树中，将该边加入最小生成树。
4.合并节点 u 和节点 v 所在的两棵树。

其中在合并u，v到同一个树的过程中，使用了并查集来实现。

1 2 3 4 5 6 7 999

1 2 2

1 3 4

1 4 1

2 4 3

2 5 10

3 4 2

3 6 5

4 5 7

4 6 8

4 7 4

5 7 6

6 7 1

0 0 0

核心代码

//kruskal（最小生成树算法）
void kruskal(Graph G, MinHeap* heap, DisjoinSet& set, int size) {
	int i = 0;
	Edge* edges = (Edge*)malloc(sizeof(Edge));

	while (i < size - 1) {
		Edge* cur = poll(heap);
		int u = find2(set, cur->start);
		int v = find2(set, cur->end);
		if (u != v) {
			edges[i] = *cur;
			unions2(set, u, v);
			i++;
		}
	}
	for (int j = 0; j < i; j++) {
		VertexType x = G.Vex[edges[j].start];
		VertexType y = G.Vex[edges[j].end];
		printf("%d->%d(%d)\n", x, y, edges[j].weight);
	}
}

全部可执行代码见源文件

运行结果

5.9Prim算法

bool set[MAXSIZE] = { false };//记录已求得的最短路径的顶点
int dist[MAXSIZE] = { INF };//记录了从源点start到其他各顶点当前的最短路径长度

VertexType path[MAXSIZE];
void prim(Graph G, VertexType start) {
	int index = verIsExist(G, start);
	set[index] = true;
	for (int i = 0; i < G.verNum; i++) {
		dist[i] = G.Edge[index][i];
		if (dist[i] < INF) {
			path[i] = start;
		}
		else {
			path[i] = -1;
		}
	}
	for (int i = 1; i < G.verNum; i++) {
		int min = INF;
		int minIndex;
		for (int w = 0; w < G.verNum; w++) {
			if (!set[w] && dist[w] < min) {
				min = dist[w];
				minIndex = w;
			}
		}
		set[minIndex] = true;
		for (int w = 0; w < G.verNum; w++) {
			if (!set[w] && G.Edge[minIndex][w] < dist[w]) {
				dist[w] = G.Edge[minIndex][w];
				path[w] = G.Vex[minIndex];
			}
		}
	}
}

5.10拓扑排序

//拓扑排序

void topologicalSort(Graph& G) {
	Queue Q;
	initQueue(Q);
	int degree[10] = { 0 };
	for (int i = 0; i < G.verNum; i++) {
		int deg = inDegree(G, G.Vex[i]);
		degree[i] = deg;
		if (deg == 0) {
			enQueue(Q, G.Vex[i]);	
		}
	}
	while (!isEmpty(Q)) {
		VertexType x = deQueue(Q);
		printf("%d->", x);
		int v = verIsExist(G, x);
		for (int i = 0; i < G.verNum; i++) {
			if (G.Edge[v][i] != 0 && G.Edge[v][i] != INF) {
				degree[i]--;
				if (degree[i] == 0) {
					enQueue(Q, G.Vex[i]);
				}
			}
		}
	}
}

//题目判断有向图是否带环,如果带环返回true否则返回false

bool Circule2(Graph& G) {
	Queue Q;
	initQueue(Q);
	int degree[10] = { 0 };
	for (int i = 0; i < G.verNum; i++) {
		int deg = inDegree(G, G.Vex[i]);
		degree[i] = deg;
		if (deg == 0) {
			enQueue(Q, G.Vex[i]);
		}
	}
	int size = 0;
	while (!isEmpty(Q)) {
		VertexType x = deQueue(Q);
		size++;
		int v = verIsExist(G, x);
		for (int i = 0; i < G.verNum; i++) {
			if (G.Edge[v][i] != 0 && G.Edge[v][i] != INF) {
				degree[i]--;
				if (degree[i] == 0) {
					enQueue(Q, G.Vex[i]);
				}
			}
		}
	}
	return size != G.verNum ?true : false;
}

5.11刷题

1.写出从图的邻接矩阵表示转换成邻接表表示的算法。

//初始化图
void InitGraph(Graph2& G){
	for (int i = 0; i < MAXSIZE; i++) {
		G.vertices[i].data = 0;
		G.vertices[i].first = NULL;
	}
	G.arcNum = 0;
	G.vexNum = 0;
}
//核心代码
void adjacencyMatrix(Graph& G,Graph2 &G2) {
	for (int i = 0; i < G.verNum; i++) {
		G2.vertices[i].data = G.Vex[i];
	}
	G2.vexNum = G.verNum;
	for (int i = 0; i < G.verNum; i++) {
		ArcNode* tail = (ArcNode*)malloc(sizeof(ArcNode));
		for (int j = 0; j < G.verNum; j++) {
			if (G.Edge[i][j] != 0 && G.Edge[i][j] != INF) {
				G2.arcNum++;
				ArcNode* node = (ArcNode*)malloc(sizeof(ArcNode));
				node->weight = G.Edge[i][j];
				node->adjVex = G.Vex[j];
				node->next = NULL;
				if (G2.vertices[i].first == NULL) {
					G2.vertices[i].first = node;
				}
				else {
					tail->next = node;
					
				}
				tail = node;
			}
		}
	}
	G2.arcNum /= 2;	//无向图可以让边数/2
}
//打印测试
void printGraph2(Graph2 G) {
	printf("图G的邻接表存储：\n");
	for (int i = 0; i < G.vexNum; i++) {
		printf("%d：", G.vertices[i].data);
		ArcNode* cur = G.vertices[i].first;
		while (cur) {
			printf("(%d,%d)->", cur->adjVex,cur->weight);
			cur = cur->next;
		}
		printf("\n");
	}
}

#define MAXSIZE 16		//图的最大顶点个数
typedef int VertexType;	//顶点类型
typedef int EdgeType;	//边类型

typedef struct {
	VertexType Vex[MAXSIZE];		//图的顶点集
	EdgeType Edge[MAXSIZE][MAXSIZE];	//图的边集
	int verNum;		//实际顶点的数量
	int edgeNum;	//实际边的数量
}Graph;

//边表结点
typedef struct ArcNode {
	int adjVex;		//理解成顶点的data域
	int weight;		//权重
	ArcNode* next;	//指向下一个边表中的结点
}ArcNode;
//顶点表
typedef struct VNode {
	VertexType data;	//顶点信息
	ArcNode* first;		//指向边表
}VNode, adjList[MAXSIZE];

//图的邻接表存储
typedef struct {
	adjList vertices;	//邻接表
	//VNode vertices[MAXSIZE];
	int vexNum;		//顶点数
	int arcNum;		//边数
}Graph2;

2.判断G是否存在EL路径

int IsExistEL(Graph G) {
	int count = 0;
	for (int i = 0; i < G.verNum; i++) {
		int degree = 0;
		for (int j = 0; j < G.verNum; j++) {
			if (G.Edge[i][j] != 0 && G.Edge[i][j] != INF) {
				degree++;
			}	
		}
		if (degree % 2 != 0) {
			count++;
		}
	}
	if (count == 0 || count == 2) {
		return 1;
	}
	else {
		return 0;
	}
}

3.求K顶点

int printVertices(Graph G) {
	int count = 0;
	for (int i = 0; i < G.numVertices; i++) {
		int indegree = 0;
		int outdegree = 0;
		for (int j = 0; j < G.numVertices; j++) {
			if (G.Edge[i][j] != 0 && G.Edge[i][j] != INF) {
				outdegree++;
			}
		}
		for (int j = 0; j < G.numVertices; j++) {
			if (G.Edge[j][i] != 0 && G.Edge[j][i] != INF) {
				indegree++;
			}
		}
		if (outdegree > indegree) {
			printf("%d ", G.VerticesList[i]);
			count++;
		}
		printf("\n");
	}
	return count;
}

4.已知无向图G=(V, E)，给出求图G的连通分量个数的算法.(邻接表存储)

//从起始顶点start开始对图G进行深度优先遍历（递归）
bool visit[MAXSIZE] = { false };
void dfs(Graph G, VertexType start) {
	visit[verIsExist(G, start)] = true;
	printf("%d ", start);
	VertexType neigbhors[MAXSIZE];
	findAllNeighbors(G, start, neigbhors);
	for (int i = 0; i < outDegree(G, start); i++) {
		if (!visit[verIsExist(G, neigbhors[i])]) {
			dfs(G, neigbhors[i]);
		}
	}
}

///已知无向图G=(V, E)，给出求图G的连通分量个数的算法.(邻接表存储)
int countConnectedComponents(Graph G) {
	int count = 0;
	// 从未访问的顶点开始进行深度优先搜索
	for (int i = 0; i < G.vexNum; i++) {
		if (!visit[i]) {
			dfs(G, G.vertices[i].data);
			count++;
		}
	}
	return count;
}

5.试设计一个算法，判断一个无向图G是否为一棵树。（邻接表存储）

///已知无向图G=(V, E)，给出求图G的连通分量个数的算法.(邻接表存储)
int countConnectedComponents(Graph G) {
	int count = 0;

	for (int i = 0; i < G.vexNum; i++) {
		if (!visit[i]) {
			dfs(G, G.vertices[i].data);
			count++;
		}
	}
	return count;
}
//统计图G的边数
int getEdgesCount(Graph G) {
	int count = 0;
	for (int i = 0; i < G.vexNum; i++) {
		ArcNode* cur = G.vertices[i].first;
		while (cur) {
			count++;
			cur = cur->next;
		}
	}
	return count / 2;
}

//判断无向图是否为树
bool isTree(Graph G) {
	if (G.vexNum - 1 != getEdgesCount(G)) {
		return false;
	}
	return countConnectedComponents(G) == 1;
}

6.分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是
否存在由顶点vi到顶点vj的路径(i ≠j)。注意，算法中涉及的图的基本操作必须在此
存储结构上实现。

bool visit[MAXSIZE] = { false };
bool result = false;
void dfs(Graph G, VertexType start,VertexType end) {
	visit[verIsExist(G, start)] = true;
	if (start == end) {
		result = true;
		return;
	}
	VertexType neigbhors[MAXSIZE];
	findAllNeighbors(G, start, neigbhors);
	for (int i = 0; i < outDegree(G, start); i++) {
		if (!visit[verIsExist(G, neigbhors[i])]) {
			dfs(G, neigbhors[i],end);
		}
	}
}
//深度优先
bool hasPathDFS(Graph G, VertexType start, VertexType end) {
	dfs(G, start, end);
	return result;
}

//广度优先遍历
bool hasPathBFS(Graph G, VertexType start, VertexType end) {
	Queue Q;
	initQueue(Q);
	bool visited[MAXSIZE] = { false };
	enQueue(Q, start);
	visited[verIsExist(G, start)] = true;
	while (!isEmpty(Q)) {
		VertexType poll = deQueue(Q);
		printf("%d ", poll);
		VertexType neigbs[MAXSIZE];
		findAllNeighbors(G, poll, neigbs);
		for (int i = 0; i < outDegree(G, poll); i++) {
			if (visited[verIsExist(G, neigbs[i])] == false) {
				enQueue(Q, neigbs[i]);
				visited[verIsExist(G, neigbs[i])] = true;
				if (end == neigbs[i]) {
					return true;
				}
			}
		}
	}
	return false;
}

6.假设图用邻接表表示，设计一个算法，输出从顶点Vi到顶点Vj的所有简单路径。

// 输出路径
void printPath(VertexType path[], int pathlen) {
	for (int i = 0; i < pathlen; i++) {
		printf("%d ", path[i]);
		if (i != pathlen - 1) {
			printf("-> ");
		}
	}
	printf("\n");
}

void dfs5(Graph G, VertexType start, VertexType end, VertexType path[], int pathLen) {
	visit[verIsExist(G, start)] = true;
	path[pathLen++] = start;
	if (start == end) {
		printPath(path, pathLen);
	}
	else {
		VertexType neigbhors[MAXSIZE];
		findAllNeighbors(G, start, neigbhors);
		for (int i = 0; i < outDegree(G, start); i++) {
			if (!visit[verIsExist(G, neigbhors[i])]) {
				dfs5(G, neigbhors[i], end, path, pathLen);
			}
		}
	}
	visit[verIsExist(G, start)] = false;
	pathLen--;
}

void printAllPaths(Graph G, VertexType start, VertexType end) {
	VertexType path[MAXSIZE];
	dfs5(G, start, end, path, 0);
}

7.删除邻接矩阵存储的图中的顶点和边

#define MAXSIZE 16		//图的最大顶点个数
typedef int VertexType;	//顶点类型
typedef int EdgeType;	//边类型
typedef struct Graph {
	VertexType Vex[MAXSIZE];		//图的顶点集
	bool isDelete[MAXSIZE] = { false };			//是否被删除了
	EdgeType Edge[MAXSIZE][MAXSIZE];	//图的边集
	int verNum;		//实际顶点的数量
	int edgeNum;	//实际边的数量
}Graph;
int DeleteNode(Graph& G, VertexType e) {
	int index = verIsExist(G, e);
	if (index == -1) {
		return 0;	///无e顶点删除失败
	}
	// 删除与顶点 e 相关联的边
	for (int i = 0; i < G.verNum; i++) {
		if (G.Edge[index][i] != 0 && G.Edge[index][i]!=INF) {
			G.Edge[index][i] = 0;
			G.Edge[i][index] = 0; // 无向图，需要删除对称位置的边
		}
	}
	//标记当前顶点已经删除，不然需要大量移动
	G.isDelete[index] = true;
	return 1;
}

int DeleteEdge(Graph& G, VertexType a, VertexType b) {
	// 获取顶点 a 和顶点 b 的编号
	int indexA = verIsExist(G, a);
	int indexB = verIsExist(G, b);
	if (indexA == -1 || indexB == -1) {
		// 如果顶点 a 或顶点 b 不存在，返回错误代码
		return 0;
	}

	// 删除边
	G.Edge[indexA][indexB] = 0;
	G.Edge[indexB][indexA] = 0; // 无向图，需要删除对称位置的边

	return 1; // 返回成功删除边的代码
}

9.编写程序判断一个用邻接表存储的有向图是否存在回路


// 深度优先搜索，检测环路
bool dfs6(Graph G, VertexType start) {
	Stack S;
	initStack(S);
	bool visited[MAXSIZE] = { false };//用来表示顶点是否访问过了
	push(S, start);
	printf("%d ", start);
	visited[verIsExist(G, start)] = true;
	while (!isEmpty(S)) {
		VertexType poll = pop(S);
		VertexType neigbhors[MAXSIZE];
		findAllNeighbors(G, poll, neigbhors);	//拿到出栈结点的所有邻居结点
		for (int i = 0; i < outDegree(G, poll); i++) {
			if (neigbhors[i] == start) {
				return true;
			}
			if (!visited[verIsExist(G, neigbhors[i])]) {
				push(S, poll);
				push(S, neigbhors[i]);
				printf("%d ", neigbhors[i]);
				visited[verIsExist(G, neigbhors[i])] = true;
				break;
			}
		}
	}
	return false;
}

// 判断有向图是否存在回路
bool hasCycle(Graph& G) {
	for (int i = 0; i < G.vexNum; i++) {
		if (dfs6(G, G.vertices[i].data)) {
			return true;
		}
	}
	return false;
}

10.从根到叶子的最大距离称为树的半径。给定一个无向连通图，写一个算法以找出半径最小
的生成树半径。[东北大学2003五(10 分)]

//从起始顶点start开始对图G进行广度优先遍历
int bfs2(Graph G, VertexType start) {
	Queue Q;
	initQueue(Q);
	bool visited[MAXSIZE] = { false };
	enQueue(Q, start);
	visited[verIsExist(G, start)] = true;
	int count = -1;
	while (!isEmpty(Q)) {
		int size = Q.size;
		for (int i = 0; i < size; i++) {
			VertexType poll = deQueue(Q);
			//printf("%d ", poll);
			VertexType neigbs[MAXSIZE];
			findAllNeighbors(G, poll, neigbs);
			for (int i = 0; i < outDegree(G, poll); i++) {
				if (visited[verIsExist(G, neigbs[i])] == false) {
					enQueue(Q, neigbs[i]);
					visited[verIsExist(G, neigbs[i])] = true;
				}
			}
		}
		count++;
	}
	return count;
}
int getmin(int a, int b) {
	return a <= b ? a : b;
}
int getMinTreeHigh(Graph G) {
	int min = 32767;
	for (int i = 0; i < G.vexNum; i++) {
		min = getmin(min, bfs2(G, G.vertices[i].data));
		//printf("%d, %d\n", G.vertices[i].data, bfs2(G, G.vertices[i].data));
	}
	return min;
}

标签：VertexType,start,int,++,算法,printf,顶点,数据结构,408
From： https://www.cnblogs.com/lingchuanfeng/p/18328808

第五章图

5.1图的邻接矩阵存储

5.2图的邻接表存储

5.3图的广度优先遍历

5.4图的深度优先遍历

5.5单源最短路径（Dijkstra）不能解决带负权边问题

5.6 多源最短路径（Floyd）

5.7 并查集

5.8Kruskal算法（克鲁斯卡尔算法）

5.9Prim算法

5.10拓扑排序

5.11刷题

相关文章

赞助商

阅读排行

408 数据结构图算法

第五章 图

5.1图的邻接矩阵存储

5.2图的邻接表存储

5.3图的广度优先遍历

5.4图的深度优先遍历

5.5单源最短路径（Dijkstra）不能解决带负权边问题

5.6 多源最短路径（Floyd）

5.7 并查集

5.8Kruskal算法（克鲁斯卡尔算法）

5.9Prim算法

5.10拓扑排序

5.11刷题

相关文章

赞助商

阅读排行

第五章图