主页 / 问题 / 609408
Accepted
m9_psy
Asked:2020-12-30 07:49:00 +0000 UTC2020-12-30 07:49:00 +0000 UTC

查找完整图形的缺失弧

  • 772

给定一个表，其中列出了连通有向图的所有弧。表中有两个数字字段，第一个包含弧的起始顶点，第二个 - 结束顶点。

必需的：

编写一个返回弧列表的 SQL 查询，添加弧列表后图形将变得完整。

首先是测试表的代码（Postgresql）：

CREATE TEMPORARY TABLE graph
(
    start_point INTEGER NOT NULL,
    end_point INTEGER NOT NULL
)
ON COMMIT DROP;

INSERT INTO graph VALUES
(1,2),
(1,4),
(2,3),
(3,4);

实际上，我的解决方案： 

-- Для начала нужно получить список всех-всех дуг для данного графа
WITH a AS (
WITH points AS(
    -- Получаем все вершины, преобразовывем в массив
    SELECT array(SELECT DISTINCT start_point FROM graph ORDER BY start_point) ||
           array(SELECT DISTINCT end_point FROM graph ORDER BY end_point)
     AS allp FROM student
     LIMIT 1
)
    SELECT DISTINCT i
    FROM unnest ((SELECT * FROM points)) AS s(i)
),
all_possible_edges AS(
SELECT *
FROM
    -- И затем все эти вершины комбинируем друг с другом
    a CROSS JOIN a AS b
WHERE
    -- Это условие означает, что пропускаем 1-1. Также оно означает, что будет только дуга 1-2, но не 2-1
    -- Хотя эти дуги одинаковы по смыслу
    a < b
ORDER BY a, b
)
-- Ну и наконец берем только те дуги, которые есть в комбинациях, но которых нет в оригинальной таблице
SELECT * FROM all_possible_edges EXCEPT SELECT * FROM graph

回答：

>> 2;4
>> 1;3

问题是我不禁觉得解决方案过于复杂。数组的大惊小怪看起来特别恶心。有没有更简单的方法来解决问题？

mysql

1 个回答

  1. Best Answer

    对于 postgersql

    WITH ps AS (
SELECT /* DISTINCT */ start_point AS point FROM graph
UNION /* DISTINCT */
SELECT /* DISTINCT */ end_point FROM graph
),
pe AS (
SELECT /* DISTINCT */ start_point AS point FROM graph
UNION /* DISTINCT */
SELECT /* DISTINCT */ end_point FROM graph
)
SELECT ps.point start_point, pe.point end_point
FROM ps, pe
WHERE ps.point != pe.point
EXCEPT 
SELECT start_point, end_point
FROM graph;

    http://www.sqlfiddle.com/#!15/6ef70/3/0

    对于 MySQL

    SELECT ps.point start_point, pe.point end_point
FROM (
SELECT /* DISTINCT */ start_point AS point FROM graph
UNION /* DISTINCT */
SELECT /* DISTINCT */ end_point FROM graph
) ps, (
SELECT /* DISTINCT */ start_point AS point FROM graph
UNION /* DISTINCT */
SELECT /* DISTINCT */ end_point FROM graph
) pe
WHERE ps.point != pe.point
AND (ps.point, pe.point) NOT IN
(SELECT start_point, end_point
FROM graph);

    http://www.sqlfiddle.com/#!9/6ef708/4/0

    • 1

相关问题