在计算中,常将运算方程或实验结果绘制成由若干有标尺的线条所组成的图,称为“算图”。计算时根据已知条件,从有关线段上一点开始,连结相关线段上的点,连线与表示所求量线段的交点即为答案。
无向图、有向图和网络能运用很多常用的图算法。这些算法包括:各种遍历算法(这些遍历类似于树的遍历),寻找最短路径的算法,寻找网络中最低代价路径的算法,用于回答一些简单相关问题例如,图是否是连通的,图中两个顶点间的最短路径是什么,等等。
(1)图的遍历
图的遍历是指从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。图的遍历操作是图的一种基本操作,图的许多操作都建立在遍历操作的基础之上。
在遍历图时,为保证图中各顶点在遍历的过程中访问且仅一次,需要为每个顶点设计一个访问标记,设置一个数组,用于标示图中每个顶点被访问过,它的初始值全部为0,表示顶点均未被访问过;某个顶点被访问后,将相应访问标志数组中的值设为1,以表示该顶点已经被访问过。
通常,图的遍历有两种:深度优先遍历搜索和广度优先遍历搜索。
(2)最小生成树
对于有n个顶点的无向连通图,至少有n-1条边,而生成树恰好有n-1条边,所以生成树是图的极小连通子图。如果无向连通图是一个网,那么它的所有生成树中必有一棵边的权值总和最小的生成树,称这颗生成树为最小生成树。
最小生成树可以用普里姆算法或克鲁斯卡尔算法求出。
(3)最短路径
(1)问题描述
给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
(2)Bellman-Ford算法
Dijkstra算法无法判断含负权边的图的最短路。如果遇到负权,在没有负权回路(回路的权值和为负,即便有负权的边)存在时,也可以采用Bellman-Ford算法正确求出最短路径。
Bellman-Ford算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题。对于给定的带权(有向或无向)图 G=(V,E), 其源点为s,加权函数 w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值,表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路,算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E)
算法描述:
该函数使用Bellman-Ford算法实现。
(1)语法
graph_sssp( vertex_table,
vertex_id,
edge_table,
edge_args,
source_vertex,
out_table
)
(2)参数
vertex_table:TEXT类型,包含图中顶点数据的表名。
vertex_id:TEXT类型,缺省值为‘id’,vertex_table表中包含顶点的列名。顶点列必须是INTEGER类型,并且数据不能重复,但不要求连续。
edge_table:TEXT类型,包含边数据的表名。边表必须包含源顶点、目标顶点和边长三列。边表中允许出现回路,并且构成回路的权重可以不同。
edge_args:TEXT类型,是一个逗号分隔字符串,包含多个“name=value”形式的参数,支持的参数如下:
source_vertex:INTEGER类型,算法的起始顶点。此顶点必须在vertex_table表的vertex_id列中存在。
out_table:TEXT类型,存储单源最短路径的表名,表中的每一行对应一个vertex_table表中的顶点,具有以下列:
路径检索函数返回从源顶点到指定目标顶点的最短路径。
(1)语法
graph_sssp( sssp_table,
dest_vertex
)
(2)参数
sssp_table:TEXT类型,单源最短路径函数的输出表名。
dest_vertex:INTEGER类型,指定目标顶点。
单源最短路径问题是图算法的经典问题,在现实中有很多应用,比如在地图中找出两个点之间的最短距离、最小运费等。社交网络中出现的“六度人脉”功能,可以查看到一个用户和一个陌生人之间可以通过哪几个人认识,也就是所谓的六度关系。这个问题也可抽象为一个单源最短路径问题。将用户作为顶点,用户之间的好友关系作为边,“六度关系”就是两个用户之间的最短路径。在这个特殊场景下,所有边的权重都可认为是1。当然,如果用户量巨大,用户好友关系将变得非常复杂,单纯的最短路径算法可能存在性能问题,需要进行改进与优化。
drop table if exists vertex, edge;
create table vertex(
id integer
);
create table edge(
src integer,
dest integer,
weight float8
);
insert into vertex values
(0),
(1),
(2),
(3),
(4),
(5),
(6),
(7);
insert into edge values
(0, 1, 1.0),
(0, 2, 1.0),
(0, 4, 10.0),
(1, 2, 2.0),
(1, 3, 10.0),
(2, 3, 1.0),
(2, 5, 1.0),
(2, 6, 3.0),
(3, 0, 1.0),
(4, 0, -2.0),
(5, 6, 1.0),
(6, 7, 1.0);
drop table if exists out;
select madlib.graph_sssp(
'vertex', -- 顶点表
null, -- 顶点列名,这里使用缺省值‘id’
'edge', -- 边表
null, -- 边参数,这里全部使用缺省列名
0, -- 计算最短路径的起始顶点
'out'); -- 输出表名
select * from out order by id;
查询结果如下:
id | weight | parent
----+--------+--------
0 | 0 | 0
1 | 1 | 0
2 | 1 | 0
3 | 2 | 2
4 | 10 | 0
5 | 2 | 2
6 | 3 | 5
7 | 4 | 6
(8 rows)
select madlib.graph_sssp_get_path('out',6) as spath;
结果:
spath
-----------
{0,2,5,6}
(1 row)
drop table if exists vertex_alt, edge_alt;
create table vertex_alt as select id as v_id from vertex;
create table edge_alt as select src as e_src, dest, weight as e_weight from edge;
drop table if exists out_alt;
select madlib.graph_sssp(
'vertex_alt', -- 顶点表
'v_id', -- 顶点列名
'edge_alt', -- 边表
'src=e_src, weight=e_weight', -- 边参数,指定顶点和边长的列名
1, -- 计算最短路径的起始顶点
'out_alt'); -- 输出表名
select * from out_alt order by v_id;
结果:
v_id | e_weight | parent
------+----------+--------
0 | 4 | 3
1 | 0 | 1
2 | 2 | 1
3 | 3 | 2
4 | 14 | 0
5 | 3 | 2
6 | 4 | 5
7 | 5 | 6
(8 rows)