[数据结构与算法]数据结构-图的实现以及基础算法-C语言实现

0.?必要的说明

• 由于是用C语言编写并且图这一章中代码复用性很强，所以在写的时候都是建立工程分文件来写的，考虑一部分同学的特殊需要，笔者重新组织了所有的源文件(xxx.c)和头文件(xxx.h)，并成为一个源文件，方便大家利用。最后考虑到在进行编译源文件和链接到相关的函数、变量以及声明时的顺序被无意打乱，程序可能跑不过，这种情况按下面红字操作。
• 有需要查看工程文件的伙伴可以点击这里进入代码仓库下载。
• 如果你的编译器是VS2019或者以往版本，那么你只需要复制一份代码到你的VS2019上再按下Fn + F5即可；如果你的编译器是CodeBlocks或者Dev C++等等其他的，那么你需要将每一个程序的第一行代码#define _CRT_SECURE_NO_WARNINGS 1删除后再将代码复制到你的编译器上运行。
• 你的支持和鼓励是我创作的最大动力😉！

1.?图的实现

?1.1?图的邻接矩阵实现

#define _CRT_SECURE_NO_WARNINGS 1

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

// 图的结点的数据类型为Char
typedef char VertexDataType;
// 边的权值类型为Int
typedef int EdgeWeightDataType;

typedef struct {
	VertexDataType* setsOfVertex; // 一维数组存储顶点的值
	EdgeWeightDataType** AdjacencyMatrix; // 二维数组表示邻接矩阵
	int numsOfVertex; // 顶点的个数
	int numsOfEdge;  // 边的条数
	int MaxSizeCnt; // 限制顶点的最大个数
}MatrixGraph; // 邻接矩阵表示图的结构

void InitGraph(MatrixGraph* Graph, int n); // 初始化图的结构

void InsertVertex(MatrixGraph* Graph, VertexDataType vertex); // 在图中插入顶点

void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight); // 添加顶点间的联系

void ShowMatrix(MatrixGraph* Graph); // 显示图的邻接矩阵表示

int main() {

	MatrixGraph graph;
	InitGraph(&graph, 5);
	// 添加顶点
	InsertVertex(&graph, 'A'); // index 0
	InsertVertex(&graph, 'B'); // index 1
	InsertVertex(&graph, 'C'); // index 2
	InsertVertex(&graph, 'D'); // index 3
	InsertVertex(&graph, 'E'); // index 4
	// 添加顶点间的关系
	InsertEdge(&graph, 0, 1, 1);
	InsertEdge(&graph, 0, 3, 1);
	InsertEdge(&graph, 1, 2, 1);
	InsertEdge(&graph, 1, 4, 1);
	InsertEdge(&graph, 2, 3, 1);
	InsertEdge(&graph, 2, 4, 1);

	// 展示无向图的邻接矩阵
	ShowMatrix(&graph);
	return 0;
}

// 初始化图的结构
void InitGraph(MatrixGraph* Graph, int n) {
	Graph->setsOfVertex = (VertexDataType*)malloc(sizeof(VertexDataType) * n);
	Graph->AdjacencyMatrix = (EdgeWeightDataType**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++) {
		Graph->AdjacencyMatrix[i] = (EdgeWeightDataType*)malloc(sizeof(EdgeWeightDataType) * n);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			Graph->AdjacencyMatrix[i][j] = 0;
		}
	}
	Graph->numsOfEdge = 0;
	Graph->numsOfVertex = 0;
	Graph->MaxSizeCnt = n;
}

// 在图中插入顶点
void InsertVertex(MatrixGraph* Graph, VertexDataType vertex) {
	if (Graph->numsOfVertex <= Graph->MaxSizeCnt) {
		Graph->setsOfVertex[Graph->numsOfEdge] = vertex;
		Graph->numsOfVertex++;
	}
}

// 添加顶点间的联系
void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight) {
	Graph->AdjacencyMatrix[v1][v2] = weight;
	Graph->AdjacencyMatrix[v2][v1] = weight;
	Graph->numsOfEdge++;
}

// 显示图的邻接矩阵表示
void ShowMatrix(MatrixGraph* Graph) {
	printf("\n\n\n");
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		printf("       [ ");
		for (int j = 0; j < Graph->numsOfVertex; j++) {
			if (j != Graph->numsOfVertex - 1) {
				printf("%d ", Graph->AdjacencyMatrix[i][j]);
			}
			else {
				printf("%d ", Graph->AdjacencyMatrix[i][j]);
			}
		}
		printf("]");
		printf("\n");
	}
}

?1.2?图的邻接表实现

#define _CRT_SECURE_NO_WARNINGS 1
#define MAX_VERTEXNUMS 70 // 最大顶点个数
#include <stdio.h>
#include <stdlib.h>

typedef char VertexDataType; // 顶点所储存数据的类型
typedef int EdgeWeightDataType; // 边的权值类型

// 边结点(的结构)
typedef struct GraphEdgeNode {
	int adjVertexIndex; // 邻接结点的索引
	struct GraphEdgeNode* p_nextEdge; // 下一条边的地址
	EdgeWeightDataType infoOfEdge; // 边的信息
}EdgeNode;

// 顶点(的结构)
typedef struct GraphVertexNode {
	VertexDataType val;
	EdgeNode* p_firstAdjEdge; // 指向第一条邻接该顶点的边
}VertexNode;

// 邻接表所表示的图所包含的信息
typedef struct {
	VertexNode* setsOfVertex; // 每个顶点所表示的关系表
	int vertexNums; // 图中顶点数
	int edgeNums;  // 图中所存在的关系(边)的个数
}ALGraph;

void BuildALGraph(ALGraph* graph); // 采用邻接表法构建无向图

int SearchVertexRetIndex(ALGraph* graph, VertexDataType val); // 在图中寻找值为val的顶点的索引

void showALGraph(ALGraph* graph); // 显示邻接表中的信息

#define _CRT_SECURE_NO_WARNINGS 1

#include "GraphOperationsStatement.h"

int main() {
	ALGraph graph;
	BuildALGraph(&graph);
	showALGraph(&graph);
	return 0;
}

// 采用邻接表法构建无向图
void BuildALGraph(ALGraph* graph) {
	graph->setsOfVertex = (VertexNode*)malloc(sizeof(VertexNode) * MAX_VERTEXNUMS);

	int vertexNums = 0;
	int edgeNums = 0;
	printf("分别输入顶点和边的个数(num1 num2):\n");
	scanf("%d %d", &vertexNums, &edgeNums);
	getchar();

	graph->vertexNums = vertexNums;
	graph->edgeNums = edgeNums;

	// 输入图中各个顶点的信息
	for (int i = 0; i < graph->vertexNums; i++) {
		printf("输入第%d个顶点的信息：\n", i + 1);
		scanf("%c", &(graph->setsOfVertex[i].val));
		getchar();
		graph->setsOfVertex[i].p_firstAdjEdge = NULL;
	}

	// 输入各个边，构建邻接表
	VertexDataType v1 = 0;
	VertexDataType v2 = 0;
	int v1Index = 0;
	int v2Index = 0;
	for (int i = 0; i < graph->edgeNums; i++) {
		printf("输入第%d条边所依附的两个结点：\n", i + 1);
		scanf("%c", &v1);
		getchar();
		scanf("%c", &v2);
		getchar();

		v1Index = SearchVertexRetIndex(graph, v1);
		v2Index = SearchVertexRetIndex(graph, v2);

		EdgeNode* newEdgeNode0 = (EdgeNode*)malloc(sizeof(EdgeNode));
		newEdgeNode0->adjVertexIndex = v2Index;
		newEdgeNode0->p_nextEdge = graph->setsOfVertex[v1Index].p_firstAdjEdge;
		graph->setsOfVertex[v1Index].p_firstAdjEdge = newEdgeNode0;

		EdgeNode* newEdgeNode1 = (EdgeNode*)malloc(sizeof(EdgeNode));
		newEdgeNode1->adjVertexIndex = v1Index;
		newEdgeNode1->p_nextEdge = graph->setsOfVertex[v2Index].p_firstAdjEdge;
		graph->setsOfVertex[v2Index].p_firstAdjEdge = newEdgeNode1;
	}
}

// 在图中寻找值为val的顶点的索引
int SearchVertexRetIndex(ALGraph* graph, VertexDataType val) {

	for (int i = 0; i < graph->vertexNums; i++) {
		if (graph->setsOfVertex[i].val == val) {
			return i;
		}
	}

	return -1;
}

// 显示邻接表中的信息
void showALGraph(ALGraph* graph) {
	EdgeNode* cur = NULL;
	printf("\n");
	for (int i = 0; i < graph->vertexNums; i++) {
		printf("%c->", graph->setsOfVertex[i].val);
		cur = graph->setsOfVertex[i].p_firstAdjEdge;
		while (cur != NULL) {
			printf("%d->", cur->adjVertexIndex);
			cur = cur->p_nextEdge;
		}
		printf("NULL\n");
	}
}

