图(数据结构篇)

数据结构之图

图

概念：

• 一个图(graph)G=(V,E)由顶点集V和边集E组成，每一条边就是一个点对(u,w)，其中u，w∈V，有时边称作弧，如果点对是有序的，那么组成的图叫做有向图，反之就是无向图。有时候边还具有第三种成分，称作权或值。
• 图中的一条路径是一个顶点序列w1,w2,w3…wn，使得(w_i,w_i+1)∈E，1<i<N；这样一条路径的长度就为该路径的边数。如果图中含有一条从顶点到自身的边(u,u)，那么路径v,v称作为环。而我们讨论的图一般是无环的。
• 简单路径是一条路径上的所有顶点都是互异的，但第一个顶点和最后一个顶点可能相同。
• 当一个长至少为1的路径中的第一个顶点等于最后一个顶点时，则称为圈，对于无向图的圈，要求边是互异的，意思就是u到v跟v到u是一条边形成的不满足无向图的圈。
• 无向图中的每一个顶点到其他顶点都有一条路径的称作这个无向图连通的，具有这种性质的有向图称为强连通，反之就是弱连通。
• 完全图的每一对顶点间都存在一条边的图

图的表示：

• 表示的图的一种简单方法是使用一个二维数组，称为邻接矩阵表示法，对于每条边(u,v)，我们将数组an[u] [v]=1；否则数组的元素等于0，如果边有权，我们就令an[u] [v]的值等于该权，而**用一个很大或者很小的权作为标记表示不存在的边。**但是该方法的空间代价太大，如果图是稠密的，可以用这种方法。空间需求O(|V|²)；
• 如果图是稀疏的，我们就用邻接表(数组+链表)来表示，数组的元素个数代表着图中有多少个节点，每个索引的链表存该索引顶点邻接的所有顶点。顶点的名称不一定是数字，因此需要将顶点通过哈希函数映射到数组中。

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms