数据结构之图
数据结构之图
1. 图的定义
图（Graph）G由顶点集合V(G)和边集合E(G)构成。
说明：对于n个顶点的图，对每个顶点连续编号，即顶点的编号为0～n-1。通过编号唯一确定一个顶点。
2. 图基本概念
顶点（Vertex）：在图中的数据元素，称之为顶点。
边：图中，任意两个顶点之间都可能存在关系，顶点之间的逻辑关系用边进行表示，边集可以是空的。其中：
- 无向边（Edge）：若顶点 Vi 到 Vj 之间的边没有方向，则称这条边为无向边，用无序偶对(Vi,Vj)来表示。
- 有向边/弧（Arc）：若从顶点 Vi 到 Vj 的边有方向，则称这条边为有向边，也称为弧（Arc）。
- 用有序偶 <Vi,Vj> 来表示，Vi称为弧尾（Tail），Vj称为弧头（Head）。
度（Degree）：一个顶点的边数称为度。其中：
对于无向图而言，顶点V的度是与该顶点相关联的边的数目，记作：TD(v)
对于有向图而言，顶点V的度分为 入度（箭头朝自己） 和 出度（箭头朝外）。
- 以顶点V为头的弧的数目称为V的入度（InDegree），记作：ID(v)，
- 以顶点V为尾的弧的数目称为V的出度（OutDegree），记作：OD(v)。
- 有向图顶点V的度为：TD(v)=ID(v)+OD(v)
权（Weight）：有向图的边或弧具有与其相关的数字，这种与图的边或弧相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或耗费。
邻接点（Adjacent）：相连接的两个顶点。
路径：一个顶点到另一个顶点所经过的边。路径的长度是路径上的边或弧的数目。
回路/环（Cycle）：第一个顶点到最后一个顶点相同的路径称为回路或环。
- 序列中顶点不重复出现的路径称为简单路径。
- 除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
连通（Connected）：若从顶点i到顶点j有路径，则称从顶点i到j是连通的。
子图：一个图是另一个图的一部分，则称为子图。
连通分量：无向图中的极大连通子图称为连通分量。
强连通分量：有向图中的极大强连通子图称作有向图的强连通分量。
3. 图的分类
有向图和无向图：
- 有向图（Directed Graph）： 图中的边有方向，从一个节点指向另一个节点。
- 无向图（Undirected Graph）： 图中的边没有方向，节点之间的关系是双向的。
加权图和无权图：
- 加权图（Weighted Graph）： 图中的边带有权重，表示节点之间的关系的强度或成本。
- 无权图（Unweighted Graph）： 图中的边没有权重。
稀疏图和稠密图：
- 稀疏图： 具有相对较少边的图。稀疏图的边数量远小于节点数量。
- 稠密图： 具有相对较多边的图。稠密图的边数量接近或等于节点数量的平方。
- 稀疏和稠密的判断条件是：$ e<n\log_2{n}$，其中e表示图中边（或弧）的数量，n 表示图中顶点的数量。如果式子成立，则为稀疏图；反之为稠密图。
简单图和多重图：
- 简单图（Simple Graph）： 每条边连接两个不同的节点，且没有节点与自身相连的边。
- 多重图（Multigraph）： 允许两个节点之间有多条平行的边，或者一个节点与自身相连的边。
连通图和非连通图：
- 连通图（Connected Graph）： 图中的任意两个节点之间都存在路径，即图是连通的。
- 非连通图（Disconnected Graph）： 存在至少一对节点之间没有路径的图。
4. 图的存储
4.1. 邻接矩阵表示法
邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个有n个顶点的图，则G的邻接矩阵是一个n×n的方阵，定义为：
A[i][j] =
1, 若<v_i, v_j>是G中的边
0, 否则
对于带权图来说，邻接矩阵可以定义为：
A[i][j] =
w_ij, 若<v_i, v_j>是G中的边，w_ij为该边的权值
0, 若i=j
∞, 若<v_i, v_j>不是G中的边
邻接矩阵的特点：
- 无向图的邻接矩阵是对称的
- 有向图的邻接矩阵通常是不对称的
- 适合表示稠密图
- 空间复杂度为O(n²)
4.2. 邻接表表示法
邻接表是图的一种链式存储表示方法。它是对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点v_i的边（对有向图是以v_i为尾的弧）。
邻接表的特点：
- 适合表示稀疏图
- 容易找到给定顶点的所有邻接点
- 不容易判断两个顶点之间是否有边
- 空间复杂度为O(n+e)，其中n为顶点数，e为边数
4.3. 十字链表表示法
十字链表是有向图的一种链式存储表示方法。它是邻接表和逆邻接表的结合，可以同时查找以某个顶点为尾的弧和以某个顶点为头的弧。
十字链表的特点：
- 适合有向图
- 容易找到以某个顶点为尾或为头的所有弧
- 空间复杂度为O(n+e)
4.4. 邻接多重表表示法
邻接多重表是无向图的一种链式存储表示方法。它类似于十字链表，但是针对无向图设计，每条边只有一个结点。
邻接多重表的特点：
- 适合无向图
- 容易找到与某个顶点相关的所有边
- 容易实现对边的操作
- 空间复杂度为O(n+e)
5. 图的遍历
图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
5.1. 深度优先搜索(DFS)
深度优先搜索(Depth-First Search, DFS)是一种用于遍历或搜索树或图的算法。该算法从图中的某一顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
深度优先搜索的基本思想是：
- 从起始顶点v出发，访问v；
- 选择v的一个未被访问的邻接点w，从w出发进行深度优先搜索；
- 重复上述过程，直到图中所有和v有路径相通的顶点都被访问到。
深度优先搜索通常使用栈来实现，也可以使用递归来实现。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>
#define MAX 100
typedef struct Graph
{
int arcnum; // 边数
int vexnum; // 顶点数
char vextex[MAX][20]; // 顶点信息
int matrix[MAX][MAX]; // 矩阵
// 带权:填充权值
// 无权: 0不连通，1连通
}Graph;
// 栈结构定义
typedef struct Stack
{
int data[MAX];
int top;
}Stack;
// 初始化栈
void InitStack(Stack* S)
{
S->top = -1;
}
// 判断栈是否为空
bool IsEmpty(Stack* S)
{
return S->top == -1;
}
// 入栈
void Push(Stack* S, int v)
{
if (S->top == MAX - 1) {
printf("栈已满!\n");
return;
}
S->data[++(S->top)] = v;
}
// 出栈
void Pop(Stack* S)
{
if (IsEmpty(S)) {
printf("栈为空!\n");
return;
}
(S->top)--;
}
// 获取栈顶元素
int GetTop(Stack* S)
{
if (IsEmpty(S)) {
printf("栈为空!\n");
return -1;
}
return S->data[S->top];
}
// 定位顶点
int get_pos(Graph* g, const char* v)
{
for (int i = 0; i < g->vexnum; i++)
{
if (strcmp(g->vextex[i], v) == 0)
{
return i;
}
}
return -1;
}
// 访问顶点
void visit(Graph* g, int v)
{
printf("%s ", g->vextex[v]);
}
// 深度优先搜索的递归实现
void DFS(Graph* g, int v, bool visited[])
{
// 访问顶点v
visit(g, v);
visited[v] = true;
// 遍历v的所有邻接点
for (int w = 0; w < g->vexnum; w++)
{
// 如果w是v的邻接点且未被访问
if (g->matrix[v][w] != 0 && g->matrix[v][w] != INT_MAX && !visited[w])
{
DFS(g, w, visited);
}
}
}
// 深度优先搜索的非递归实现（使用栈）
void DFS_NonRecursive(Graph* g, int v)
{
bool visited[MAX] = {false};
Stack S;
InitStack(&S);
// 访问起始顶点v
visit(g, v);
visited[v] = true;
Push(&S, v);
while (!IsEmpty(&S))
{
int v = GetTop(&S);
int w;
// 查找v的未被访问的邻接点
for (w = 0; w < g->vexnum; w++)
{
if (g->matrix[v][w] != 0 && g->matrix[v][w] != INT_MAX && !visited[w])
{
// 找到未被访问的邻接点w
visit(g, w);
visited[w] = true;
Push(&S, w);
break;
}
}
// 如果v的所有邻接点都已被访问，则将v出栈
if (w == g->vexnum)
{
Pop(&S);
}
}
}
// 深度优先遍历的入口函数
void DFSTraverse(Graph* g, int start_vertex)
{
bool visited[MAX] = {false};
printf("深度优先遍历(递归实现)结果: ");
DFS(g, start_vertex, visited);
printf("\n");
printf("深度优先遍历(非递归实现)结果: ");
DFS_NonRecursive(g, start_vertex);
printf("\n");
}
// 创建图
Graph* create_graph()
{
Graph* g = (Graph*)malloc(sizeof(Graph));
assert(g);
printf("输入边和顶点数:");
scanf_s("%d%d", &g->arcnum, &g->vexnum);
printf("输入顶点信息:");
for (int i = 0; i < g->vexnum; i++)
{
scanf_s("%s", g->vextex[i], 20);
}
for (int i = 0; i < g->vexnum; i++)
{
for (int j = 0; j < g->vexnum; j++)
{
g->matrix[i][j] = INT_MAX;
}
}
char v1[20] = "";
char v2[20] = "";
int weight = 0;
int i = 0, j = 0;
printf("输入边的信息(顶点1 顶点2 权值):\n");
for (int k = 0; k < g->arcnum; k++)
{
scanf_s("%s%s%d", v1, 20, v2, 20, &weight);
//有向图 v1-->v2 一次插入
//无向图 v1-->v2 v2-->v1 两次插入
i = get_pos(g, v1);
j = get_pos(g, v2);
if (i == -1 || j == -1)
{
printf("顶点有误!\n");
k--;
continue;
}
g->matrix[i][j] = weight;
//无向图再做一次权值填充
g->matrix[j][i] = weight;
}
return g;
}
// 打印图的邻接矩阵
void print_graph(Graph* g)
{
printf("图的邻接矩阵:\n");
for (int i = 0; i < g->vexnum; i++)
{
printf("\t%s", g->vextex[i]);
}
printf("\n");
for (int i = 0; i < g->vexnum; i++)
{
printf("%s\t", g->vextex[i]);
for (int j = 0; j < g->vexnum; j++)
{
if (g->matrix[i][j] == INT_MAX)
printf("∞\t");
else
printf("%d\t", g->matrix[i][j]);
}
printf("\n");
}
}
// 深度优先遍历示例
int main()
{
Graph* g = create_graph();
print_graph(g);
int start_vertex = 0;
printf("请输入起始顶点的索引(0-%d): ", g->vexnum - 1);
scanf_s("%d", &start_vertex);
if (start_vertex >= 0 && start_vertex < g->vexnum)
{
DFSTraverse(g, start_vertex);
}
else
{
printf("无效的顶点索引!\n");
}
free(g);
return 0;
}
/*
示例输入:
7 5
A B C D E
A B 1
A C 1
B D 1
C D 1
D E 1
B C 1
C E 1
0
示例输出:
输入边和顶点数:7 5
输入顶点信息:A B C D E
输入边的信息(顶点1 顶点2 权值):
A B 1
A C 1
B D 1
C D 1
D E 1
B C 1
C E 1
图的邻接矩阵:
A B C D E
A ∞ 1 1 ∞ ∞
B 1 ∞ 1 1 ∞
C 1 1 ∞ 1 1
D ∞ 1 1 ∞ 1
E ∞ ∞ 1 1 ∞
请输入起始顶点的索引(0-4): 0
深度优先遍历(递归实现)结果: A B C D E
深度优先遍历(非递归实现)结果: A B C D E
*/
5.2. 广度优先搜索(BFS)
广度优先搜索(Breadth-First Search, BFS)是一种用于遍历或搜索树或图的算法。该算法从图中的某一顶点v出发，访问此顶点，然后访问v的所有未被访问的邻接点，再从这些邻接点出发，访问它们的所有未被访问的邻接点，依此类推，直至图中所有和v有路径相通的顶点都被访问到。
广度优先搜索的基本思想是：
- 从起始顶点v出发，访问v；
- 访问v的所有未被访问的邻接点；
- 依次访问这些邻接点的所有未被访问的邻接点；
- 重复上述过程，直到图中所有和v有路径相通的顶点都被访问到。
广度优先搜索通常使用队列来实现。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>
#define MAX 100
typedef struct Graph
{
int arcnum; // 边数
int vexnum; // 顶点数
char vextex[MAX][20]; // 顶点信息
int matrix[MAX][MAX]; // 矩阵
// 带权:填充权值
// 无权: 0不连通，1连通
}Graph;
// 定位顶点
int get_pos(Graph* g, const char* v)
{
for (int i = 0; i < g->vexnum; i++)
{
if (strcmp(g->vextex[i], v) == 0)
{
return i;
}
}
return -1;
}
// 访问顶点
void visit(Graph* g, int v)
{
printf("%s ", g->vextex[v]);
}
// 创建图
Graph* create_graph()
{
Graph* g = (Graph*)malloc(sizeof(Graph));
assert(g);
printf("输入边和顶点数:");
scanf_s("%d%d", &g->arcnum, &g->vexnum);
printf("输入顶点信息:");
for (int i = 0; i < g->vexnum; i++)
{
scanf_s("%s", g->vextex[i], 20);
}
for (int i = 0; i < g->vexnum; i++)
{
for (int j = 0; j < g->vexnum; j++)
{
g->matrix[i][j] = INT_MAX;
}
}
char v1[20] = "";
char v2[20] = "";
int weight = 0;
int i = 0, j = 0;
printf("输入边的信息(顶点1 顶点2 权值):\n");
for (int k = 0; k < g->arcnum; k++)
{
scanf_s("%s%s%d", v1, 20, v2, 20, &weight);
//有向图 v1-->v2 一次插入
//无向图 v1-->v2 v2-->v1 两次插入
i = get_pos(g, v1);
j = get_pos(g, v2);
if (i == -1 || j == -1)
{
printf("顶点有误!\n");
k--;
continue;
}
g->matrix[i][j] = weight;
//无向图再做一次权值填充
g->matrix[j][i] = weight;
}
return g;
}
// 打印图的邻接矩阵
void print_graph(Graph* g)
{
printf("图的邻接矩阵:\n");
for (int i = 0; i < g->vexnum; i++)
{
printf("\t%s", g->vextex[i]);
}
printf("\n");
for (int i = 0; i < g->vexnum; i++)
{
printf("%s\t", g->vextex[i]);
for (int j = 0; j < g->vexnum; j++)
{
if (g->matrix[i][j] == INT_MAX)
printf("∞\t");
else
printf("%d\t", g->matrix[i][j]);
}
printf("\n");
}
}
// 队列结构定义
typedef struct Queue
{
int data[MAX];
int front;
int rear;
}Queue;
// 初始化队列
void InitQueue(Queue* Q)
{
Q->front = Q->rear = 0;
}
// 判断队列是否为空
bool IsEmpty(Queue* Q)
{
return Q->front == Q->rear;
}
// 入队
void EnQueue(Queue* Q, int v)
{
if ((Q->rear + 1) % MAX == Q->front) {
printf("队列已满!\n");
return;
}
Q->data[Q->rear] = v;
Q->rear = (Q->rear + 1) % MAX;
}
// 出队
bool DeQueue(Queue* Q, int* v)
{
if (IsEmpty(Q)) {
printf("队列为空!\n");
return false;
}
*v = Q->data[Q->front];
Q->front = (Q->front + 1) % MAX;
return true;
}
// 广度优先搜索的实现
void BFS(Graph* g, int v) {
bool visited[MAX] = { false };
Queue Q;
InitQueue(&Q);
// 访问起始顶点v
visit(g, v);
visited[v] = true;
EnQueue(&Q, v);
while (!IsEmpty(&Q)) {
int v;
DeQueue(&Q, &v);
// 遍历v的所有邻接点
for (int w = 0; w < g->vexnum; w++) {
// 如果w是v的邻接点且未被访问
if (g->matrix[v][w] != 0 && g->matrix[v][w] != INT_MAX && !visited[w]) {
visit(g, w);
visited[w] = true;
EnQueue(&Q, w);
}
}
}
}
// 广度优先遍历的入口函数
void BFSTraverse(Graph* g, int start_vertex)
{
printf("广度优先遍历结果: ");
BFS(g, start_vertex);
printf("\n");
}
// 图遍历
int main()
{
Graph* g = create_graph();
print_graph(g);
int start_vertex = 0;
printf("请输入起始顶点的索引(0-%d): ", g->vexnum - 1);
scanf_s("%d", &start_vertex);
if (start_vertex >= 0 && start_vertex < g->vexnum)
{
BFSTraverse(g, start_vertex);
}
else
{
printf("无效的顶点索引!\n");
}
free(g);
return 0;
}
/*
示例输入:
7 5
A B C D E
A B 1
A C 1
B D 1
C D 1
D E 1
B C 1
C E 1
0
示例输出:
输入边和顶点数:7 5
输入顶点信息:A B C D E
输入边的信息(顶点1 顶点2 权值):
A B 1
A C 1
B D 1
C D 1
D E 1
B C 1
C E 1
图的邻接矩阵:
A B C D E
A ∞ 1 1 ∞ ∞
B 1 ∞ 1 1 ∞
C 1 1 ∞ 1 1
D ∞ 1 1 ∞ 1
E ∞ ∞ 1 1 ∞
请输入起始顶点的索引(0-4): 0
广度优先遍历结果: A B C D E
*/
6. 图的应用算法
6.1. 最小生成树
最小生成树(Minimum Spanning Tree, MST)是一个连通无向图的生成树，其权值之和最小。
6.1.1. Prim算法
Prim算法是一种求解最小生成树的贪心算法。其基本思想是：
- 从图中任选一个顶点作为起始点，加入到最小生成树中；
- 在所有与当前最小生成树中顶点相邻的边中，选择权值最小的边，将其连接的未访问顶点加入到最小生成树中；
- 重复步骤2，直到所有顶点都加入到最小生成树中。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAX 100
typedef struct Graph
{
int arcnum; //边数
int vexnum; //顶点数
char vextex[MAX][20]; //顶点信息
int matrix[MAX][MAX]; //矩阵
//带权:填充权值
//无权: 0不连通，1连通
}Graph;
typedef struct Arc
{
int begin;
int end;
}Arc;
//定位顶点
int get_pos(Graph* g, const char* v)
{
for (int i = 0; i < g->vexnum; i++)
{
if (strcmp(g->vextex[i], v) == 0)
{
return i;
}
}
return -1;
}
// 打印最小生成树
void print_minimum_spanning_tree(Graph* g, Arc* arc, int arrayNum)
{
printf("最小生成树的边:\n");
for (int i = 0; i < arrayNum; i++)
{
printf("%s - %s\n", g->vextex[arc[i].begin], g->vextex[arc[i].end]);
}
}
// Prim算法实现
void prim(Graph* g)
{
int lowcost[MAX]; // 记录顶点与当前生成树的最小权重边的权值
int closest[MAX]; // 记录顶点与当前生成树最小权重边的顶点
Arc* arc = (Arc*)malloc(sizeof(Arc) * g->arcnum);
int count = 0;
assert(arc);
// 初始化数组
for (int i = 0; i < g->vexnum; i++)
{
//0不连通
lowcost[i] = g->matrix[0][i]; //当前顶点的所有邻接顶点权值
closest[i] = 0;
}
printf("Prim算法生成最小生成树的过程:\n");
for (int i = 1; i < g->vexnum; i++)
{
int minWeight = INT_MAX;
int k = -1;
// 选取lowcost中的最小值
for (int j = 0; j < g->vexnum; j++)
{
if (lowcost[j] > 0 && lowcost[j] < minWeight)
{
minWeight = lowcost[j];
k = j;
}
}
if (k != -1)
{
//k=1
// 输出选取的边
printf("选择边: %s - %s，权值：%d\n", g->vextex[closest[k]], g->vextex[k], minWeight);
(arc + count)->begin = closest[k]; //A
(arc + count)->end = k; //B
count++;
//lowcost[closest[k]] = -1;
lowcost[k] = -1; //标记顶点k已加入最小生成树
printf("\n");
// 更新lowcost和closest数组
for (int j = 0; j < g->vexnum; j++)
{
if (lowcost[j] != -1 && g->matrix[k][j] < lowcost[j])
{
lowcost[j] = g->matrix[k][j];
closest[j] = k;
}
}
}
}
// 打印最小生成树
print_minimum_spanning_tree(g, arc, count);
}
Graph* create_graph()
{
Graph* g = (Graph*)malloc(sizeof(Graph));
assert(g);
printf("输入边和顶点数:");
scanf_s("%d%d", &g->arcnum, &g->vexnum);
printf("输入顶点信息:");
for (int i = 0; i < g->vexnum; i++)
{
scanf_s("%s", g->vextex[i], 20);
}
//memset(g->matrix, INT_MAX, sizeof(int) * MAX * MAX);
for (int i = 0; i < g->vexnum; i++)
{
for (int j = 0; j < g->vexnum; j++)
{
g->matrix[i][j] = INT_MAX;
}
}
char v1[20] = "";
char v2[20] = "";
int weight = 0;
int i = 0, j = 0;
printf("输入边的信息:");
for (int k = 0; k < g->arcnum; k++)
{
scanf_s("%s%s%d", v1, 20, v2, 20, &weight);
//有向图 v1-->v2 一次插入
//无向图 v1-->v2 v2-->v1 两次插入
i = get_pos(g, v1);
j = get_pos(g, v2);
if (i == -1 || j == -1)
{
printf("顶点有误!\n");
k--;
continue;
}
g->matrix[i][j] = weight;
//无向图再做一次权值填充
g->matrix[j][i] = weight;
}
return g;
}
void print_graph(Graph* g)
{
for (int i = 0; i < g->vexnum; i++)
{
printf("\t%s", g->vextex[i]);
}
printf("\n");
for (int i = 0; i < g->vexnum; i++)
{
printf("%s\t", g->vextex[i]);
for (int j = 0; j < g->vexnum; j++)
{
printf("%d\t", g->matrix[i][j]);
}
printf("\n");
}
}
int main()
{
Graph* g = create_graph();
print_graph(g);
prim(g);
return 0;
}
/*
示例输入:
6 5
A B C D E
A B 6
A C 1
B C 5
B D 3
C E 6
D E 2
示例输出:
输入顶点信息:A B C D E
输入边的信息:A B 6
A C 1
B C 5
B D 3
C E 6
D E 2
A B C D E
A 2147483647 6 1 2147483647 2147483647
B 6 2147483647 5 3 2147483647
C 1 5 2147483647 2147483647 6
D 2147483647 3 2147483647 2147483647 2
E 2147483647 2147483647 6 2 2147483647
Prim算法生成最小生成树的过程:
选择边: A - C，权值：1
选择边: C - A，权值：1
选择边: C - B，权值：5
选择边: B - D，权值：3
最小生成树的边:
A - C
C - A
C - B
B - D
*/
6.1.2. Kruskal算法
Kruskal算法是另一种求解最小生成树的贪心算法。其基本思想是：
- 将图中所有边按权值从小到大排序；
- 按照权值从小到大的顺序选择边，如果该边不会与已选择的边构成环路，则将其加入到最小生成树中；
- 重复步骤2，直到选择了n-1条边（n为顶点数）。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <assert.h>
#define MAX 10
typedef struct Graph
{
int arcnum; //边数
int vexnum; //顶点数
char vextex[MAX][20]; //顶点信息
int matrix[MAX][MAX]; //矩阵
//带权:填充权值
//无权: 0不连通，1连通
}Graph;
typedef struct Arc
{
int begin;
int end;
int weight;
}Arc;
//定位顶点
int get_pos(Graph* g, const char* v)
{
for (int i = 0; i < g->vexnum; i++)
{
if (strcmp(g->vextex[i], v) == 0)
{
return i;
}
}
return -1;
}
// 打印最小生成树
void print_minimum_spanning_tree(Graph* g, Arc* arc, int arrayNum)
{
printf("最小生成树的边:\n");
for (int i = 0; i < arrayNum; i++)
{
printf("%s - %s\n", g->vextex[arc[i].begin], g->vextex[arc[i].end]);
}
}
Graph* create_graph()
{
Graph* g = (Graph*)malloc(sizeof(Graph));
assert(g);
printf("输入边和顶点数:");
scanf_s("%d%d", &g->arcnum, &g->vexnum);
printf("输入顶点信息:");
for (int i = 0; i < g->vexnum; i++)
{
scanf_s("%s", g->vextex[i], 20);
}
//memset(g->matrix, INT_MAX, sizeof(int) * MAX * MAX);
for (int i = 0; i < g->vexnum; i++)
{
for (int j = 0; j < g->vexnum; j++)
{
g->matrix[i][j] = INT_MAX;
}
}
char v1[20] = "";
char v2[20] = "";
int weight = 0;
int i = 0, j = 0;
printf("输入边的信息:");
for (int k = 0; k < g->arcnum; k++)
{
scanf_s("%s%s%d", v1, 20, v2, 20, &weight);
//有向图 v1-->v2 一次插入
//无向图 v1-->v2 v2-->v1 两次插入
i = get_pos(g, v1);
j = get_pos(g, v2);
if (i == -1 || j == -1)
{
printf("顶点有误!\n");
k--;
continue;
}
g->matrix[i][j] = weight;
//无向图再做一次权值填充
g->matrix[j][i] = weight;
}
return g;
}
void print_graph(Graph* g)
{
for (int i = 0; i < g->vexnum; i++)
{
printf("\t%s", g->vextex[i]);
}
printf("\n");
for (int i = 0; i < g->vexnum; i++)
{
printf("%s\t", g->vextex[i]);
for (int j = 0; j < g->vexnum; j++)
{
printf("%d\t", g->matrix[i][j]);
}
printf("\n");
}
}
int compare_arc(const void* a, const void* b)
{
return ((struct Arc*)a)->weight - ((struct Arc*)b)->weight;
}
void kruskal(Graph* g)
{
Arc* arc = (Arc*)malloc(sizeof(Arc) * g->arcnum * 2);
assert(arc);
int count = 0;
// 将图的所有边存入edges数组
for (int i = 0; i < g->vexnum; i++)
{
for (int j = i + 1; j < g->vexnum; j++)
{
if (g->matrix[i][j] != INT_MAX)
{
(arc + count)->begin = i;
(arc + count)->end = j;
(arc + count)->weight = g->matrix[i][j];
count++;
}
}
}
#pragma warning(disable: 6386)
// 对边按权值进行排序
qsort(arc, count, sizeof(Arc), compare_arc);
#pragma warning(default: 6386)
// 使用并查集判断是否形成环路
int* parent = (int*)malloc(sizeof(int) * g->vexnum);
assert(parent);
for (int i = 0; i < g->vexnum; i++)
{
parent[i] = i;
}
Arc* result = (Arc*)malloc(sizeof(Arc) * g->arcnum);
assert(result);
count = 0;
int i = 0;
printf("Kruskal算法生成最小生成树的过程:\n");
while (count < g->vexnum - 1)
{
int x = (arc + i)->begin;
int y = (arc + i)->end;
int root_x = x;
int root_y = y;
while (parent[root_x] != root_x)
{
root_x = parent[root_x];
}
while (parent[root_y] != root_y)
{
root_y = parent[root_y];
}
if (root_x != root_y)
{
// 没有形成环路
result[count] = arc[i];
count++;
printf("选择边: %s - %s，权值：%d\n",
g->vextex[x], g->vextex[y], arc[i].weight);
// 合并两个顶点所在的集合
parent[root_x] = root_y;
}
i++;
}
print_minimum_spanning_tree(g, result, count);
free(arc);
free(parent);
free(result);
}
/*
1 2 100
1 3 150
3 4 15
1 4 140
2 5 80
2 4 80
4 5 10
*/
int main()
{
Graph* g = create_graph();
print_graph(g);
kruskal(g);
free(g);
return 0;
}
/*
示例输入:
7 5
A B C D E
A B 6
A C 1
B C 5
B D 3
C E 6
D E 2
C D 5
示例输出:
输入边和顶点数:7 5
输入顶点信息:A B C D E
输入边的信息:A B 6
A C 1
B C 5
B D 3
C E 6
D E 2
C D 5
A B C D E
A 2147483647 6 1 2147483647 2147483647
B 6 2147483647 5 3 2147483647
C 1 5 2147483647 5 6
D 2147483647 3 5 2147483647 2
E 2147483647 2147483647 6 2 2147483647
Kruskal算法生成最小生成树的过程:
选择边: A - C，权值：1
选择边: D - E，权值：2
选择边: B - D，权值：3
选择边: C - D，权值：5
最小生成树的边:
A - C
D - E
B - D
C - D
*/
6.2. 最短路径
最短路径问题是图论中的一个经典问题，其目标是找到图中两个顶点之间的最短路径。
6.2.1. Dijkstra算法
Dijkstra算法是一种求解单源最短路径的贪心算法。其基本思想是：
- 初始化起始顶点到其他所有顶点的距离；
- 选择当前未访问的顶点中距离起始顶点最近的顶点，将其标记为已访问；
- 更新起始顶点到其他未访问顶点的距离；
- 重复步骤2和3，直到所有顶点都被访问。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define NO 0xFFFFFF //不连通
#define MAX 10 //不能直接定义太大数组
//简单描述一下图
typedef struct graph
{
char vexs[MAX]; //顶点数组
int vexnum; //顶点数
int arcnum; //边数
int matrix[MAX][MAX]; //权值数组
}GRAPH, * LPGRAPH;
void DijKstra(GRAPH map, int in, int dist[])
{
int i = 0;
int flag[MAX]; //成功获取路径的标记
int path[MAX]; //记录每个节点的前驱节点
//求出当前节点到其他节点距离
for (int i = 0; i < map.vexnum; i++)
{
flag[i] = 0;
dist[i] = map.matrix[in][i]; //当前节点到其他节点距离遍历第一行权值数组
path[i]=in;
}
flag[in] = 1;
dist[in] = 0;
int min;
int k = 0;
int j;
//2.扩充顶点
//数组存储顶点从下标0存储
for (i = 1; i < map.vexnum; i++) //i=1本质是扩充第二个顶点
{
min = NO; //不连通的值
for (j = 1; j < map.vexnum; j++)
{
if (flag[j] == 0 && dist[j] < min)
{
min = dist[j];
k = j; //连通的状态
}
}
flag[k] = 1;
for (j = 1; j < map.vexnum; j++)
{
if (flag[j] == 0 && (min + map.matrix[k][j]) < dist[j])
{
dist[j] = min + map.matrix[k][j];
path[j] = k;
}
}
}
printf("\n");
for (int i = 1; i < map.vexnum; i++)
{
printf("最短路径:(%c,%c)=%d\n", map.vexs[in], map.vexs[i], dist[i]);
// 输出最短路径经过的节点
printf("[%c", map.vexs[in]);
int prev = path[i];
while (prev != in)
{
printf("->%c", map.vexs[prev]);
prev = path[prev];
}
printf("->%c]\n", map.vexs[i]);
}
}
int main()
{
GRAPH map = { {'1','2','3','4','5'},5,7,
{
{NO,10,NO,30,100},
{NO,NO,50,NO,NO},
{NO,NO,NO,NO,10},
{NO,NO,20,NO,60},
{NO,NO,NO,NO,NO}
}
};
int in = 0; //'1'这个顶点进来，找到其他顶点距离
int dist[MAX];
DijKstra(map, in, dist);
return 0;
}
/*
示例输出:
最短路径:(1,2)=10
[1->2]
最短路径:(1,3)=50
[1->2->3]
最短路径:(1,4)=30
[1->4]
最短路径:(1,5)=60
[1->4->3->5]
*/
6.2.2. Floyd算法
Floyd算法是一种求解所有顶点对之间最短路径的动态规划算法。其基本思想是：
- 初始化距离矩阵；
- 对于每一个可能成为中间节点的顶点k，更新任意两个顶点i和j之间的最短路径；
- 重复步骤2，直到考虑了所有可能的中间节点。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define NO 0xFFFFFF //不连通
#define MAX 10 //不能直接定义太大数组
//简单描述一下图
typedef struct graph
{
char vexs[MAX]; //顶点数组
int vexnum; //顶点数
int arcnum; //边数
int matrix[MAX][MAX]; //权值数组
}GRAPH, * LPGRAPH;
void Floyd(GRAPH map, int dist[][MAX], int path[][MAX])
{
int i, j, k;
// 初始化距离矩阵和路径矩阵
for (i = 0; i < map.vexnum; i++)
{
for (j = 0; j < map.vexnum; j++)
{
dist[i][j] = map.matrix[i][j];
if (i!=j&&map.matrix[i][j] != NO)
{
path[i][j] = i;
}
else
{
path[i][j] = -1;
}
}
}
// 计算最短路径和路径矩阵
for (k = 0; k < map.vexnum; k++)
{
for (i = 0; i < map.vexnum; i++)
{
for (j = 0; j < map.vexnum; j++)
{
if (dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[k][j];
}
}
}
}
// 输出最短路径和路径矩阵
printf("\n最短路径和路径矩阵:\n");
for (i = 0; i < map.vexnum; i++)
{
for (j = 0; j < map.vexnum; j++)
{
if (dist[i][j] == NO)
{
printf("%7s ", "NO");
}
else {
printf("%7d ", dist[i][j]);
}
}
printf("\n");
}
printf("\n路径矩阵:\n");
for (i = 0; i < map.vexnum; i++)
{
for (j = 0; j < map.vexnum; j++)
{
if (path[i][j] == -1)
{
printf("%7s ", "NO");
}
else {
printf("%7d ", path[i][j]);
}
}
printf("\n");
}
}
int main()
{
GRAPH map = { {'0','1','2','3'},4,8,
{
{0,5,NO, 7},
{NO,0,4,2},
{3,3,0,2},
{NO,NO,1,0},
}
};
int distMatrix[MAX][MAX];
int pathMatrix[MAX][MAX];
Floyd(map, distMatrix, pathMatrix);
return 0;
}
/*
示例输出:
最短路径和路径矩阵:
0 5 8 7
5 0 4 2
3 3 0 2
4 4 1 0
路径矩阵:
NO 0 1 0
2 NO 1 1
0 0 NO 2
2 2 2 NO
*/
7. 图的应用
图是一种非常重要的数据结构，它在计算机科学和现实生活中有着广泛的应用。以下是一些常见的图应用：
社交网络：社交网络可以用图来表示，其中顶点表示用户，边表示用户之间的关系。
地图和导航：地图可以用图来表示，其中顶点表示地点，边表示道路，边的权值可以表示距离或时间。
网络流量：网络流量可以用图来表示，其中顶点表示网络节点，边表示连接，边的权值可以表示带宽或流量。
任务调度：任务调度可以用有向图来表示，其中顶点表示任务，边表示任务之间的依赖关系。
电路设计：电路可以用图来表示，其中顶点表示元件，边表示连接。
编译器优化：编译器可以使用图来表示程序的控制流，以便进行优化。
资源分配：资源分配问题可以用二分图来表示，其中一部分顶点表示资源，另一部分顶点表示需求。
游戏开发：游戏中的地图和关卡可以用图来表示，以便进行路径规划和AI决策。
推荐系统：推荐系统可以使用图来表示用户和物品之间的关系，以便进行推荐。
网页排名：搜索引擎可以使用图来表示网页之间的链接关系，以便进行网页排名。
图的应用非常广泛，上述只是一些常见的例子。在实际应用中，需要根据具体问题选择合适的图表示方法和算法。