2.?图的基础算法

?2.1?图的深度优先遍历

#define _CRT_SECURE_NO_WARNINGS 1
#define MAX_SIZEOFVERTEX 70

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

typedef int VertexDataType; // 顶点所储存数据的类型
typedef int EdgeWeightDataType; // 边的权值类型

// 边结点(的结构)
typedef struct GraphEdgeNode {
	int adjVertexIndex; // 邻接结点的索引
	struct GraphEdgeNode* p_nextEdge; // 下一条边的地址
	EdgeWeightDataType infoOfEdge; // 边的信息
}EdgeNode;

// 顶点(的结构)
typedef struct GraphVertexNode {
	VertexDataType val;
	EdgeNode* p_firstAdjEdge; // 指向第一条邻接该顶点的边
}VertexNode;

// 邻接表所表示的图所包含的信息
typedef struct {
	VertexNode* setsOfVertex; // 每个顶点所表示的关系表
	int vertexNums; // 图中顶点数
	int edgeNums;  // 图中所存在的关系(边)的个数
	int* visited; // 图中顶点是否被访问过的的标志数组
}ALGraph;

void InitALGraph(ALGraph* graph); // 初始化无向图

void InsertVertex(ALGraph* graph, VertexDataType val); // 插入值为val的顶点

void InsertEdge(ALGraph* graph, VertexDataType val_1, VertexDataType val_2); // 插入依附顶点val1和val2的边

int SearchVertexRetIndex(ALGraph* graph, VertexDataType val); // 在图中寻找值为val的顶点的索引

void showALGraph(ALGraph* graph); // 显示邻接表中的信息

void DFS_AL(ALGraph* graph, int StartVertexIndex); // 对无向图进行深度优先遍历

int main() {
	ALGraph graph;
	InitALGraph(&graph);

	InsertVertex(&graph, 1);
	InsertVertex(&graph, 2);
	InsertVertex(&graph, 3);
	InsertVertex(&graph, 4);
	InsertVertex(&graph, 5);
	InsertVertex(&graph, 6);
	InsertVertex(&graph, 7);

	InsertEdge(&graph, 1, 3);
	InsertEdge(&graph, 1, 2);
	InsertEdge(&graph, 3, 2);
	InsertEdge(&graph, 2, 5);
	InsertEdge(&graph, 2, 4);
	InsertEdge(&graph, 5, 7);
	InsertEdge(&graph, 5, 6);
	showALGraph(&graph);

	printf("无向连通图的优先深度遍历结果：\n");
	DFS_AL(&graph, 0);
	return 0;
}

// 初始化无向图
void InitALGraph(ALGraph* graph) {
	graph->setsOfVertex = (VertexNode*)malloc(sizeof(VertexNode) * MAX_SIZEOFVERTEX );
	graph->edgeNums = 0;
	graph->vertexNums = 0;

	graph->visited = (int*)malloc(sizeof(int) * MAX_SIZEOFVERTEX );
}

// 插入值为val的顶点
void InsertVertex(ALGraph* graph, VertexDataType val) {
	graph->setsOfVertex[graph->vertexNums].val = val;
	graph->setsOfVertex[graph->vertexNums].p_firstAdjEdge = NULL;
	graph->visited[graph->vertexNums] = 0;// 初始化插入时的结点未被访问
	graph->vertexNums++;
}

// 插入依附顶点val1和val2的边
void InsertEdge(ALGraph* graph, VertexDataType val_1, VertexDataType val_2) {
	int v1Index = 0;
	int v2Index = 0;

	v1Index = SearchVertexRetIndex(graph, val_1);
	v2Index = SearchVertexRetIndex(graph, val_2);


	// 无向图需要关联到一条边所依附的两个顶点，即联系X->Y的同时，也需要联系Y->X

	// 头插结点来构建每个顶点的邻接关系

	// X->Y
	EdgeNode* newEdgeNode0 = (EdgeNode*)malloc(sizeof(EdgeNode));
	if (newEdgeNode0 == NULL) {
		exit(0);
	}
	newEdgeNode0->adjVertexIndex = v2Index;
	newEdgeNode0->p_nextEdge = graph->setsOfVertex[v1Index].p_firstAdjEdge;
	graph->setsOfVertex[v1Index].p_firstAdjEdge = newEdgeNode0;

	// Y->X
	EdgeNode* newEdgeNode1 = (EdgeNode*)malloc(sizeof(EdgeNode));
	if (newEdgeNode1 == NULL) {
		exit(0);
	}
	newEdgeNode1->adjVertexIndex = v1Index;
	newEdgeNode1->p_nextEdge = graph->setsOfVertex[v2Index].p_firstAdjEdge;
	graph->setsOfVertex[v2Index].p_firstAdjEdge = newEdgeNode1;

	graph->edgeNums++;
}

// 在图中寻找值为val的顶点的索引
int SearchVertexRetIndex(ALGraph* graph, VertexDataType val) {

	for (int i = 0; i < graph->vertexNums; i++) {
		if (graph->setsOfVertex[i].val == val) {
			return i;
		}
	}

	return -1;
}

// 显示邻接表中的信息
void showALGraph(ALGraph* graph) {
	EdgeNode* cur = NULL;
	printf("当前图的邻接表的状态：\n");
	for (int i = 0; i < graph->vertexNums; i++) {
		printf("Adjacency List[%d]: %d => ", i, graph->setsOfVertex[i].val);
		cur = graph->setsOfVertex[i].p_firstAdjEdge;
		while (cur != NULL) {
			printf("%d->", graph->setsOfVertex[cur->adjVertexIndex].val);
			cur = cur->p_nextEdge;
		}
		printf("NULL\n");
	}
}

// 对无向连通图进行深度优先遍历
void DFS_AL(ALGraph* graph, int startVertexIndex) {
	printf("%d ", graph->setsOfVertex[startVertexIndex].val);
	graph->visited[startVertexIndex] = 1;

	// 当前访问结点的第一个关联点（用边来存储信息）
	EdgeNode* cur = graph->setsOfVertex[startVertexIndex].p_firstAdjEdge;
	while (cur) {
		// 边中储存着当前顶点的邻接顶点（弧头）的索引
		int adjVertexIndex = cur->adjVertexIndex;
		if (graph->visited[adjVertexIndex] == 0) { // 判断当前顶点的邻接顶点是否被访问过
			DFS_AL(graph, adjVertexIndex);  // 没有被访问过就递归访问
		}

		cur = cur->p_nextEdge; // 访问过就判断被访问过的当前边的下一条边,即当前顶点的其他邻接顶点
	}
}

?2.2?图的广度优先遍历

#define _CRT_SECURE_NO_WARNINGS 1
#define MAX_VERTEXNUMS 70 // 最大顶点个数

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

typedef int VertexDataType; // 顶点所储存数据的类型
typedef int EdgeWeightDataType; // 边的权值类型

// 边结点(的结构)
typedef struct GraphEdgeNode {
	int adjVertexIndex; // 邻接结点的索引
	struct GraphEdgeNode* p_nextEdge; // 下一条边的地址
	EdgeWeightDataType infoOfEdge; // 边的信息
}EdgeNode;

// 顶点(的结构)
typedef struct GraphVertexNode {
	VertexDataType val;
	EdgeNode* p_firstAdjEdge; // 指向第一条邻接该顶点的边
}VertexNode;

// 邻接表所表示的图所包含的信息
typedef struct {
	VertexNode* setsOfVertex; // 每个顶点所表示的关系表
	int vertexNums; // 图中顶点数
	int edgeNums;  // 图中所存在的关系(边)的个数
	int* visited; // 图中顶点是否被访问过的的标志数组
}ALGraph;
/*---------辅助队列--------*/
typedef struct LQueueNode {
	VertexNode* val; // 队列中存放图中的顶点
	struct LQueueNode* next;
}LQueueNode;

typedef struct {
	LQueueNode* head;
	LQueueNode* tail;
}LQueue;
/*---------辅助队列--------*/

void InitALGraph(ALGraph* graph); // 初始化无向图

void InsertVertex(ALGraph* graph, VertexDataType val); // 插入值为val的顶点

void InsertEdge(ALGraph* graph, VertexDataType val_1, VertexDataType val_2); // 插入依附顶点val1和val2的边

int SearchVertexRetIndex(ALGraph* graph, VertexDataType val); // 在图中寻找值为val的顶点的索引

void showALGraph(ALGraph* graph); // 显示邻接表中的信息

void GraphBFS_AL(ALGraph* graph, int startVertexIndex); // 广度优先遍历无向连通图

void InitLQueue(LQueue* queue); // 初始化链式队列

void push(LQueue* queue, VertexNode* val); // 队列的入队操作

void pop(LQueue* queue, VertexNode* retVertex); // 队列的出队操作

int QueueEmpty(LQueue* queue); // 判断队列是否为空

