Haskell中简单图的表示及自定义带类型变量的Graph构造器实现疑问

你目前的data Graph a = Void | Vertex a [Graph a]本质是玫瑰树（多叉树）的定义，只能表达无环、节点不共享的层级结构，无法适配通用图的需求：图允许存在环、也允许多个顶点指向同一个顶点，递归ADT的结构天然很难处理这类共享和循环引用的场景，也没法直接对应你认知里「顶点列表+边列表」的存储逻辑。

下面是两种通用的带类型参数a的图实现思路： #

1. 邻接表实现（最接近Data.Graph的设计逻辑） #

这种实现用独立的VertexId保证顶点的唯一性，把顶点携带的值、邻接关系分开存储，是工业界最常用的实现方式：

import qualified Data.Map as Map
import qualified Data.Set as Set

type VertexId = Int
type Edge = (VertexId, VertexId)

data Graph a = Graph
  { nextVertexId :: VertexId       -- 下一个可分配的顶点ID，方便新增顶点
  , vertexVals :: Map.Map VertexId a  -- 存储顶点ID对应的值
  , adjList :: Map.Map VertexId (Set.Set VertexId) -- 存储每个顶点的邻接ID集合
  } deriving (Eq, Show)

配套的基础操作示例：

-- 初始化空图
empty :: Graph a
empty = Graph 0 Map.empty Map.empty

-- 新增顶点，返回新图和新顶点的ID
addVertex :: a -> Graph a -> (Graph a, VertexId)
addVertex val (Graph next vMap adj) =
  ( Graph (next + 1) (Map.insert next val vMap) (Map.insert next Set.empty adj)
  , next
  )

-- 新增有向边 from -> to
addEdge :: Edge -> Graph a -> Graph a
addEdge (from, to) g =
  g { adjList = Map.adjust (Set.insert to) from (adjList g) }

-- 新增无向边
addUndirectedEdge :: Edge -> Graph a -> Graph a
addUndirectedEdge (u, v) = addEdge (u, v) . addEdge (v, u)

2. 顶点列表+边列表实现（完全匹配你认知的存储逻辑） #

如果你不需要频繁查询邻接关系，也可以直接用最直观的结构存储：

data Graph a = Graph
  { vertices :: [a]
  , edges :: [(a, a)]
  } deriving (Eq, Show)

这种实现要求a类型实现Eq类型类，才能正确判断顶点的同一性，比如查询邻居的函数需要加约束：

neighbors :: Eq a => a -> Graph a -> [a]
neighbors v g = [y | (x, y) <- edges g, x == v]

这种方式的缺点是查询、去重的效率较低，只适合小图场景。

内容的提问来源于stack exchange，提问作者AwhatLoop