图是一种复杂的非线性结构，通常用来表示和存储具有“多对多”关系的数据，是数据结构中非常重要的一种结构。这篇文章将带你回忆图相关的最重要的概念以及图的存储结构。
在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继；
在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素(parent node)及下一层的多个元素(孩子节点)相关；
而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。
图(Graph)G由顶点集合V(G)和边集合E(G)构成。例如，
上图中，代表边的顶点对是无序的，则称G为无向图。用圆括号序偶表示无向边。例如可以用(0，1)表示顶点0和1之间的边。
如果表示边的顶点对是有序的，则称G为有向图。用尖括号序偶表示有向边。
一图的基本术语端点和邻接点
无向图：若存在一条边(i，j) 的顶点i和顶点j为端点，它们互为邻接点。
有向图：若存在一条边 的顶点i为起始端点(简称为起点)，顶点j为终止端点(简称终点)，它们互为邻接点。
顶点的度、入度和出度
无向图：以顶点i为端点的边数称为该顶点的度。
有向图：以顶点i为终点的入边的数目，称为该顶点的入度。以顶点i为始点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
若一个图中有n个顶点和e条边，每个顶点的度为di(0≤i≤n-1)，则有：
完全图
无向图：每两个顶点之间都存在着一条边，称为完全无向图， 包含有n(n-1)/2条边。
有向图：每两个顶点之间都存在着方向相反的两条边，称为完全有向图，包含有n(n-1)条边。
稠密图、稀疏图、子图
当一个图接近完全图时，则称为稠密图。相反，当一个图含有较少的边数(即当e<稀疏图。
路径和路径长度
设有两个图G=(V，E)和G'=(V'，E')，若V'是V的子集，即V'属于V，且E'是E的子集，即E'属于E，则称G'是G的子图。在一个图G=(V，E)中，从顶点i到顶点j的一条路径(i,i1...,ij )。其中所有的(ix,iy)∈E(G)，或者∈E(G)。路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。
回路或环
若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。
连通、(强)连通图和(强)连通分量
无向图：若从顶点i到顶点j有路径，则称顶点i和j是连通的。若图中任意两个顶点都连通，则称为连通图，否则称为非连通图。无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。
有向图：若从顶点i到顶点j有路径，则称从顶点i到j是连通的。若图G中的任意两个顶点i和j都连通，即从顶点i到j和从顶点j到i都存在路径，则称图G是强连通图。有向图G中的极大强连通子图称为G的强连通分量。显然，强连通图
只有一个强连通分量，即本身。非强连通图有多个强连通分量。
在一个非强连通中找强连通分量的方法。
① 在图中找有向环。
② 扩展该有向环：如果某个顶点到该环中任一顶点有路径，并且该环
中任一顶点到这个顶点也有路径，则加入这个顶点。
权和网
图中每一条边都可以附带有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网。
二图的存储结构
图的存储结构用来存储每个顶点的信息以及存储每条边的信息。主要的两种存储结构是邻接矩阵和邻接表。
邻接矩阵存储方法
邻接矩阵是表示顶点之间相邻关系的矩阵。邻接矩阵的主要特点：一个图的邻接矩阵表示是唯一的，特别适合于稠密图的存储。邻接矩阵的存储空间为O(n^2)。
设G=(V，E)是具有n(n＞0)个顶点的图，顶点的编号依次为0～n-1。G的邻接矩阵A是n阶方阵，其定义如下：
(1)如果G是无向图，则：A[i][j]=1：若(i,j)∈E(G)， 0:其他；
(2)如果G是有向图，则：A[i][j]=1：若∈E(G)， 0:其他；
(3)如果G是带权无向图，则：A[i][j]= wij：若i≠j且(i,j)∈E(G)， 0：i=j ，∞：其他；
(4)如果G是带权有向图，则：A[i][j]= wij：若i≠j且∈E(G)， 0：i=j ，∞：其他。
图的邻接矩阵存储类型定义如下：
#define MAXV // 声明顶点的类型typedef struct{ int no; //顶点编号InfoType info; //顶点其他信息} VertexType;// 声明的邻接矩阵类型typedef struct // 图的定义{ int edges[MAXV][MAXV]; //邻接矩阵int n，e; //顶点数，边数VertexType vexs[MAXV]; //存放顶点信息} MGraph;
邻接表存储方法
图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。对图中每个顶点i建立一个单链表，将顶点i的所有邻接点链起来。并且为每个单链表上添加一个表头节点(表示顶点信息)。并将所有表头节点构成一个数组，下标为i的元素表示顶点i的表头节点。邻接表的特点如下：邻接表表示不唯一。特别适合于稀疏图存储。邻接表的存储空间为O(n+e)。
图的邻接表存储类型定义如下：
// 声明边节点类型typedef struct ANode{ int adjvex; //该边的终点编号struct ANode *nextarc; //指向下一条边的指针InfoType info; //该边的权值等信息} ArcNode;// 声明邻接表头节点类型typedef struct Vnode{ Vertex data; //顶点信息ArcNode *firstarc; //指向第一条边} VNode;//声明图邻接表类型typedef struct{ VNode adjlist[MAXV] ; //邻接表int n,e; //图中顶点数n和边数e} ALGraph;
思考：
图的邻接矩阵和邻接图两者存储结构各有什么优缺点？
end
点击“❀在看”，让更多朋友们看到吧~