int main() {
	ALGraph graph;
	InitALGraph(&graph);

	InsertVertex(&graph, 1);
	InsertVertex(&graph, 2);
	InsertVertex(&graph, 3);
	InsertVertex(&graph, 4);
	InsertVertex(&graph, 5);
	InsertVertex(&graph, 6);
	InsertVertex(&graph, 7);

	InsertEdge(&graph, 1, 3);
	InsertEdge(&graph, 1, 2);
	InsertEdge(&graph, 3, 2);
	InsertEdge(&graph, 2, 5);
	InsertEdge(&graph, 2, 4);
	InsertEdge(&graph, 5, 7);
	InsertEdge(&graph, 5, 6);
	showALGraph(&graph);
	
	GraphBFS_AL(&graph, 0);
	GraphBFS_AL(&graph, 1);
	GraphBFS_AL(&graph, 5);
	GraphBFS_AL(&graph, 3);
	GraphBFS_AL(&graph, 2);

	return 0;
}

// 初始化链式队列
void InitLQueue(LQueue* queue) {
	queue->head = (LQueueNode*)malloc(sizeof(LQueueNode));
	if (queue->head == NULL) {
		exit(0);
	}
	queue->head->next = NULL;
	queue->tail = queue->head;
}

// 队列的入队操作
void push(LQueue* queue, VertexNode* val) {
	LQueueNode* newNode = (LQueueNode*)malloc(sizeof(LQueueNode));
	if (newNode == NULL) {
		exit(0);
	}
	newNode->val = val;
	newNode->next = NULL;

	queue->tail->next = newNode;
	queue->tail = newNode;
}

// 队列的出队操作
void pop(LQueue* queue, VertexNode* retVertex) {
	if (QueueEmpty(queue)) {
		exit(0);
	}
	LQueueNode* pHead = queue->head->next;

	*retVertex = *(pHead->val);
	queue->head->next = pHead->next;
	
	if (queue->tail == pHead) {
		queue->tail = queue->head;
	}

	free(pHead);
}

// 判断队列是否为空
int QueueEmpty(LQueue* queue) {
	if (queue->head == queue->tail) {
		return 1;
	}

	return 0;
}

// 初始化无向图
void InitALGraph(ALGraph* graph) {
	graph->setsOfVertex = (VertexNode*)malloc(sizeof(VertexNode) * MAX_VERTEXNUMS);
	graph->edgeNums = 0;
	graph->vertexNums = 0;

	graph->visited = (int*)malloc(sizeof(int) * MAX_VERTEXNUMS);
}

// 插入值为val的顶点
void InsertVertex(ALGraph* graph, VertexDataType val) {
	graph->setsOfVertex[graph->vertexNums].val = val;
	graph->setsOfVertex[graph->vertexNums].p_firstAdjEdge = NULL;
	graph->visited[graph->vertexNums] = 0;// 初始化插入时的结点未被访问
	graph->vertexNums++;
}

// 在图中寻找值为val的顶点的索引
int SearchVertexRetIndex(ALGraph* graph, VertexDataType val) {

	for (int i = 0; i < graph->vertexNums; i++) {
		if (graph->setsOfVertex[i].val == val) {
			return i;
		}
	}

	return -1;
}

// 插入依附顶点val1和val2的边
void InsertEdge(ALGraph* graph, VertexDataType val_1, VertexDataType val_2) {
	int v1Index = 0;
	int v2Index = 0;

	v1Index = SearchVertexRetIndex(graph, val_1);
	v2Index = SearchVertexRetIndex(graph, val_2);

	// 无向图需要关联到一条边所依附的两个顶点，即联系X->Y的同时，也需要联系Y->X
	// 头插结点来构建每个顶点的邻接关系

	// X->Y
	EdgeNode* newEdgeNode0 = (EdgeNode*)malloc(sizeof(EdgeNode));
	if (newEdgeNode0 == NULL) {
		exit(0);
	}
	newEdgeNode0->adjVertexIndex = v2Index;
	newEdgeNode0->p_nextEdge = graph->setsOfVertex[v1Index].p_firstAdjEdge;
	graph->setsOfVertex[v1Index].p_firstAdjEdge = newEdgeNode0;

	// Y->X
	EdgeNode* newEdgeNode1 = (EdgeNode*)malloc(sizeof(EdgeNode));
	if (newEdgeNode1 == NULL) {
		exit(0);
	}
	newEdgeNode1->adjVertexIndex = v1Index;
	newEdgeNode1->p_nextEdge = graph->setsOfVertex[v2Index].p_firstAdjEdge;
	graph->setsOfVertex[v2Index].p_firstAdjEdge = newEdgeNode1;

	graph->edgeNums++;
}

// 显示邻接表中的信息
void showALGraph(ALGraph* graph) {
	EdgeNode* cur = NULL;
	printf("当前图的邻接表的状态：\n");
	for (int i = 0; i < graph->vertexNums; i++) {
		printf("Adjacency List[%d]: %d => ", i, graph->setsOfVertex[i].val);
		cur = graph->setsOfVertex[i].p_firstAdjEdge;
		while (cur != NULL) {
			printf("%d->", graph->setsOfVertex[cur->adjVertexIndex].val);
			cur = cur->p_nextEdge;
		}
		printf("NULL\n");
	}
}

// 广度优先遍历无向连通图
void GraphBFS_AL(ALGraph* graph, int startVertexIndex) {
	// 每一次调用广度优先遍历算法都要重置之前调用时被“充满”的已被访问过的标志
	memset(graph->visited, 0, MAX_VERTEXNUMS);
	printf("\n从值为%d的顶点开始广度优先遍历得结果为：", graph->setsOfVertex[startVertexIndex].val);
	LQueue queue;
	InitLQueue(&queue);
	push(&queue, &(graph->setsOfVertex[startVertexIndex].val)); // 首先将元素入队是BFS所惯用的

	VertexNode* retVal = (VertexNode*)malloc(sizeof(VertexNode));
	EdgeNode* cur = (EdgeNode*)malloc(sizeof(EdgeNode));

	while (!QueueEmpty(&queue)) {
		pop(&queue, retVal);
		if (retVal == NULL) {
			exit(0);
		}
		cur = retVal->p_firstAdjEdge; // cur 和 retVal的类型不一致 在给cur赋值时是赋上顶点表的顶点的第一条与之相联系的边的地址
		if (graph->visited[SearchVertexRetIndex(graph, retVal->val)] == 0) {
			printf("%d ", retVal->val);
			graph->visited[SearchVertexRetIndex(graph, retVal->val)] = 1; // 记录该顶点已被访问过
		}
		while (cur) {
			if (graph->visited[cur->adjVertexIndex] == 0) { // 遇到被访问过的顶点不必入栈，接着遍历下一条边
				push(&queue, &(graph->setsOfVertex[cur->adjVertexIndex].val));
			}
			
			cur = cur->p_nextEdge;
		}
	}
	free((&queue)->head);
}

?2.3?图最小生成树的Prime算法

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

// 图的结点的数据类型为Char
typedef char VertexDataType;
// 边的权值类型为Int
typedef int EdgeWeightDataType;

typedef struct {
	VertexDataType lowAdjVex; // 与最小边相邻接的顶点的值
	EdgeWeightDataType lowEdgeWeight; // 最小边的权值
}closedge;

typedef struct {
	VertexDataType* setsOfVertex; // 一维数组存储顶点的值
	EdgeWeightDataType** AdjacencyMatrix; // 二维数组表示邻接矩阵
	closedge* flag; // 标记数组
	int numsOfVertex; // 顶点的个数
	int numsOfEdge;  // 边的条数
	int MaxSizeCnt; // 限制顶点的最大个数
}MatrixGraph; // 邻接矩阵表示图的结构

void InitGraph(MatrixGraph* Graph, int n); // 初始化图的结构

void InsertVertex(MatrixGraph* Graph, VertexDataType vertex); // 在图中插入顶点

void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight); // 添加顶点间的联系

void ShowMatrix(MatrixGraph* Graph); // 显示图的邻接矩阵表示

int searchVerIndex(MatrixGraph* Graph, VertexDataType verValue); // 在邻接矩阵中寻找值为verIndex的顶点的索引

int Min(MatrixGraph* Graph); // 在辅助数组中寻找最小边，目的是添加顶点

void MST_Prim(MatrixGraph* Graph, VertexDataType vertexValue); // 借助图的邻接矩阵来实现Prim算法

int main() {
	MatrixGraph graph;
	InitGraph(&graph, 6);
	InsertVertex(&graph, 'a'); // 0
	InsertVertex(&graph, 'b'); // 1
	InsertVertex(&graph, 'c'); // 2
	InsertVertex(&graph, 'd'); // 3
	InsertVertex(&graph, 'e'); // 4
	InsertVertex(&graph, 'f'); // 5

	InsertEdge(&graph, 0, 5, 13);
	InsertEdge(&graph, 0, 1, 9);
	InsertEdge(&graph, 0, 2, 7);
	InsertEdge(&graph, 0, 3, 8);
	InsertEdge(&graph, 1, 5, 17);
	InsertEdge(&graph, 1, 4, 12);
	InsertEdge(&graph, 4, 5, 18);
	InsertEdge(&graph, 2, 4, 10);
	InsertEdge(&graph, 2, 3, 5);
	InsertEdge(&graph, 3, 4, 24);

	//ShowMatrix(&graph);
	MST_Prim(&graph, 'c');
	return 0;
}
	
