图的基本概念和数据结构
圆圈表示节点
线是边
图是V和E的二元组
无向图：边没有方向（边是双向的）
有向图：边有方向
无权图：所有边的权重都是1
有权图：权重不同；在不同的应用里，权重的意义不同
没有的边记作0或者无穷大，具体看实际应用
基本原则是进行搜索的时候，使无法通过这条边
数据结构
无向无权图(Undirected Unweighted Graph)
有向无权图(Dirceted Unwieghted Graph)
无向图的邻接矩阵关于主对角线对称
有向图的邻接矩阵通常是不对称的
有向有权图(Undirected Weighted Graph)
-------------------------
最短路
Simple Path：路径上没有重复节点即为简单路径
无权图：长度等于边数
有权图：长度等于边权加和
单元最短路(Single-source Shortest Path Problem)：
输入图G，起点s
输出到所有点的最短路
无权图最短路算法
int < queue >;
struct a[N]{
int v;//vertex
bool visit = 0;
int dist = inf;
int path = 0;//路径
};
首先把起始点放入队列，设为已访问，距离是0
拿出起始点（dequeue()），如果起始点未被访问过，开始迭代此点；否则取出队列中下一点然后进行相同操作
迭代：
void function()
{
拿出上一点;
visit = 1;
dist[现在点] = dist[上一点] + 1;
path[现在点] = 上一点;
此点插入队列;
return ;
}
由于无向图的最短路仅取决于经过的边数，故越早经过的必然是最短路
if( queue.empty() ) 返回结构体的表;
算法时间复杂度： O(|V|+|E|)
初始化需要把每个点的参量遍历一遍，时间复杂度是O(|V|)
队列操作只会把没有访问过的节点插入，所以每个节点只会被访问一次，时间复杂度是O(|V|);
每个节点只会被访问一次，所以每个边只会被访问一次，时间复杂度是O(|E|)
有权图最短路算法：迪杰斯特拉算法(Dijkstra`s Algorithm)
初始化：
需要一个优先队列（离起始点最近的点在最前面）
以dist为排序依据，同时记录所对应的path（即为指向的点）
一个结构体，包括vertex，dist，path
其中 dist = inf , path = 0;
如果路径更短（dist`=dist+weigth[现在点]），就取代原来的值，并记入path，同时插入到优先队列中
存在自环，所以如果不更新，则不向下迭代；即相等时不更改
要求：权重非负
时间复杂度：
插入和取出的次数不会超过节点+边的数量：O(|V|+|E|)
优先队列的长度不会超过点的数量，最坏情况下所有边都在队列里O(log|V|)（最小堆实现）
总时间复杂度：O((|V|+|E|)log|V|)
标签：图论,dist,队列,复杂度,笔记,节点,学习,path,短路 From： https://www.cnblogs.com/coper/p/graph_theory_note.html