1-图的定义
小结
图是一种扩展的树结构，每个结点可以指向任意的其它结点
链表是特殊的树结构，树是特殊的图结构
图这种数据结构常用于网络规划和路径规划等领域，GPS相关产品大量应用了图结构和图算法
2-图的存储
图的存储分两种：
图的顺序存储，对于顺序存储来说我们如何表达顶点之间存在的联系呢？我们会借助邻接矩阵进行顺序存储。
对于链式存储，多重链表，如何设计结点结构？我们会介绍几种链式存储结构，比如说邻接表，邻接多重表，十字链表
我们先看顺序存储。
邻接矩阵
设图G=(V, E)具有n(n>=1)个顶点v1,v2,...,vn和m条边或弧e1,e2,...,em，则G的邻接矩阵是V*V阶矩阵，记为A(G)。
邻接矩阵存放n个顶点信息和n^2条边或弧信息
其每一个元素aij定义为：
aij = 0 顶点vi与vj不相邻接 1 顶点vi与vj相邻接
优点：
1，容易判断任意两个顶点之间是否有边或弧
2，容易求取各个顶点的度。
无向图可以采用压缩存储方式
邻接表
对图中每一个顶点建立一个单链表，指示与该顶点关联的边或出弧。
头结点 表结点
vexinfo | firstarc adjvex | arcinfo | nextarc
vexinfo：顶点的信息 adjvex：邻接顶点位置
firstarc：第一条关联边结点 arcinfo：边的信息
nextarc：下一条关联边结点
需要多少存储空间？
V+2E
十字链表
将有向图的邻接表和逆邻接表结合在一起，就得到了有向图的另一种链式存储结构——十字链表。
头结点 表结点
vexinfo | firstin | firstout tailvex | headvex | arcinfo | tnext | hnext
vexinfo：顶点的信息 tailvex：弧尾顶点位置
firstin：第一条关联入弧结点 headvex：弧头顶点位置
firstout：第一条关联出弧结点 arcinfo：弧的信息
tnext：弧尾相同的下一条弧
hnext：弧头相同的下一条弧
邻接多重表
邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息；
但在邻接表中，每一条边都有两个结点表示，因此在某些对边进行的操作(例如对搜索过到边做标记)中就需要对每一条边处理两遍；
故引入邻接多重表实现无向图的存储结构。
邻接多重表的结构与十字链表相似
头结点 表结点
vexinfo | firstedge mark | einfo | ivex | inext | jvex | jnext
vexinfo：顶点的信息 mark：标志域
firstedge：第一条关联边结点 einfo：边的信息
ivex：边的第一个顶点位置
inext：顶点i的下一条关联边
jvex：边的另一个顶点位置
jnext：顶点j的下一条关联边
3-图的遍历
定义
从图中的某一顶点出发，沿着一些边访问图中所有的顶点，使得每个顶点仅被访问一次。
分类
深度优先搜索 DFS (Depth First Search)
广度优先搜索BFS（Breadth First Search)
深度优先遍历
算法描述
访问起始顶点v
当v还有邻接顶点未访问时
－深度遍历未访问过的邻接顶点w
当v的所有邻接顶点都被访问时
－若图中所有顶点均已访问
》算法结束
－若图中还有未访问的顶点
》以未访问顶点作为起始顶点深度遍历
仙剑（走迷宫）
其实就是我们以前接触过的二叉树的先序遍历，使用递归
广度优先遍历
算法描述
1，访问起始顶点v0
2，依次访问v0的各个邻接点v01，v02，...，v0x
3，假设最近一次访问的顶点依次为vi1，vi2，...，viy，则依次访问vi1，vi2，....，viy的未被访问的邻接点
4，重复3，直到所有顶点均被访问
其实就是我们以前接触过的二叉树的层次遍历，需要借助队列
小结
广度优先遍历与深度优先遍历是图结构的基础算法，也是其它图算法的基础
4 － 最小连通网
运营商的挑战
在下图标出的城市间架设一条通信线路
要求
任意两个城市间都能够通信
将架设成本降至最低
问题的提出
如何在图中选择n-1条边使得n个顶点间两两可达，且这n-1条边的权值之和最小？
目标
必须使用且仅使用该网络中的n-1条边来联结网络中的n个顶点；
不能使用产生回路的边；
各边上的权值的总和达到最小
Prim算法
基本思想
从图N={V, E}中选择某一顶点u0进行标记，之后选择与它关联的具有最小权值的边(u0, v)，并将顶点v进行标记
反复在一个顶点被标记，而另一个顶点未被标记的各条边中选择权值最小的边(u, v)，并将未标记的顶点进行标记
如此继续下去，直到图中所有顶点都被标记为止
Kruskal算法
基本思想：
对于n个顶点的图G={V, E}
构造一个只有n个顶点，没有边的图G'={V, O}
在E中选择一条具有最小权值的边，若该边的两个顶点不构成回路，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边
如此重复下去，直到所有顶点都连通为止
小结
Prim算法是针对顶点展开的，适合于边的数量较多的情况，算法复杂度是邻接矩阵:O(v2) 邻接表:O(elog2v)
Kruskal算法是针对边展开的，适合于边的数量较少的情况，算法复杂度是O(elog2e)
5 - 最短路径
问题分析
问题的提出：给定一个带权有向图D与源点v，求v到D中其它顶点的最短路径。限定各边上的权值大于0。
解决思路：Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。
算法精髓
S集内的顶点是已经找到最短路径的顶点
V0到w的最短路径只能通过S集内的顶点
D[w]可能改变：
if (D[u] + edge[u, w] < D[w]) {
D[w] = D[u] + edge[u, w];
}
所有顶点之间的最短路径
问题的提法：已知一个各边权值均大于0的带权有向图，对每一对顶点 v_i != v_j，要求求出v_i与v_j之间的最短路径和最短路径长度。
方法：Dijkstra:把所有顶点作为源点，重复执行？
floyd算法本质和Dijkstra本质相同
Floyd算法基本思想
定义一个n阶方阵序列：
A(-1)，A(0)，...，A(n-1)
其中：
A(-1)[i][j] = Edge[i][j]
A(k)[i][j] = min{A(k-1)[i][j]，A(k-1)[i][k]+A(k-1)[k][j]}
k = 0，1，....，n-1
小结
Dijkstra最短路径算法是基于递推的思想设计的
未达顶点的最短路径一定是由已达顶点的最短路径求出
Floyd最短路径算法只是Dijkstra最短路径算法的加强，其本质还是递推