// 初始化图的结构
void InitGraph(MatrixGraph* Graph, int n) {
	Graph->setsOfVertex = (VertexDataType*)malloc(sizeof(VertexDataType) * n);
	Graph->AdjacencyMatrix = (EdgeWeightDataType**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++) {
		Graph->AdjacencyMatrix[i] = (EdgeWeightDataType*)malloc(sizeof(EdgeWeightDataType) * n);
	}
	if (Graph->AdjacencyMatrix == NULL) {
		exit(0);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			Graph->AdjacencyMatrix[i][j] = 2147483647;
		}
	}

	Graph->flag = (closedge*)malloc(sizeof(closedge) * n);
	Graph->numsOfEdge = 0;
	Graph->numsOfVertex = 0;
	Graph->MaxSizeCnt = n;
}

// 在图中插入顶点
void InsertVertex(MatrixGraph* Graph, VertexDataType vertex) {
	int i = Graph->numsOfVertex;
	if (i < Graph->MaxSizeCnt) {
		Graph->setsOfVertex[i] = vertex;
		(Graph->numsOfVertex)++;
	}
}

// 添加顶点间的联系
void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight) {
	Graph->AdjacencyMatrix[v1][v2] = weight;
	Graph->AdjacencyMatrix[v2][v1] = weight;
	Graph->numsOfEdge++;
}

// 显示图的邻接矩阵表示
void ShowMatrix(MatrixGraph* Graph) {
	printf("\n\n\n");
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		printf("       [ ");
		for (int j = 0; j < Graph->numsOfVertex; j++) {
			if (j != Graph->numsOfVertex - 1) {
				printf("%02d ", Graph->AdjacencyMatrix[i][j]);
			}
			else {
				printf("%02d ", Graph->AdjacencyMatrix[i][j]);
			}
		}
		printf("]");
		printf("\n");
	}
}

// 在邻接矩阵中寻找值为verIndex的顶点的索引
int searchVerIndex(MatrixGraph* Graph, VertexDataType verValue) {
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		if (verValue == Graph->setsOfVertex[i]) {
			return i;
		}
	}

	return -1;
}

int Min(MatrixGraph* Graph) {
	int min = 100, minIndex = 0;
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		if ((Graph->flag[i].lowEdgeWeight != 0) && (Graph->flag[i].lowEdgeWeight < min)) {
			min = Graph->flag[i].lowEdgeWeight;
			minIndex = i;
		}
	}

	return minIndex;
}

// 借助图的邻接矩阵来实现Prim算法
void MST_Prim(MatrixGraph* Graph, VertexDataType vertexValue) {
	MatrixGraph retGraph;
	InitGraph(&retGraph, Graph->numsOfVertex);

	int initIndex = searchVerIndex(Graph, vertexValue);

	// 初始化flag数组，以被选择的顶点作为一个单独的集合，其他的所有点看成另外一个集合
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		InsertVertex(&retGraph, Graph->setsOfVertex[i]);
		if (i == initIndex) { // 所选择的点的到所选择的点无边，权值记为0
			Graph->flag[i].lowEdgeWeight = 0;
		}
		else {
			// 其他点到所被选择的点之间的权值由生成的邻接矩阵可得
			// 由于此时被选择的点为一个单独的集合，且当前状态只有
			// 其一个元素，所以其他点到的邻接矩阵到看作是被选择的
			// 点，因为我们要选择一条具有最权值的边，这条边是与当
			// 前被选择的点相邻接的
			Graph->flag[i].lowAdjVex = vertexValue;
			Graph->flag[i].lowEdgeWeight = Graph->AdjacencyMatrix[initIndex][i];
		} 
	}
	int weights = 0;
	for (int i = 1; i < Graph->numsOfVertex; i++) {
		int minWeightEdgeIndex = Min(Graph);

		// 与最小边相连的顶点值（from）
		VertexDataType vertex_0 = Graph->flag[minWeightEdgeIndex].lowAdjVex;
		// 所选择的最小边指向的顶点（to）
		VertexDataType vertex_1 = Graph->setsOfVertex[minWeightEdgeIndex];

		// 根据最优边得到所选择的两个顶点在图中的索引，重新加入到所要构造的最小生成树中
		int i_1 = searchVerIndex(Graph, vertex_0);
		int i_2 = searchVerIndex(Graph, vertex_1);

		// 逐步构造最小生成树
		InsertEdge(&retGraph, i_1, i_2, Graph->flag[minWeightEdgeIndex].lowEdgeWeight);
		// 累计每次选择的最优边的权值
		weights += Graph->flag[minWeightEdgeIndex].lowEdgeWeight;

		printf("The %d times two vertices selected are：%c %c\n", i, vertex_0, vertex_1);
		(Graph->flag)[minWeightEdgeIndex].lowEdgeWeight = 0;
		// 以当前选择的最小权值的边指向的顶点为基准，更新flag数组
		for (int i = 0; i < Graph->numsOfVertex; i++) {
			int edge_0 = Graph->AdjacencyMatrix[minWeightEdgeIndex][i];
			int edge_1 = Graph->flag[i].lowEdgeWeight;
			if (edge_0 < edge_1) { 
				/*              ----更新flag数组----
				 与基准作比较，如果基准值小于flag数组中储存着的到相应顶点的权值，则
				 更新flag数组中到相应的顶点的最小权值(由贪心思想可知，flag数组储存
				 的是已构造出的部分最小生成树中到未被选择的顶点的最小权值）为基准值
				 */
				(Graph->flag)[i].lowAdjVex = vertex_1;
				(Graph->flag)[i].lowEdgeWeight = edge_0;
			}
		}
	}
	printf("\n");
	// 打印最小生成树的邻接矩阵
	printf("MST generated with Prim is：\n");
	for (int i = 0; i < retGraph.numsOfVertex; i++) {
		for (int j = 0; j < retGraph.numsOfVertex; j++) {
			if (j == 0) {
				printf("\t   [");
			}
			if (retGraph.AdjacencyMatrix[i][j] == 2147483647) {
				// 不直接连通的两个点：简化其之间的权值
				printf("00 ");
			}
			else {
				printf("%02d ", retGraph.AdjacencyMatrix[i][j]);
				
			}
			if (j == retGraph.numsOfVertex - 1) {
				printf("]");
			}
			
		}
		printf("\n");
	}
	printf("Minimum Cost Spanning is: %d", weights);
}

?2.4?最小生成树的Kruskal算法

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

// 图的结点的数据类型为Char
typedef char VertexDataType;
// 边的权值类型为Int
typedef int EdgeWeightDataType;

typedef struct {
	VertexDataType head; // 边的起始点 from
	VertexDataType tail; // 边的的终点 to
	EdgeWeightDataType weight; // 边上的权值
}Edge; // 储存边的信息

typedef struct {
	VertexDataType* setsOfVertex; // 一维数组存储顶点的值
	EdgeWeightDataType** AdjacencyMatrix; // 二维数组表示邻接矩阵
	Edge* Edges; // 储存权值较小的一些边的信息
	int* vertexSet; // 每个顶点的连通分量
	int numsOfVertex; // 顶点的个数
	int numsOfEdge;  // 边的条数
	int MaxSizeCnt; // 限制顶点的最大个数
}MatrixGraph; // 邻接矩阵表示图的结构

void InitGraph(MatrixGraph* Graph, int n); // 初始化图的结构

void InsertVertex(MatrixGraph* Graph, VertexDataType vertex); // 在图中插入顶点

void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight); // 添加顶点间的联系

void ShowMatrix(MatrixGraph* Graph); // 显示图的邻接矩阵表示

int searchVerIndex(MatrixGraph* Graph, VertexDataType verValue); // 在邻接矩阵中寻找值为verIndex的顶点的索引

void sort_Edges(MatrixGraph* Graph); // 为Edge数组按边的权值大小进行从小到大排序

void Kruskal_MSTRelize(MatrixGraph* Graph); // 借助Kruskal算法构造MST

int main() {
	MatrixGraph graph;
	InitGraph(&graph, 6);
	InsertVertex(&graph, 'a'); // 0
	InsertVertex(&graph, 'b'); // 1
	InsertVertex(&graph, 'c'); // 2
	InsertVertex(&graph, 'd'); // 3
	InsertVertex(&graph, 'e'); // 4
	InsertVertex(&graph, 'f'); // 5

	InsertEdge(&graph, 0, 5, 13);
	InsertEdge(&graph, 0, 1, 9);
	InsertEdge(&graph, 0, 2, 7);
	InsertEdge(&graph, 0, 3, 8);
	InsertEdge(&graph, 1, 5, 17);
	InsertEdge(&graph, 1, 4, 12);
	InsertEdge(&graph, 4, 5, 18);
	InsertEdge(&graph, 2, 4, 10);
	InsertEdge(&graph, 2, 3, 5);
	InsertEdge(&graph, 3, 4, 24);

	Kruskal_MSTRelize(&graph);
	
	return 0;
}

