前言
与线性表中的元素是“一对一”的关系和树中的元素是“一对多”的关系不同的是，数据结构中图的元素则是“多对多”的关系。图（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 100 int 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：表示边或弧的数目
