数据结构-图的实现以及基础算法-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("nnn");
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("NULLn");
}
}
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("NULLn");
}
}
// 对无向连通图进行深度优先遍历
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("NULLn");
}
}
// 广度优先遍历无向连通图
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("nnn");
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 %cn", 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("nnn");
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 %cn", 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("nnThe 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("nnn");
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-网的邻接表:nn");
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("NULLn");
}
printf("nn");
}
// 插入顶点
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-网的邻接表:nn");
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("NULLn");
}
printf("nn");
}
// 插入顶点
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;
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码