图的基本概念和数据结构
圆圈表示节点
线是边
图是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