一起学习交流~

图-01-图的基本概念

算法 laomuji 7个月前 (03-01) 310次浏览 已收录 0个评论

图的常用类型

无向图: A连接B B也连接A
有向图: A连接B B不连接A
混合图: 既有无向图也有有向图
以上三种图,一般都用有向图表示,因为无向图和混合图都可以通过有向图形成
带权图: 边拥有权重

图的常用术语

顶点:相当于节点,一般叫做vertex
边:两个顶点相连的线称作为边,一般叫做edge
路径:从一个顶点到另一个顶点经过所有点的集合,一般称path
环:A连接B,B连接C,C连接A,此时就形成了环
负权环:如果一个环的所有边的权重加起来为负数,就称作负权环
连通性:如果两个顶点之间至少存在一条路径,称作这两个顶点是连通的
度:连接顶点的边数
入度:从其它点进入到A点的边数,称作A的入度,一般称inDegree
出度:从A点进入到其它点的边数,称作A的出度,一般称outDegree
有一条边,从A到B
一般称A为tail(尾节点,起点),用u表示
一般称B为head(头节点,终点),用v表示
有向图时,u和v需要区分,无向图时不需要区分u和v
稠密图:边较多的图
稀疏图:边较少的图
权值:一般用来记录边的长度等,一般称weight

图的常用算法

深搜(DFS)
广搜(BFS)
最小生成树(Prim,Kruskal)
最短路径(Dijkstra,folyd,bellman ford)
拓扑排序(Kahn)

图的数据结构还经常需要另外一个比较简单的数据结构,叫做并查集(union find)

图的存储结构

邻接矩阵:
使用二维数组,n行n列
行表示u,列表示v
对应的位置存放数据,
可以指定u,可以指定v
该数据中必须含有权值
适合稠密图

邻接表:
数组里存储一个链表之类的结构,
n行,列的数量根据节点数量动态添加,
可以指定u,不可以指定v
需要在对应的结构体中额外存放v的信息
该数据中必须含有v、权值
适合稀疏图

有时候边的数据比较少也会直接用一个链表存放所有边信息,
当存在边时往链表中添加一条数据
该数据中必须含有u、v、权值
适合边数据非常小的情况,写起来比较方便

喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论