文章目录[隐藏]
图的定义
图的定义非常多，只记录概括，需要的时候自行去查阅：
图按照有无方向分为 无向图 和 有向图。无向图由 顶点 和 边 构成，有向图由顶点和 弧 构成。弧有 弧尾 和 弧头 之分。
图按照边或弧的多少分 稀疏图 和 稠密图。如果任意两个顶点之间都存在边叫 完全图，有向的叫 有向完全图。若无重复的边或顶点到自身的边则叫 简单图。
图中顶点之间有 邻接点、依附 的概念。无向图顶点的边数叫做 度，有向图顶点分为 入度 和 出度。
图上的边或弧上带 权 则称为 网。
图中顶点间存在 路径，两顶点存在路径则说明是 连通 的，如果路径最终回到起始点则称为 环，当中不重复叫 简单路径。若任意两顶点都是连通的，则图就是 连通图，有向则称 强连通图。图中有子图，若子图极大连通则就是 连通分量，有向的则称 强连通分量。
无向图中连通且 n 个顶点 n-1 条边叫 生成树。有向图中一顶点入度为 0 其余顶点入度为 1 的叫 有向树。一个有向图由若干棵有向树构成 生成森林。
图的存储结构
邻接矩阵
定义
图的邻接矩阵（AdjacencyMatrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
设图 G 有 n 个顶点，则邻接矩阵是一个 nxn 的方阵，定义为：
无向图举例：
- 顶点数组：vertex[4]={v0,v1,v2,v3};
- 边数组: arc[4][4]。
矩阵主对角线全为0代表不存在顶点到自身的边，且为对称矩阵。
有向图举例：
- 顶点数组：vertex[4]={v0,v1,v2,v3};
- 弧数组: arc[4][4]。
对角线虽为0，但是矩阵不对称。有向图讲究入度与出度。顶点 V1 的入度为1，正好是第v1列各数之和。顶点 v1 的出度为2，即第v行的各数之和。与无向图同样的办法，判断顶点 vi 到 vj 是否存在弧，只需要查找矩阵中 arc[i][j] 是否为 1 即可。要求 vi 的所有邻接点就是将矩阵第 i 行元素扫描一遍，查找 arc[i][j] 为 1 的顶点。
网图举例：
设图G是网图，有n个顶点，则邻接矩阵是一个nxn的方阵，定义为：
数据结构
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITY 65535 /* 用65535来代表∞ */
typedef sturct
{
VetexType vexs[MAXVEX]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，可看作边表 */
int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;
无向忘图建立
void CreatMGraph(MGraph *G)
{
int i,j,k,w;
printf("输入顶点数和边数：\n");
scanf("%d,%d", &G->numVertexes, &G->numEdges);
for(i = 0; i < G->numVertexes; i++)
scanf(&G->vexs[i]);
for(i = 0; i < G->numVertexes; i++)
for(j = 0; j < G->numVertexes; j++)
G->arc[i][j] = INFINITY;
for(k = 0; k < G->numEdges; k++)
{
printf("输入边(vi,vj)上的下标i,下标j和权w:\n");
scanf("%d,%d,%d",&i,&j,&w);
G->arc[i][j]=w;
G->arc[j][i]=G->arc[i][j];
}
}
邻接表
定义
邻接表(Adjacency List)：数组与链表相结合的存储方式。
结构
图：无向图的邻接表结构
顶点表的各个结点由 data 和 firstedge 两个域表示，data 是数据域，存储顶点的信息，firstedge 是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由 adjvex 和 next 两个域组成。adjvex 是邻接点域，存储某顶点的邻接点在顶点表中的下标，next 则存储指向边表中下一个结点的指针。比如 v 顶点与 vo、V2 互为邻接点，则在 v 的边表中，adjvex 分别为 vo 的 0 和 v2 的 2。
图：有向图的邻接表结构和逆邻接表结构
此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。
图：带权值的网图
代码实现
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct EdgeNode /* 边表结点 */
{
int adjvex; /* 邻接点域，存储该顶点对应的下标 */
EdgeType weight; /* 用于存储权值，对于非网图可以不需要 */
struct EdgeNode *next; /* 链域，指向下一个邻接点 */
} EdgeNode;
typedef struct VertexNode /* 顶点表结点 */
{
VertexType data; /* 顶点域，存储顶点信息 */
EdgeNode *firstedge; /* 边表头指针 */
} VertexNode, AdjList[MAXVEX]; /* 图的邻接表类型定义 */
typedef struct /* 图的邻接表结构 */
{
AdjList adjList;
int numVertexes, numEdges; /* 图的当前顶点数和边数 */
} GraphAdjList;
void CreateALGraph(GraphAdjList *G) {
int i, j, k, w;
EdgeNode *e;
printf("请输入顶点数和边数：\n");
scanf("%d %d", &G->numVertexes, &G->numEdges);
for (i = 0; i < G->numVertexes; i++) {
scanf(" %c", &G->adjList[i].data);
G->adjList[i].firstedge = NULL;
}
for (k = 0; k < G->numEdges; k++) {
printf("请输入边(vi,vj)上的顶点序号：\n");
scanf("%d, %d", &i, &j);
/* 建立从顶点i到顶点j的连接 */
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = j; /* 邻接点序号 */
e->next = G->adjList[i].firstedge; /* 插入链表头部 */
G->adjList[i].firstedge = e; /* 头插法 */
/* 建立从顶点j到顶点i的连接 */
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = i; /* 邻接点序号 */
e->next = G->adjList[j].firstedge; /* 插入链表头部 */
G->adjList[j].firstedge = e; /* 头插法 */
}
}
十字链表
十字链表（Orthogonal List）:结合了邻接表与逆邻接表。
顶点表结点结构：
| data | firstin | firstout |
| --- | --- | --- |
- firstin: 指向该顶点入边表中第一个结点。
- firstout: 指向该顶点的出边表中第一个结点。边表结点结构：
| tailvex | headvex |headlink | taillink |
| --- | --- | --- |---|
- tailvex: 弧起点在顶点表的下标。
- headvex: 弧终点在顶点表中的下标。
- headlink: 入边表指针域，指向终点相同的下一条边。
- taillink: 边表指针域，指向起点相同的下一条边。如果是网，还可以增加一个weight域来存储权值。
邻接多重表
这里不多做介绍，只留个概念，需要用到的时候再来补充
| ivex | ilink | jvex | jlink |
| --- | --- | --- | --- |
- vex、jvex：某条边依附的两个顶点在顶点中的下标。
- ilink: 指向依附顶点 ivex 的下一条边。
- jlink: 指向依附顶点 jvex 的下一条边。
边集数组
边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信
息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权
（weight）组成。| begin | end | weight |
| --- | --- | --- |
- begin：起点下标
- end： 终点下标
- weight: 存储权值
图的遍历
从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（TraversingGraph）
深度优先遍历
深度优先遍历（Depth_FirstSearch），也有称为深度优先搜索，简称为DFS，类似于树的前序遍历。
- 连通图：从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问。
- 非连通图：它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
用邻接矩阵方式实现：
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef int Boolean;
#define TRUE 1
#define FALSE 0
Boolean visited[MAX];
typedef struct {
char vexs[MAX]; /* 顶点表 */
int arcs[MAX][MAX]; /* 邻接矩阵 */
int vexnum, arcnum; /* 图的当前顶点数和边数 */
} MGraph;
void DFS(MGraph *G, int i) {
int j;
visited[i] = TRUE; /* 标记顶点vi为已访问 */
printf("%c", G->vexs[i]);
for (j = 0; j < G->vexnum; j++) {
if (G->arcs[i][j] == 1 && !visited[j]) /* 如果顶点vi与vj有边且vj未被访问 */
{
DFS(G, j); /* 递归访问顶点j */
}
}
}
void DFS_Traverse(MGraph *G) {
int i;
for (i = 0; i < G->vexnum; i++) {
visited[i] = FALSE; /* 初始化所有顶点为未访问 */
}
for (i = 0; i < G->vexnum; i++) {
if (!visited[i]) /* 如果顶点i未被访问 */
{
DFS(G, i); /* 从顶点i开始深度优先遍历 */
}
}
}
int main() {
MGraph G;
/* 创建图G */
G.vexnum = 5; /* 假设有5个顶点 */
G.arcnum = 6; /* 假设有6条边 */
/* 顶点表 */
G.vexs[0] = 'A';
G.vexs[1] = 'B';
G.vexs[2] = 'C';
G.vexs[3] = 'D';
G.vexs[4] = 'E';
/* 邻接矩阵 */
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0; /* 初始化邻接矩阵 */
}
}
/* 添加边(无向图) */
G.arcs[0][1] = 1;
G.arcs[1][0] = 1; // A-B
G.arcs[0][2] = 1;
G.arcs[2][0] = 1; // A-C
G.arcs[1][3] = 1;
G.arcs[3][1] = 1; // B-D
G.arcs[2][4] = 1;
G.arcs[4][2] = 1; // C-E
G.arcs[3][4] = 1;
G.arcs[4][3] = 1; // D-E
DFS_Traverse(&G);
printf(" \n");
return 0;
}
ABDEC
[Done] exited with code=0 in 0.408 seconds
广度优先遍历
广度优先遍历（Breadth_First_Search），又称为广度优先搜索，简称BFS。类似于树的层序遍历。
将图的第一幅图稍微变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与B和F有边的顶点C、I、G、E为第三层，再将这四个顶点有边的D、H放在第四层，如图的第二图所示。此时在视觉上感觉图的形状发生了变化，其实顶点和边的关系还是完全相同的。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef int Boolean;
#define TRUE 1
#define FALSE 0
Boolean visited[MAX];
/* 队列结构定义 */
typedef struct Queue {
int data[MAX];
int front; /* 队头 */
int rear; /* 队尾 */
} Queue;
/* 入队操作 */
void EnQueue(Queue* Q, int item)
{
if((Q->rear + 1) % MAX == Q->front)
return; /* 队列满 */
Q->data[Q->rear] = item; /* 入队 */
Q->rear = (Q->rear + 1) % MAX; /* 更新队尾指针 */
}
/* 出队操作 */
int DeQueue(Queue* Q)
{
if(Q->front == Q->rear)
return -1; /* 队列空 */
int item = Q->data[Q->front]; /* 取队头元素 */
Q->front = (Q->front + 1) % MAX; /* 队头指针后移 */
return item;
}
/* 队列判空操作 */
int IsEmpty(Queue* Q)
{
return Q->front == Q->rear;
}
typedef struct {
char vexs[MAX]; /* 顶点表 */
int arcs[MAX][MAX]; /* 邻接矩阵 */
int vexnum, arcnum; /* 图的当前顶点数和边数 */
} MGraph;
/* 广度优先搜索算法 */
void BFS(MGraph *G, int start) {
Queue Q;
Q.front = Q.rear = 0; /* 初始化队列 */
visited[start] = TRUE; /* 标记起始顶点为已访问 */
printf("%c ", G->vexs[start]); /* 输出起始顶点 */
EnQueue(&Q, start); /* 入队起始顶点 */
while (!IsEmpty(&Q)) {
int v = DeQueue(&Q); /* 出队一个顶点 */
for (int j = 0; j < G->vexnum; j++) {
if (G->arcs[v][j] == 1 && !visited[j]) { /* 如果有边且未访问 */
visited[j] = TRUE; /* 标记为已访问 */
printf("%c ", G->vexs[j]); /* 输出该顶点 */
EnQueue(&Q, j); /* 入队该顶点 */
}
}
}
}
void BFS_Traverse(MGraph *G) {
for (int i = 0; i < G->vexnum; i++) {
visited[i] = FALSE; /* 初始化所有顶点为未访问 */
}
for (int i = 0; i < G->vexnum; i++) {
if (!visited[i]) { /* 如果顶点i未被访问 */
BFS(G, i); /* 从顶点i开始广度优先遍历 */
}
}
}
int main() {
MGraph G;
/* 创建图G */
G.vexnum = 5; /* 假设有5个顶点 */
G.arcnum = 6; /* 假设有6条边 */
/* 顶点表 */
G.vexs[0] = 'A';
G.vexs[1] = 'B';
G.vexs[2] = 'C';
G.vexs[3] = 'D';
G.vexs[4] = 'E';
/* 邻接矩阵初始化 */
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0; /* 初始化邻接矩阵 */
}
}
/* 添加边(无向图) */
G.arcs[0][1] = 1;
G.arcs[1][0] = 1; // A-B
G.arcs[0][2] = 1;
G.arcs[2][0] = 1; // A-C
G.arcs[1][3] = 1;
G.arcs[3][1] = 1; // B-D
G.arcs[2][4] = 1;
G.arcs[4][2] = 1; // C-E
printf("广度优先遍历结果：\n");
BFS_Traverse(&G); /* 执行广度优先遍历 */
return 0;
}
广度优先遍历结果：
A B C D E
[Done] exited with code=0 in 0.436 seconds
最小生成树
造连通网的最小代价生成树称为最小生成树（MinimumCostSpanningTree)。主要有2个算法，普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。
因我平常工作主要涉及驱动，底层控制，实际用到很少，待需要用到的时候在来学习补充。
最短路径
对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点
迪杰斯特拉（Dijkstra）算法
Dijkstra算法是由荷兰计算机科学家Edsger Dijkstra在1956年提出的，用于解决单源最短路径问题。它是一种贪心算法，能够找到图中一个顶点到其他所有顶点的最短路径。
Dijkstra算法基于这样一个事实：如果顶点i到顶点j的最短路径经过顶点k，那么这条路径上从i到k的部分也必然是i到k的最短路径。
算法的核心思想是：
- 维护一个已确定最短路径的顶点集合
- 每次从未确定的顶点中选择距离源点最近的顶点
- 更新通过该顶点到达其他顶点的距离
- 重复这个过程直到所有顶点都被处理
应用场景:
Dijkstra算法广泛应用于：
- 网络路由协议
- 地图导航系统
- 社交网络分析
- 游戏开发中的路径寻找
- 交通运输规划
#include <stdio.h>
#include <stdlib.h>
#define MAX_VEX 9
#define INFINITY 65535
typedef int PathMatrix[MAX_VEX]; /* 用于存储最短路径下标的数组 */
typedef int ShortPathTable[MAX_VEX]; /* 于存储到各点最短路径的权值和 */
typedef struct {
char vexs[MAX_VEX]; /* 顶点表 */
int arcs[MAX_VEX][MAX_VEX]; /* 邻接矩阵 */
int num_vex, num_arc; /* 图的当前顶点数和边数 */
} MGraph;
/* Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]
* @param G 图的邻接矩阵表示
* @param v0 起始顶点
* @param p 存储最短路径下标的数组
* @param D 存储到各点最短路径的权值和
*/
void ShortestPath_Dijkstra(MGraph G, int v0, PathMatrix *p, ShortPathTable *D) {
int v, w, k, min;
int final[MAX_VEX] = {0}; /* 标记顶点是否已确定最短路径 */
for (v = 0; v < G.num_vex; v++) {
final[v] = 0; /* 初始化所有顶点未确定最短路径 */
(*D)[v] = G.arcs[v0][v]; /* 初始化到各顶点的距离 */
(*p)[v] = v0; /* 初始化路径为起始顶点 */
}
(*D)[v0] = 0; /* 起始顶点到自身的距离为0 */
final[v0] = 1; /* 标记起始顶点已确定最短路径 */
/* 确定所有顶点的最短距离 */
for (v = 1; v < G.num_vex; v++) {
min = INFINITY; /* 初始化最小距离为正无穷大 */
/* 找到未确定最短路径的顶点中距离起始顶点最近的顶点 */
for (w = 0; w < G.num_vex; w++) {
if (!final[w] && (*D)[w] < min) {
min = (*D)[w]; /* 更新最小距离 */
k = w; /* 记录最短距离的顶点下标 */
}
}
final[k] = 1; /* 标记该顶点已确定最短路径 */
/* 更新其他顶点的最短路径 */
for (w = 0; w < G.num_vex; w++) {
if (!final[w] && (min + G.arcs[k][w] < (*D)[w])) {
(*D)[w] = min + G.arcs[k][w]; /* 更新最短路径长度 */
(*p)[w] = k; /* 更新路径下标 */
}
}
}
}
// 添加main函数用于测试Dijkstra算法
int main() {
MGraph g;
PathMatrix p;
ShortPathTable D;
int i, j;
// 初始化图的数据
g.num_vex = 9;
g.num_arc = 15;
// 初始化顶点
char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};
for (i = 0; i < g.num_vex; i++) {
g.vexs[i] = vexs[i];
}
// 初始化邻接矩阵
for (i = 0; i < g.num_vex; i++) {
for (j = 0; j < g.num_vex; j++) {
if (i == j) {
g.arcs[i][j] = 0;
} else {
g.arcs[i][j] = INFINITY;
}
}
}
// 添加边的权值
g.arcs[0][1] = 1; // A->B = 1
g.arcs[0][2] = 5; // A->C = 5
g.arcs[1][2] = 3; // B->C = 3
g.arcs[1][3] = 7; // B->D = 7
g.arcs[1][4] = 5; // B->E = 5
g.arcs[2][4] = 1; // C->E = 1
g.arcs[2][5] = 7; // C->F = 7
g.arcs[3][6] = 3; // D->G = 3
g.arcs[3][7] = 5; // D->H = 5
g.arcs[4][5] = 3; // E->F = 3
g.arcs[4][7] = 2; // E->H = 2
g.arcs[4][8] = 5; // E->I = 5
g.arcs[5][8] = 1; // F->I = 1
g.arcs[6][7] = 2; // G->H = 2
g.arcs[7][8] = 3; // H->I = 3
// 调用Dijkstra算法计算从顶点0(A)到其他各顶点的最短路径
ShortestPath_Dijkstra(g, 0, &p, &D);
// 输出结果
printf("顶点 最短路径长度 最短路径\n");
for (i = 0; i < g.num_vex; i++) {
printf("%c %d ", g.vexs[i], D[i]);
// 打印路径
int path[MAX_VEX];
int path_index = 0;
int temp = i;
while (temp != 0) { // 回溯到起点
path[path_index++] = temp;
temp = p[temp];
}
path[path_index] = 0; // 添加起点
// 输出路径
for (j = path_index; j >= 0; j--) {
printf("%c", g.vexs[path[j]]);
if (j > 0)
printf(" -> ");
}
printf("\n");
}
return 0;
}
顶点 最短路径长度 最短路径
A 0 A
B 1 A -> B
C 4 A -> B -> C
D 8 A -> B -> D
E 5 A -> B -> C -> E
F 8 A -> B -> C -> E -> F
G 11 A -> B -> D -> G
H 7 A -> B -> C -> E -> H
I 9 A -> B -> C -> E -> F -> I
[Done] exited with code=0 in 0.408 seconds
弗洛伊德（Floyd）算法
Floyd算法是一种用于寻找图中所有顶点对之间最短路径的算法，也称为"多源最短路径算法"。它的主要特点包括：
1. 算法简单：核心代码只有几行，采用动态规划思想，容易理解和实现
2. 全面性：一次运行可以得到图中任意两点间的最短路径
3. 时间复杂度高：O(n³)，空间复杂度O(n²)
4. 适用范围：适用于中小规模的图，不适合大规模图适用场景：
- 导航系统：
- 车载导航设备
- GPS定位系统
- 无人机路径规划
- 网络通信：
- 嵌入式网络设备的路由选择
- 传感器网络中的数据传输路径优化
- 工业控制：
- 自动化生产线的路径优化
- 机器人路径规划
目前没有涉及该领域，暂时不学习。待学习的时候来补充。
了解 Heiweilu的小世界 的更多信息
订阅后即可通过电子邮件收到最新文章。
