【数据结构与算法】图的概述（内含源码）

个人主页：【😊个人主页】
系列专栏：【❤️数据结构与算法】
学习名言：天子重英豪，文章教儿曹。万般皆下品，惟有读书高——《神童诗劝学》

---

---

系列文章目录

第一章 ❤️ 学前知识
第二章 ❤️ 单向链表
第三章 ❤️ 递归
…

---

---

前言

与线性表中的元素是“一对一”的关系和树中的元素是“一对多”的关系不同的是，数据结构中图的元素则是“多对多”的关系。图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的，今天就让我来带大家了解数据结构中图结构吧。

---

什么是图？

在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
顶点有时也称为节点或者交点，边有时也称为链接
图有各种形状和大小。边可以有权重（weight），即每一条边会被分配一个正数或者负数值。

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合

---

图的分类

图按照无方向和有方向分为：无向图和有向图。

不带有箭头指向的图只由顶点和边构成称为无向图，有向图是由顶点和弧（有向边构成）。弧有弧头和弧尾区别。

图按照边分为：稀疏图和稠密图

这是个模糊的概念，同样是相对的概念。

完全图

如果任意两个顶点之间都存在边叫完全图，有向的边叫有向完全图。如果无重复的边或者顶点到自身的边叫简单图。在用数学方式表示时，无向边用()表示，有向边用<>表示。我们目前接触到的图全是简单图。

没有重复的边或者到自身的边（简单图），右图则有

网

这种边带权值的图叫网

---

顶点与边

顶点与边的关系

• 顶点的度：顶点关联边的数目。有向图图中有，入度：方向指向顶点的边；出度：方向背向顶点的边。在有向图中顶点的度就是两者之和。
• 路径长度：路径上边或者弧的数目。

---

图的存储结构

理论上，图就是一堆顶点和边对象而已，那我们又如何用代码来实现它呢？

通常我们有两种选择：邻接列表和邻接矩阵。

邻接列表

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

顶点表的各个结点由data（数据域）和Firstedge（指针域）两个域表示，data是数据域，指针域指向边表的第一个结点，即顶点的第一个邻接点。边表结点由adjvex（邻接点域）和next两个域组成。
邻接点域存储某顶点的邻接点在顶点表中坐标，next存储边表中下一个结点指针。
如图中v1顶点与v2、v0互为邻接点，则在v1边表中，adjvex分别为0和2。
有向图也可以用邻接表，出度表叫邻接表，入度表尾逆邻接表。

#include <stdio.h>
#include <stdlib.h>// 邻接表中每个节点的结构体
struct AdjListNode {int dest;struct AdjListNode* next;
};// 邻接表的结构体
struct AdjList {struct AdjListNode *head;
};// 图的结构体
struct Graph {int V;struct AdjList* array;
};// 创建一个新的邻接表节点
struct AdjListNode* newAdjListNode(int dest) {struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));newNode->dest = dest;newNode->next = NULL;return newNode;
}// 创建一个具有V个顶点的新图
struct Graph* createGraph(int V) {struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));graph->V = V;// 创建邻接表数组graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));// 初始化链表头为空for (int i = 0; i < V; ++i)graph->array[i].head = NULL;return graph;
}// 添加一个边到无向图
void addEdge(struct Graph* graph, int src, int dest) {// 添加一条从src到dest的边struct AdjListNode* newNode = newAdjListNode(dest);newNode->next = graph->array[src].head;graph->array[src].head = newNode;// 添加一条从dest到src的边，因为是无向图newNode = newAdjListNode(src);newNode->next = graph->array[dest].head;graph->array[dest].head = newNode;
}// 打印邻接列表表示的图
void printGraph(struct Graph* graph) {for (int v = 0; v < graph->V; ++v) {struct AdjListNode* pCrawl = graph->array[v].head;printf("\n 邻接列表%d: ", v);while (pCrawl) {printf("-> %d", pCrawl->dest);pCrawl = pCrawl->next;}printf("\n");}
}int main() {// 创建一个具有5个顶点的新图struct Graph* graph = createGraph(5);// 添加边addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 2, 3);addEdge(graph, 2, 4);addEdge(graph, 3, 4);// 打印邻接列表表示的图printGraph(graph);return 0;
}

邻接矩阵

邻接矩阵(Adjacency Matrix):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:

• 对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零(在此仅讨论无向简单图)，副对角线不一定为0，有向图则不一定如此。
• 在无向图中，任一顶点i的度为第i列(或第i行)所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
• 用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n(n-1)/2个空间

#include <stdio.h>#define MAX_NODES 100int adj_matrix[MAX_NODES][MAX_NODES];void add_edge(int start, int end) {adj_matrix[start][end] = 1;adj_matrix[end][start] = 1; // 无向图需要将两个方向都标记为已连接
}int main() {// 添加边add_edge(0, 1);add_edge(0, 2);add_edge(1, 2);add_edge(2, 3);// 输出邻接矩阵printf("邻接矩阵：\n");for (int i = 0; i < MAX_NODES; i++) {for (int j = 0; j < MAX_NODES; j++) {printf("%d ", adj_matrix[i][j]);}printf("\n");}return 0;
}

图的定义和术语总结

顶点（Vertex）：图中的数据元素通常称为顶点
弧（Arc）：若< v,w >∈VR，则< v,w >表示从v到w的一条弧
弧尾（Tail）：v为弧尾或初始点（Initial node）
弧头（Head）：w为弧头或终端点（Terminal node）
有向图（Digraph）：图中每条边都有方向
无向图（Undigraph）：图中每条边都没有方向
连通图（Connected Graph）：对于图中任意两个顶点v，j∈V，v和j都是连通的，则称G是连通图
连通分量（Connected Compenent）：无向图中的极大连通子图
完全图（Completed graph）：有1/2*n（n-1）条边的无向图称为完全图
有向完全图：具有n（n-1）条弧的有向图称为有向完全图
稀疏图（Sparse graph）：有很少条边或弧（如e < nlogn）的图称为稀疏图
稠密图（Dense graph）：有很多条边或弧
权（Weight）：有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权
度（Degree）：定点v的度是和v相关联的边的数目，记为TD（V）
入度（InDegree）：以顶点v为头的弧的数目称为v的入度，记为ID（v）
出度（Outdegree）：以v为尾的弧的数目成为v的出度，记为OD（v）
V： 是顶点的有穷非空集合
VR：是两个顶点之间的关系的集合
n：表示图中顶点数目
e：表示边或弧的数目