目录
前言
一，图的基本知识
二，图的表示法：边列表
三，图的表示方法：邻接矩阵
四，图的表示方法：邻接表
五，功能
总结
前言
图是一个非常有意思东西，可以运用到生活中的很多很多的领域
一，图的基本知识
这个是树和图各个的关系
图的顶点集和边集的表示
顶点集V V={v1,v2,v3,v4…v9} 边集E E={ {v1，v2}，{v1,v3}…{v8，v9}} 图有两种类型
1，有向图 2，无向图
(无序对) (单向对)
比如社交网络就是无向图，网络链接就是无向图
单向图 双向图 加权图
加权就是给每个路径赋予长度值，我们把加权值加起来就可以算出最短路径了
(每个链接有不同的权重，这个就是加权图)图的属性
自环 多重边 网页的刷新
航班的路线
如果不包括闭环和多重边，则这个图被称为简单图
问题：在给定的节点中，求最大的边数为多少？假设有n个节点
有方向：0<=|E|<=n(n-1) 无方向：0<=|E|<n(n-1)/2
图中的数量接近最大的可能边数，则这个图是稠密的，接近顶点的平方数量
图中的数量接近最小的可能边数，则这个图是系数的，接近顶点的数量专有名词
walk（道路）指所划的路里面有重复的点
path（路径）指最简单的路径无重复的点
trail：顶点可以重复，边不可重复图要选择合适的数据结构存储
稠密：邻接矩阵
稀疏：邻接表图的连接
一个图被称为强连接的条件：从图上的任意节点可以来到任意其他节点
如图一，这个是无向图，则我们就直接说连接
如图二，这个是有向图，但是B不可以到C等，则我们称为弱连接
如图三，这个是有向图，且每个节点可以到每个节点，则我们称为强连接无环图
一个没有循环的图称为无环图
左图则是一个无向无环图，右图则是一个有向无环图
A-B-E-H-D-A这个就是最简单的环
二，图的表示法：边列表
无加权
下面我们用数组和链表表示一下这个图
我们可以看到，左边是顶点列表，右边是边列表，对于边列表，我们有两种表示形式
//C struct Edge {char* starVertex;char* endVertex; }; //C++ class Edge {string starVertex;string starVertex; };由于这个是无向图，所以AB和BA在里面是一样的，但是为有向图就不一样了
加权图
当我们的图有了权重之后，我们这个节点可以改一下
我们的表示形式也可以改
//C struct Edge {char* starVertex;char* endVertex;int weight }; //C++ class Edge {string starVertex;string starVertex;int weight; };我们在考虑是否使用这个邻接表的时候，我们要考虑它的空间复杂度和时间复杂度
空间复杂度
在空间上，当然我们上面实现的知识几个字母代表的节点进行互相连接，我们来模拟一下我们现实生活中例子
在我们设置图的时候，名字就不再是那种一个字母一个字母的了，所以我们再边列表和顶点列表都弄一遍名字会大大提高内存的占用，这个时候我们就要用到指针和引用了或者运用索引
空间复杂度我们考虑了，结果为O(|V|+|E|)
时间复杂度
再程序中最频繁的操作就是查找了
时间复杂度O(|E|){ 1，遍历图O(|E|) 2，检查图中是否所有都有连接O(|E|) }
没有自环和多重边的时候
有方向：0<=|E|<=n(n-1) 无方向：0<=|E|<n(n-1)/2
所以O(|E|)=O(V^2)
总的来说这样的空间复杂度并不是很理想，不是很高效，所以我们应该寻找更好的办法
三，图的表示方法：邻接矩阵
我们在使用边列表的时候，不难发现，他的时间复杂度以及达到V^2的地步了，所以我们肯定要选择别的更好的，V就很好，下面我们就来看看邻接矩阵
我们来分析一下这个矩阵
我们先来看1的位置， 我们给右边那个图标上了对应的索引，然后我们来画图
首先A连接了BCD这三个字母，那么对应的索引就是1，2，3这三个数字，我们就在1，2，3这写1
紧接着B连接了AEF这三个字母 ，那么对应的索引就是0，4，5这三个数字，我们就在0，4，5这写1
当我们把所有的1写完是这样的
然后再空余的地方补上0就好了
左边的索引是对应你所站的顶点，上面的索引则是你站的顶点所连接节点的索引
在无向图里面，Aij和Aji是对称的，但是有向图却不一样，有向图就不一定对称了
这样有什么好处呢？我们只可以用画一般的矩阵就好了，但是这个就稍稍难一丢丢
现在我们学习完了邻接矩阵，我们就来进行时间和空间复杂度的计算
时间复杂度
寻找一个特定的节点
比如我们寻找一个F节点
我们在顶点列表找到对应的索引，然后再矩阵找到对应的索引，然后就可以逐个访问周围的顶点了，那么时间复杂度就是O(V)+O(V)那么就是O(V)
判断两个节点是否连接
在顶点列表里面找到索引，然和去矩阵里面判断对应的小方格里面是否为1，这里可以运用哈希表
那么加权图怎么写呢？
我们只需要在对应的连接的小方格写下数字即可
空间复杂度
我们确实把时间复杂度降低了，但是空间复杂度就不低了，这个图十分稀疏，为O(V^2)+O(V)，就是O(V^2)
就比如我们社会网路中有10亿个人，但是每个人好友有1000就不错了，且还没有1000，这就会极大浪费我们内存今天我们一个电脑的容量：5*10^11byte=0.5TB
我们算每一个名字算一个字节，那么就是10^18byte=1000PB
这一个电脑都装不下对此我们应该想出另外一个办法
四，图的表示方法：邻接表
我们不难观察到我们矩阵的左边的索引都是起点，上面都是终点
我们就这样，把对应的连接的节点放入到表中，对此我们有两个方式构建邻接表
方法一：
指针数组int*A[8]每个数组可以指向不同的数组
方法二：
C++容器
这里我们使用这个方法，空间复杂度就是O(E)，这个空间复杂度下降了很多时间复杂度
判断一个节点是否相连
邻接矩阵 邻接表 O(1) O(n)
这里有0和1可以快速区分
直接查找这里是线性查找需要一个一个
扫描，还有最优的二分法O()
查找一个节点
我们以一个社交网络为例子
在10^9使用者，每个人最大的朋友数量为1000，一个机器一次可以处理10^6行指令每秒
邻接矩阵 邻接表 查找一个节点 10^9/10^6=1000s=16.66min 10^4/10^6=10^-2=10ms 查找连个点是否相连 1/10^6s=1us 10ms 所以综上所述，如果稀疏我们就选择邻接表
五，功能
插入与删除
邻接表是在对应索引加上那个节点就好，邻接矩阵是在对应的节点写下1
我们使用数组的话就是十分复杂的，所以我们直接使用链表实现动态，其实树也可以
我们创建一个节点数组，这个是访问每一行，然后逐步利用链表的知识进行操作即可
邻接矩阵的话就是运用二维数组和矩阵就好了
总结
1，学习了图的基本知识，特殊的图有自环和多重边，加权图，顶点集和边集，这几个是最重要的
2，边列表，这个时间复杂度太高，创建一个顶点list，边list
3，邻接矩阵，这个空间复杂度高，但是时间复杂度相对较好(主要是查找两个边十分相连)，使用在稠密图
4，邻接表，这个空间复杂度相对较低，时间复杂度也较好(查找点和判断相连都一样)，使用在稀疏图