// 初始化图的结构
void InitGraph(MatrixGraph* Graph, int n) {
	Graph->setsOfVertex = (VertexDataType*)malloc(sizeof(VertexDataType) * n);
	Graph->AdjacencyMatrix = (EdgeWeightDataType**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++) {
		Graph->AdjacencyMatrix[i] = (EdgeWeightDataType*)malloc(sizeof(EdgeWeightDataType) * n);
	}
	if (Graph->AdjacencyMatrix == NULL) {
		exit(0);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			Graph->AdjacencyMatrix[i][j] = 2147483647;
		}
	}

	Graph->vertexSet = (int*)malloc(sizeof(int) * n);
	Graph->Edges = (Edge*)malloc(sizeof(Edge) * n * (n - 1) / 2); // 无向图最多n * (n - 1) / 2条边
	Graph->numsOfEdge = 0;
	Graph->numsOfVertex = 0;
	Graph->MaxSizeCnt = n;
}

// 在图中插入顶点
void InsertVertex(MatrixGraph* Graph, VertexDataType vertex) {
	int i = Graph->numsOfVertex;
	Graph->setsOfVertex[i] = vertex; // 录入顶点的信息
	Graph->vertexSet[i] = i; // 开始时给每个顶点的连通分量分配为自己

	(Graph->numsOfVertex)++; // 顶点的个数增加
}

// 添加顶点间的联系
void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight) {
	Graph->AdjacencyMatrix[v1][v2] = weight;
	Graph->AdjacencyMatrix[v2][v1] = weight;
	Graph->Edges[Graph->numsOfEdge].weight = weight;
	Graph->Edges[Graph->numsOfEdge].head = Graph->setsOfVertex[v1];
	Graph->Edges[Graph->numsOfEdge].tail = Graph->setsOfVertex[v2];

	Graph->numsOfEdge++;
}

// 显示图的邻接矩阵表示
void ShowMatrix(MatrixGraph* Graph) {
	printf("\n\n\n");
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		printf("       [");
		for (int j = 0; j < Graph->numsOfVertex; j++) {
			if (j == 0) {
				if (Graph->AdjacencyMatrix[i][j] == 2147483647) printf("00 ");
				else printf("%02d ", Graph->AdjacencyMatrix[i][j]);
				continue;
			}
			if (j != Graph->numsOfVertex - 1) {
				if (Graph->AdjacencyMatrix[i][j] == 2147483647) printf("00 ");
				else printf("%02d ", Graph->AdjacencyMatrix[i][j]);
			}
			else {
				if (Graph->AdjacencyMatrix[i][j] == 2147483647) printf("00");
				else printf("%02d", Graph->AdjacencyMatrix[i][j]);
			}
		}
		printf("]");
		printf("\n");
	}
}

// 在邻接矩阵中寻找值为verIndex的顶点的索引
int searchVerIndex(MatrixGraph* Graph, VertexDataType verValue) {
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		if (verValue == Graph->setsOfVertex[i]) {
			return i;
		}
	}

	return -1;
}

// 为Edges数组按边的权值大小进行从小到大排序
void sort_Edges(MatrixGraph* Graph) {
	for (int i = 0; i < Graph->numsOfEdge - 1; i++) {
		for (int j = 0; j < Graph->numsOfEdge - i - 1; j++) {
			if (Graph->Edges[j].weight > Graph->Edges[j + 1].weight) {
				Edge tmp = Graph->Edges[j];
				Graph->Edges[j] = Graph->Edges[j + 1];
				Graph->Edges[j + 1] = tmp;
			}
		}
	}
}

// 借助Kruskal算法构造MST
void Kruskal_MSTRelize(MatrixGraph* Graph) {
	sort_Edges(Graph);

	MatrixGraph KruskalMST;
	InitGraph(&KruskalMST, Graph->numsOfVertex);

	for (int i = 0; i < Graph->numsOfVertex; i++)
		InsertVertex(&KruskalMST, Graph->setsOfVertex[i]);

	int cnt = 1;
	for (int i = 0; i < Graph->numsOfEdge; i++) {
		int v1 = searchVerIndex(Graph, Graph->Edges[i].head);
		int v2 = searchVerIndex(Graph, Graph->Edges[i].tail);

		int v1_Adj = Graph->vertexSet[v1];
		int v2_Adj = Graph->vertexSet[v2];

		if (v1_Adj != v2_Adj) {
			InsertEdge(&KruskalMST, v1, v2, Graph->Edges[i].weight);
			printf("The two vertices of the %d selected edge are: %c %c\n", cnt++ , Graph->Edges[i].head, Graph->Edges[i].tail);
			for (int j = 0; j < Graph->numsOfVertex; j++) {
				if (Graph->vertexSet[j] == v2_Adj) Graph->vertexSet[j] = v1_Adj;
			}
		}
	}

	printf("\n\nThe MST generated with the Kruskal algorithm is:\n");
	ShowMatrix(&KruskalMST);
}

?2.5?最短路径(SSSP)的Dijkstra算法

#define _CRT_SECURE_NO_WARNINGS 1
#define Override_MAX_INT 20020427
#include <stdio.h>
#include <stdlib.h>

// 图的结点的数据类型为Char
//typedef int VertexDataType;
// 边的权值类型为Int
typedef int EdgeWeightDataType;

typedef struct {
	int* setsOfVertex; // 一维数组存储顶点的值
	EdgeWeightDataType** AdjacencyMatrix; // 二维数组表示邻接矩阵
	int* flag_IsSpOfVertex; // 记录从源点到其他顶点是否已经被确定最短路径
	int* indexOfForward; // 记录源点到其他顶点的最短路径上该顶点的直接前驱
	int* spOfVertex; // 记录源点到其他顶点的最短路径的长度
	int numsOfVertex; // 顶点的个数
	int numsOfEdge;  // 边的条数
	int MaxSizeCnt; // 限制顶点的最大个数
}MatrixGraph; // 邻接矩阵表示图的结构

void InitGraph(MatrixGraph* Graph, int n); // 初始化图的结构

void InsertVertex(MatrixGraph* Graph, int vertex); // 在图中插入顶点

void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight); // 添加顶点间的联系

void ShowMatrix(MatrixGraph* Graph); // 显示图的邻接矩阵表示

void SSSP_DIJ(MatrixGraph* Graph, int v0); // DIJkstra算法解决SSSP问题

int main() {
	MatrixGraph graph;
	InitGraph(&graph, 7);
	InsertVertex(&graph, 1);
	InsertVertex(&graph, 2);
	InsertVertex(&graph, 3);
	InsertVertex(&graph, 4);
	InsertVertex(&graph, 5);
	InsertVertex(&graph, 6);
	InsertVertex(&graph, 7);

	InsertEdge(&graph, 0, 1, 13);
	InsertEdge(&graph, 0, 2, 8);
	InsertEdge(&graph, 0, 4, 30);
	InsertEdge(&graph, 0, 6, 32);
	InsertEdge(&graph, 1, 6, 7);
	InsertEdge(&graph, 1, 5, 9);
	InsertEdge(&graph, 2, 3, 5);
	InsertEdge(&graph, 3, 4, 6);
	InsertEdge(&graph, 4, 5, 2);
	InsertEdge(&graph, 5, 6, 17);

	SSSP_DIJ(&graph, 0);
	return 0;
}

// 初始化有向网的结构
void InitGraph(MatrixGraph* Graph, int n) {
	Graph->setsOfVertex = (int*)malloc(sizeof(int) * n);
	memset(Graph->setsOfVertex, 0, sizeof(int) * n);
	Graph->AdjacencyMatrix = (EdgeWeightDataType**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++) {
		Graph->AdjacencyMatrix[i] = (EdgeWeightDataType*)malloc(sizeof(EdgeWeightDataType) * n);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			Graph->AdjacencyMatrix[i][j] = Override_MAX_INT;
		}
	}

	// flag_IsSpOfVertex[i] 表示源点到索引为i的顶点是否确定了最短距离。  
	// 初始：（false --- 0）
	Graph->flag_IsSpOfVertex = (int*)malloc(sizeof(int) * n);
	memset(Graph->flag_IsSpOfVertex, 0, sizeof(int) * n);

	// indexOfForward[i] 表示源点到索引为i的顶点的最短路径上，顶点i的直接前驱 。
	// 初始：（-1）
	Graph->indexOfForward = (int*)malloc(sizeof(int) * n);
	memset(Graph->indexOfForward, -1, sizeof(int) * n);

	// spOfVertex 表示源点到其他顶点的最短路径。
	// 初始： （无穷---Override_MAX_INT） 
	Graph->spOfVertex = (int*)malloc(sizeof(int) * n);
	memset(Graph->spOfVertex, Override_MAX_INT, sizeof(int) * n);

	Graph->numsOfEdge = 0;
	Graph->numsOfVertex = 0;
	Graph->MaxSizeCnt = n;
}

// 在有向网中插入顶点
void InsertVertex(MatrixGraph* Graph, int vertex) {
		if (Graph->numsOfEdge >= Graph->MaxSizeCnt) exit(0);
		int i = Graph->numsOfVertex;
		Graph->setsOfVertex[i] = vertex;
		Graph->numsOfVertex++;
}

// 添加顶点间的联系
void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight) {
	Graph->AdjacencyMatrix[v1][v2] = weight;
	Graph->numsOfEdge++;
}

// 显示有向网的邻接矩阵
void ShowMatrix(MatrixGraph* Graph) {
	printf("\n\n\n");
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		printf("       [");
		for (int j = 0; j < Graph->numsOfVertex; j++) {
			if (j != Graph->numsOfVertex - 1) {
				if(Graph->AdjacencyMatrix[i][j] == Override_MAX_INT) printf("00 ");
				else printf("%02d ", Graph->AdjacencyMatrix[i][j]);
			}
			else {
				if (Graph->AdjacencyMatrix[i][j] == Override_MAX_INT) printf("00");
				else printf("%02d", Graph->AdjacencyMatrix[i][j]);
			}
		}
		printf("]");
		printf("\n");
	}
}

// DIJkstra算法解决SSSP问题
void SSSP_DIJ(MatrixGraph* Graph, int v0) {
	int n = Graph->numsOfVertex;

	// 初始化辅助数组	
	for (int i = 0; i < n; i++) {
		Graph->flag_IsSpOfVertex[i] = 0;
		Graph->spOfVertex[i] = Graph->AdjacencyMatrix[v0][i];

		if (Graph->spOfVertex[i] < Override_MAX_INT) Graph->indexOfForward[i] = v0;
		else Graph->indexOfForward[i] = -1;
	}

	Graph->flag_IsSpOfVertex[v0] = 1;
	Graph->spOfVertex[v0] = 0;

	// 每一次寻找当前中转点到其他顶点的最短距离，v0当作成第一次的中转点
	
	for (int i = 0; i < n; i++) {

		int minWeightEdgeDesIndex = 0;
		int min_FLag = Override_MAX_INT;
		for (int j = 0; j < n; j++) {
			if (!Graph->flag_IsSpOfVertex[j] && Graph->spOfVertex[j] < min_FLag) {
				minWeightEdgeDesIndex = j;
				min_FLag = Graph->spOfVertex[j];
			}
		}
		Graph->flag_IsSpOfVertex[minWeightEdgeDesIndex] = 1;

		for (int j = 0; j < n; j++) {
			int flag = (Graph->spOfVertex[minWeightEdgeDesIndex] + Graph->AdjacencyMatrix[minWeightEdgeDesIndex][j]) < Graph->spOfVertex[j];
			if (!Graph->flag_IsSpOfVertex[j] && flag) {
				Graph->spOfVertex[j] = Graph->spOfVertex[minWeightEdgeDesIndex] +
					Graph->AdjacencyMatrix[minWeightEdgeDesIndex][j];
				Graph->indexOfForward[j] = minWeightEdgeDesIndex;
			}
		}
	}
	// 打印出源点到每个顶点的最短距离

	for (int i = 0; i < n; i++) {
		if (i == v0) continue;
		printf("源点%d到顶点%d的最短路径为：%02d. 所选择的路径为：", Graph->setsOfVertex[i], Graph->setsOfVertex[v0], 
			Graph->spOfVertex[i]);

		int l = i;
		printf("( %d", Graph->setsOfVertex[l]);
		while (l) {
			l = Graph->indexOfForward[l];
			printf(", %d", Graph->setsOfVertex[l]);
		}
		printf(" )\n");
	}
}

?2.6?AVO-网的拓扑排序算法

#define _CRT_SECURE_NO_WARNINGS 1
#define MAX_SIZEOFVERTEX 70
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char VertexDataType; // 顶点所储存数据的类型
typedef int EdgeWeightDataType; // 边的权值类型

// 边结点(的结构)
typedef struct GraphEdgeNode {
	int adjVertexIndex; // 邻接结点的索引
	struct GraphEdgeNode* p_nextEdge; // 下一条边的地址
	EdgeWeightDataType infoOfEdge; // 边的信息
}EdgeNode;

// 顶点(的结构)
typedef struct GraphVertexNode {
	VertexDataType* val;
	EdgeNode* p_firstAdjEdge; // 指向第一条邻接该顶点的边
}VertexNode;

// 邻接表所表示的图所包含的信息
typedef struct {
	VertexNode* setsOfVertex; // 每个顶点所表示的关系表
	int vertexNums; // 图中顶点数
	int edgeNums;  // 图中所存在的关系(边)的个数
	int* indegree; // indegree[i] 表示索引为i的顶点的入度
	int* topo; // 记录拓扑排序的线性序列中顶点的索引
}ALGraph;

typedef struct SqStack {
	VertexNode* bottom; // 栈底指针
	VertexNode* top; // 栈顶指针
	int capacityOfSqStack;
}SqStack; // 辅助栈 -- 存放入度为0的顶点（集）

void BuildALGraph(ALGraph* graph); // 采用邻接表法初始化AOV-网

int SearchVertexRetIndex(ALGraph* graph, VertexDataType* val); // 在图中寻找值为val的顶点的索引

void showALGraph(ALGraph* graph); // 显示邻接表中的信息

void Topo_sort(ALGraph* graph); // 对AOV-网进行拓扑排序

void insertVertex(ALGraph* graph, VertexDataType* val); // 插入顶点

void insertEdge(ALGraph* graph, VertexDataType* from_Vertex, VertexDataType* to_Vertex, EdgeWeightDataType weight); // 插入边

void SqStackInit(SqStack* s); // 顺序栈的初始化

void SqStackPushBack(SqStack* s, VertexNode x); // 顺序栈的入栈操作

void SqStackPopBack(SqStack* s, VertexNode* retTopElem); // 顺序栈的出栈操作

int SqStackEmpty(SqStack* s); // 判断栈是否为空

int main() {
	ALGraph graph;
	BuildALGraph(&graph);
	insertVertex(&graph, "C1");
	insertVertex(&graph, "C2");
	insertVertex(&graph, "C3");
	insertVertex(&graph, "C4");
	insertVertex(&graph, "C5");
	insertVertex(&graph, "C6");
	insertVertex(&graph, "C7");
	insertVertex(&graph, "C8");
	insertVertex(&graph, "C9");
	insertVertex(&graph, "C10");
	insertVertex(&graph, "C11");
	insertVertex(&graph, "C12");

	insertEdge(&graph, "C1", "C4", 1);
	insertEdge(&graph, "C1", "C2", 1);
	insertEdge(&graph, "C1", "C3", 1);
	insertEdge(&graph, "C1", "C12", 1);
	insertEdge(&graph, "C2", "C3", 1);
	insertEdge(&graph, "C3", "C5", 1);
	insertEdge(&graph, "C3", "C7", 1);
	insertEdge(&graph, "C3", "C8", 1);
	insertEdge(&graph, "C4", "C5", 1);
	insertEdge(&graph, "C5", "C7", 1);
	insertEdge(&graph, "C9", "C12", 1);
	insertEdge(&graph, "C9", "C10", 1);
	insertEdge(&graph, "C9", "C11", 1);
	insertEdge(&graph, "C10", "C12", 1);
	insertEdge(&graph, "C11", "C6", 1);
	insertEdge(&graph, "C6", "C8", 1);
	showALGraph(&graph);

	Topo_sort(&graph);

	return 0;
}

// 采用邻接表法构建无向图
void BuildALGraph(ALGraph* graph) {
	graph->setsOfVertex = (VertexNode*)malloc(sizeof(VertexNode) * MAX_SIZEOFVERTEX);
	graph->topo = (int*)malloc(sizeof(int) * MAX_SIZEOFVERTEX);
	graph->indegree = (int*)malloc(sizeof(int) * MAX_SIZEOFVERTEX);
	memset(graph->indegree, 0, sizeof(int) * MAX_SIZEOFVERTEX);
	memset(graph->topo, 0, sizeof(int) * MAX_SIZEOFVERTEX);
	graph->edgeNums = 0;
	graph->vertexNums = 0;
}

// 在图中寻找值为val的顶点的索引
int SearchVertexRetIndex(ALGraph* graph, VertexDataType* val) {

	for (int i = 0; i < graph->vertexNums; i++) {
		if (!strcmp(graph->setsOfVertex[i].val, val)) {
			return i;
		}
	}

	return -1;
}

