数据结构——图（一）

这是我参与更文挑战的第19天，活动详情查看：更文挑战

图

图的概念

图G由顶点集V和边集E组成，记为G=(V,E)其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)集合，若V={$v_1,v_2,v_3…,v_n$},则用|V|表示图G中顶点的个数，也称图G的阶，E={(u,v)|u$\in V,v\in V$ },用|E|表示图G中边的条数

不存在空图，即图必有顶点

• 有向图
• 无向图
• 简单图
  • 不存在重复边
  • 不存在顶点到自身的边
• 多重图：与简单图相反
• 完全图：在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图，含有n个顶点的无向完全图有n(n-1)条边，在有向图中，若任意两个顶点之间存在都存在方向相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条有向边，图5.1中$G_2$ 为无向完全图，而$G_3$为有向完全图

• 子图：设有两个图G=(V,E)和G‘ = (V’,E’),若V’是V的子集，且E‘是E的子集则称G’是G的子图。如果G和G‘的顶点数量相同，则称G’为生成子图
• 连通，连通图和连通分量：无向图的极大连通子图称为连通分量
• 强连通图，强连通分量：从顶点v到顶点w都连通，则是强连通
• 生成树，生成森林：
  • 连通图的生成树是包含图中全部顶点的一个极小连通子图
  • 非连通图中，连通分量的生成树构成了非连通图的生成森林
• 顶点的度，入度，出度：
  • 图中的顶点的度：这个点边的数目
  • 入度：以顶点v为终点的有向边的数目，
  • 入度之和和出度之和相等，并等于边数
• 边的权和网：每个边都有一个数。带权图称为网
• 路径，路径长度，回路：路径——顶点$v_p到顶点v_q之间的一条路径序列v_p,v_1,v_2,v_q$，路径上边的数目称为路径长度，最后一个顶点和第一个顶点相同的路经称为回路或环，若一个图有n个顶点，并且有大于n-1条边，则此图一定有环
• 简单路径，简单回路：不存在重复出现的路径称为简单路径，除第一个顶点外不出现重复出现的顶点的回路称为简单回路
• 距离：i到v的最短路径长度
• 一个顶点入度为0，其余顶点均不为0的有向图，称为有向树

图的存储方式

邻接矩阵<顺序>

一个一维数组存储图中顶点信息，一个二维数组存储图中边的信息，该二维数组称为邻接矩阵

特点

• 无向图的邻接矩阵一定是个对称矩阵，因此可以只存一半
• 无法直接看出总共有几条边
• 稠密图适合
• A‘’的元素A”[i][j] 等于顶点i到顶点j的长度为n的路径的数目

邻接表<链接>

特点

• 稀疏图
• 若G为无向图，则所需存储空间为O(|V|+2|E|)；若G为有向图则为O(|V|+|E|)
• 无法直接看出来两个节点之间是否存在边
• 求入度不好求
• 邻接表表示不唯一