// 显示邻接表中的信息
void showALGraph(ALGraph* graph) {
	EdgeNode* cur = NULL;
	printf("AOV-网的邻接表：\n\n");
	for (int i = 0; i < graph->vertexNums; i++) {
		printf("	%s->", graph->setsOfVertex[i].val);
		cur = graph->setsOfVertex[i].p_firstAdjEdge;
		while (cur != NULL) {
			printf("%s->", graph->setsOfVertex[cur->adjVertexIndex].val);
			cur = cur->p_nextEdge;
		}
		printf("NULL\n");
	}
	printf("\n\n");
}

// 插入顶点
void insertVertex(ALGraph* graph, VertexDataType* val){
	int i = graph->vertexNums;
	graph->setsOfVertex[i].val = val;
	graph->setsOfVertex[i].p_firstAdjEdge = NULL;
	graph->vertexNums++;
}

// 插入边
void insertEdge(ALGraph* graph, VertexDataType* from_Vertex, VertexDataType* to_Vertex, EdgeWeightDataType weight) {
	VertexDataType* v1 = (VertexDataType*)malloc(sizeof(VertexDataType) * 3);
	VertexDataType* v2 = (VertexDataType*)malloc(sizeof(VertexDataType) * 3);
	int v1Index = 0; strcpy(v1, from_Vertex);
	int v2Index = 0; strcpy(v2, to_Vertex);

	v1Index = SearchVertexRetIndex(graph, v1);
	v2Index = SearchVertexRetIndex(graph, v2);

	EdgeNode* newEdgeNode0 = (EdgeNode*)malloc(sizeof(EdgeNode));
	newEdgeNode0->adjVertexIndex = v2Index;
	newEdgeNode0->infoOfEdge = weight;
	newEdgeNode0->p_nextEdge = graph->setsOfVertex[v1Index].p_firstAdjEdge;
	graph->setsOfVertex[v1Index].p_firstAdjEdge = newEdgeNode0;
}

// 对AOV-网进行拓扑排序
void Topo_sort(ALGraph* graph) {
	// 借助graph中的indegree数组记录每个顶点的入度
	for (int i = 0; i < graph->vertexNums; i++) {
		EdgeNode* cur = graph->setsOfVertex[i].p_firstAdjEdge;
		while (cur) {
			int j = cur->adjVertexIndex;
			graph->indegree[j]++;
			cur = cur->p_nextEdge;
		}
	}

	// 初始化辅助栈
	SqStack s;
	SqStackInit(&s);

	for (int i = 0; i < graph->vertexNums; i++) {
		if (!graph->indegree[i]) {
			SqStackPushBack(&s, graph->setsOfVertex[i]);
		}
	}

	int cnt_inputed_Vertex = 0; // 设置计数器记录已经输出的顶点数
	while (!SqStackEmpty(&s)) {
		VertexNode top_Vertex;
		SqStackPopBack(&s, &top_Vertex);

		int top_Vertex_index = SearchVertexRetIndex(graph, top_Vertex.val);
		graph->topo[cnt_inputed_Vertex] = top_Vertex_index;
		cnt_inputed_Vertex++;

		EdgeNode* p_fristAdjEdgeOfTop_vertex = top_Vertex.p_firstAdjEdge;
		while (p_fristAdjEdgeOfTop_vertex) {
			int indexOfAdjVertex = p_fristAdjEdgeOfTop_vertex->adjVertexIndex;
			graph->indegree[indexOfAdjVertex]--;
			if (graph->indegree[indexOfAdjVertex] == 0) {
				SqStackPushBack(&s, graph->setsOfVertex[indexOfAdjVertex]);
			}
			p_fristAdjEdgeOfTop_vertex = p_fristAdjEdgeOfTop_vertex->p_nextEdge;
		}
	}
	if (cnt_inputed_Vertex < graph->vertexNums) {
		printf("AOV-图中有环，无法进行拓扑排序\n");
	}
	else {
		printf("AOV-图的拓扑排序的其中一种为：\n");
		for (int i = 0; i < graph->vertexNums; i++) {
			printf("%s ", graph->setsOfVertex[graph->topo[i]]);
		}
	}
}

// 顺序栈的初始化
void SqStackInit(SqStack* s) {
	s->bottom = (VertexNode*)malloc(sizeof(VertexNode) * 70);
	if (!s->bottom) exit(0);
	s->top = s->bottom;
	s->capacityOfSqStack = 70;
}

// 顺序栈的入栈操作
void SqStackPushBack(SqStack* s, VertexNode x) {
	if (s->top - s->bottom == 70) {
		exit(0);
	}

	*(s->top) = x;
	s->top++;

}

// 顺序栈的出栈操作
void SqStackPopBack(SqStack* s, VertexNode* retTopElem) {
	if (SqStackEmpty(s)) exit(0);

	*retTopElem = *(s->top - 1);
	s->top--;
}

// 判断栈是否为空
int SqStackEmpty(SqStack* s) {
	if (s->bottom == s->top) return 1;

	return 0;
}

?2.7?AOE-网的关键路径算法

#define _CRT_SECURE_NO_WARNINGS 1
#define MAX_SIZEOFVERTEX 70
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char VertexDataType; // 顶点所储存数据的类型
typedef int EdgeWeightDataType; // 边的权值类型

// 边结点(的结构)
typedef struct GraphEdgeNode {
	int adjVertexIndex; // 邻接结点的索引
	struct GraphEdgeNode* p_nextEdge; // 下一条边的地址
	EdgeWeightDataType infoOfEdge; // 边的权值
	char* edgeTitle; // 边的标识
}EdgeNode;

// 顶点(的结构)
typedef struct GraphVertexNode {
	VertexDataType* val;
	EdgeNode* p_firstAdjEdge; // 指向第一条邻接该顶点的边
}VertexNode;

// 邻接表所表示的图所包含的信息
typedef struct {
	VertexNode* setsOfVertex; // 每个顶点所表示的关系表
	int vertexNums; // 图中顶点数
	int edgeNums;  // 图中所存在的关系(边)的个数
	int* indegree; // indegree[i] 表示索引为i的顶点的入度
	int* topo; // 记录拓扑排序的线性序列中顶点的索引
	int* happen_earliest; // happen_earliest[i] 表示索引为i的事件最早发生的时间
	int* happen_late; // happen_late[i] 表示索引为i的事件最迟发生的时间
}ALGraph;

typedef struct SqStack {
	VertexNode* bottom; // 栈底指针
	VertexNode* top; // 栈顶指针
	int capacityOfSqStack;
}SqStack; // 辅助栈 -- 存放入度为0的顶点（集）

void BuildALGraph(ALGraph* graph); // 采用邻接表法初始化AOV-网

int SearchVertexRetIndex(ALGraph* graph, VertexDataType* val); // 在图中寻找值为val的顶点的索引

void showALGraph(ALGraph* graph); // 显示邻接表中的信息

void Topo_sort(ALGraph* graph); // 对AOE-网进行拓扑排序

void CriticalPath(ALGraph* graph); // 解决AOE-网的关键路径

void insertVertex(ALGraph* graph, VertexDataType* val); // 插入顶点

void insertEdge(ALGraph* graph, VertexDataType* from_Vertex, VertexDataType* to_Vertex, EdgeWeightDataType weight, char* edgeTitle); // 插入边

void SqStackInit(SqStack* s); // 顺序栈的初始化

void SqStackPushBack(SqStack* s, VertexNode x); // 顺序栈的入栈操作

void SqStackPopBack(SqStack* s, VertexNode* retTopElem); // 顺序栈的出栈操作

int SqStackEmpty(SqStack* s); // 判断栈是否为空

int main() {
	ALGraph graph;
	BuildALGraph(&graph);

	insertVertex(&graph, "V0");
	insertVertex(&graph, "V1");
	insertVertex(&graph, "V2");
	insertVertex(&graph, "V3");
	insertVertex(&graph, "V4");
	insertVertex(&graph, "V5");
	insertVertex(&graph, "V6");
	insertVertex(&graph, "V7");
	insertVertex(&graph, "V8");

	insertEdge(&graph, "V0", "V1", 6, "a1");
	insertEdge(&graph, "V0", "V2", 4, "a2");
	insertEdge(&graph, "V0", "V3", 5, "a3");
	insertEdge(&graph, "V1", "V4", 1, "a4");
	insertEdge(&graph, "V2", "V4", 1, "a5");
	insertEdge(&graph, "V3", "V5", 2, "a6");
	insertEdge(&graph, "V4", "V6", 9, "a7");
	insertEdge(&graph, "V4", "V7", 7, "a8");
	insertEdge(&graph, "V5", "V7", 4, "a9");
	insertEdge(&graph, "V6", "V8", 2, "a10");
	insertEdge(&graph, "V7", "V8", 4, "a11");

	showALGraph(&graph);
	CriticalPath(&graph);
	return 0;
}

// 采用邻接表法构建AOE-网
void BuildALGraph(ALGraph* graph) {
	graph->setsOfVertex = (VertexNode*)malloc(sizeof(VertexNode) * MAX_SIZEOFVERTEX);
	graph->topo = (int*)malloc(sizeof(int) * MAX_SIZEOFVERTEX);
	graph->indegree = (int*)malloc(sizeof(int) * MAX_SIZEOFVERTEX);
	graph->happen_late = (int*)malloc(sizeof(int) * MAX_SIZEOFVERTEX);
	graph->happen_earliest = (int*)malloc(sizeof(int) * MAX_SIZEOFVERTEX);
	for (int i = 0; i < MAX_SIZEOFVERTEX; i++) graph->topo[i] = 0;
	for (int i = 0; i < MAX_SIZEOFVERTEX; i++) graph->indegree[i] = 0;
	for (int i = 0; i < MAX_SIZEOFVERTEX; i++) graph->happen_earliest[i] = 0;
	for (int i = 0; i < MAX_SIZEOFVERTEX; i++) graph->happen_late[i] = 0;
	graph->edgeNums = 0;
	graph->vertexNums = 0;
}

// 在图中寻找值为val的顶点的索引
int SearchVertexRetIndex(ALGraph* graph, VertexDataType* val) {

	for (int i = 0; i < graph->vertexNums; i++) {
		if (!strcmp(graph->setsOfVertex[i].val, val)) {
			return i;
		}
	}

	return -1;
}

// 显示邻接表中的信息
void showALGraph(ALGraph* graph) {
	EdgeNode* cur = NULL;
	printf("AOV-网的邻接表：\n\n");
	for (int i = 0; i < graph->vertexNums; i++) {
		printf("	%s -> ", graph->setsOfVertex[i].val);
		cur = graph->setsOfVertex[i].p_firstAdjEdge;
		while (cur != NULL) {
			printf("%s -> ", graph->setsOfVertex[cur->adjVertexIndex].val);
			cur = cur->p_nextEdge;
		}
		printf("NULL\n");
	}
	printf("\n\n");
}

// 插入顶点
void insertVertex(ALGraph* graph, VertexDataType* val) {
	int i = graph->vertexNums;
	graph->setsOfVertex[i].val = val;
	graph->setsOfVertex[i].p_firstAdjEdge = NULL;
	graph->vertexNums++;
}

// 插入边
void insertEdge(ALGraph* graph, VertexDataType* from_Vertex, VertexDataType* to_Vertex, EdgeWeightDataType weight, char* edgeTitle) {
	VertexDataType* v1 = (VertexDataType*)malloc(sizeof(VertexDataType) * 3);
	VertexDataType* v2 = (VertexDataType*)malloc(sizeof(VertexDataType) * 3);
	int v1Index = 0; strcpy(v1, from_Vertex);
	int v2Index = 0; strcpy(v2, to_Vertex);

	v1Index = SearchVertexRetIndex(graph, v1);
	v2Index = SearchVertexRetIndex(graph, v2);

	EdgeNode* newEdgeNode0 = (EdgeNode*)malloc(sizeof(EdgeNode));
	newEdgeNode0->adjVertexIndex = v2Index;
	newEdgeNode0->infoOfEdge = weight;
	newEdgeNode0->edgeTitle = edgeTitle;
	newEdgeNode0->p_nextEdge = graph->setsOfVertex[v1Index].p_firstAdjEdge;
	graph->setsOfVertex[v1Index].p_firstAdjEdge = newEdgeNode0;
}

// 对AOE-网进行拓扑排序
void Topo_sort(ALGraph* graph) {
	// 借助graph中的indegree数组记录每个顶点的入度
	for (int i = 0; i < graph->vertexNums; i++) {
		EdgeNode* cur = graph->setsOfVertex[i].p_firstAdjEdge;
		while (cur) {
			int j = cur->adjVertexIndex;
			graph->indegree[j]++;
			cur = cur->p_nextEdge;
		}
	}

	// 初始化辅助栈
	SqStack s;
	SqStackInit(&s);

	for (int i = 0; i < graph->vertexNums; i++) {
		if (!graph->indegree[i]) {
			SqStackPushBack(&s, graph->setsOfVertex[i]);
		}
	}

	int cnt_inputed_Vertex = 0; // 设置计数器记录已经输出的顶点数
	while (!SqStackEmpty(&s)) {
		VertexNode top_Vertex;
		SqStackPopBack(&s, &top_Vertex);

		int top_Vertex_index = SearchVertexRetIndex(graph, top_Vertex.val);
		graph->topo[cnt_inputed_Vertex] = top_Vertex_index;
		cnt_inputed_Vertex++;

		EdgeNode* p_fristAdjEdgeOfTop_vertex = top_Vertex.p_firstAdjEdge;
		while (p_fristAdjEdgeOfTop_vertex) {
			int indexOfAdjVertex = p_fristAdjEdgeOfTop_vertex->adjVertexIndex;
			graph->indegree[indexOfAdjVertex]--;
			if (graph->indegree[indexOfAdjVertex] == 0) {
				SqStackPushBack(&s, graph->setsOfVertex[indexOfAdjVertex]);
			}
			p_fristAdjEdgeOfTop_vertex = p_fristAdjEdgeOfTop_vertex->p_nextEdge;
		}
	}
	if (cnt_inputed_Vertex < graph->vertexNums) {
		printf("AOV-图中有环，无法进行拓扑排序\n");
		exit(0);
	}
	else {
		printf("AOV-图的拓扑排序的其中一种为：\n");
		for (int i = 0; i < graph->vertexNums; i++) {
			printf("%s ", graph->setsOfVertex[graph->topo[i]]);
		}
		printf("\n");
	}
}

// 解决AOE-网的关键路径
void CriticalPath(ALGraph* graph) {
	Topo_sort(graph);
	printf("\nAOE-网的关键路径为：\n");
	int numsOfVertex = graph->vertexNums;
	// 初始化每个事件的最早发生时间
	for (int i = 0; i < numsOfVertex; i++) {
		graph->happen_earliest[i] = 0;
	}

	// 解决每个事件的最早发生时间
	for (int i = 0; i < numsOfVertex; i++) {
		int indexOfTopoList = graph->topo[i]; // 获取拓扑序列中顶点的索引
		EdgeNode* cur = graph->setsOfVertex[indexOfTopoList].p_firstAdjEdge; // 获取每个顶点所邻接的顶点
		while (cur) {
			int adjVer_Index = cur->adjVertexIndex;
			if (graph->happen_earliest[adjVer_Index] < graph->happen_earliest[indexOfTopoList] + cur->infoOfEdge) {
				graph->happen_earliest[adjVer_Index] = graph->happen_earliest[indexOfTopoList] + cur->infoOfEdge;
			}
			cur = cur->p_nextEdge;
		}
	}

	// 初始化每个事件的最迟发生时间
	for (int i = 0; i < numsOfVertex; i++) {
		int late_times = graph->happen_earliest[numsOfVertex - 1];
		graph->happen_late[i] = late_times;
	}

	// 解决每个事件的最迟发生时间
	for (int i = numsOfVertex - 1; i >= 0; i--) {
		int indexOfTopoList = graph->topo[i];
		EdgeNode* cur = graph->setsOfVertex[indexOfTopoList].p_firstAdjEdge;
		while (cur) {
			int adjVer_index = cur->adjVertexIndex;
			if (graph->happen_late[indexOfTopoList] > graph->happen_late[adjVer_index] - cur->infoOfEdge) {
				graph->happen_late[indexOfTopoList] = graph->happen_late[adjVer_index] - cur->infoOfEdge;
			}
			cur = cur->p_nextEdge;
		}
	}
	
	// 判断哪些活动是关键活动--转化为判断活动所联系的两个事件
	printf("源点 -> ");
	for (int i = 0; i < numsOfVertex; i++) {
		EdgeNode* cur = graph->setsOfVertex[i].p_firstAdjEdge;
		while (cur) {
			int adjVerIndex = cur->adjVertexIndex;
			int e_times = graph->happen_earliest[i];
			int l_times = graph->happen_late[adjVerIndex] - cur->infoOfEdge;
			if (e_times == l_times) {
				printf("%s %s -> ", graph->setsOfVertex[i].val, graph->setsOfVertex[adjVerIndex].val);
			}
			cur = cur->p_nextEdge;
		}
	}
	printf("汇点\n");
}

// 顺序栈的初始化
void SqStackInit(SqStack* s) {
	s->bottom = (VertexNode*)malloc(sizeof(VertexNode) * 70);
	if (!s->bottom) exit(0);
	s->top = s->bottom;
	s->capacityOfSqStack = 70;
}

// 顺序栈的入栈操作
void SqStackPushBack(SqStack* s, VertexNode x) {
	if (s->top - s->bottom == 70) {
		exit(0);
	}

	*(s->top) = x;
	s->top++;

}

// 顺序栈的出栈操作
void SqStackPopBack(SqStack* s, VertexNode* retTopElem) {
	if (SqStackEmpty(s)) exit(0);

	*retTopElem = *(s->top - 1);
	s->top--;
}

// 判断栈是否为空
int SqStackEmpty(SqStack* s) {
	if (s->bottom == s->top) return 1;

	return 0;
}