图搜索算法失败

Question

我试图修改我的代码，该代码使用 Graph a 来查找连接到顶点 n 的任何顶点。这里连接的定义是顶点 m 直接连接到顶点 n（通过边）或连接到顶点 k，后者又连接到顶点 n .

我要修改的代码

-- ** Code 1 **

findPath :: Eq a => Graph a -> a -> [a]
findPath (Graph v w) a
    | [x | x<-v, x==a] == [] = []
    | otherwise = findPath' (Graph v w) [a]

findPath' :: Eq a => Graph a -> [a] -> [a]
findPath' (Graph [] _) _ = []
findPath' (Graph _ _) [] = []
findPath' (Graph v w) (tp:st)
    | [x | x<-v, x==tp] == [] = findPath' (Graph vv w) st
    | otherwise = tp : findPath' (Graph vv w) (adjacent ++ st)
    where
        adjacent = [x | (x,y)<-w, y==tp] ++ [x | (y,x)<-w, y==tp]
        vv = [x | x<-v, x/=tp]

connected :: Eq a => Graph a -> a -> a -> Bool
connected g a b =  if (a `elem` (findPath g b)) == True then True else False

我的修改尝试

-- **Code 2**

convert :: [a] -> [(a, a)]
convert [] = []
convert (k:v:t) = (k, v) : convert t


-- a is vertex
-- [a] is a list from neighbors
getEdges :: Eq a => a -> [a] -> [a]
getEdges _ [] = []
getEdges a (y:ys) = a : y : getEdges a ys


-- vertices :: Eq a => Graph a -> [a]
-- neighbors :: Eq a => Graph a -> a -> [a]
-- [a] is a list of vertex
mergeEdges :: Eq a => Graph a -> [a] -> [a]
mergeEdges _ [] = []
mergeEdges g (x:xs) = getEdges x (neighbors g x) ++ mergeEdges g xs

removeElements :: Eq a => [(a,a)] -> [(a,a)]
removeElements [] = []
removeElements ((a,b) : (v,w) : xs) =  [(a,b)] ++ removeElements xs

--v = vertex, w = edges
findPath :: Eq a => [a] -> [(a,a)] -> a -> [a]
findPath v w a
    | [x | x<-v, x==a] == [] = []
    | otherwise = findPath' v w [a]

--v = vertex, w = edges
findPath' :: Eq a => [a] -> [(a,a)] -> [a] -> [a]
findPath' [] _ _ = []
findPath' _ _ [] = []
findPath' v w (tp:st)
    | [x | x<-v, x==tp] == [] = findPath' vv w st
    | otherwise = tp : findPath' vv w (adjacent ++ st)
    where
        adjacent = [x | (x, y)<-w, y==tp] ++ [x | (y,x)<-w, y==tp]
        vv = [x | x<-v, x/=tp]

getParam :: Eq a => Graph a -> [(a,a)]
getParam g = removeElements ((convert(mergeEdges g (vertices g))))


connected :: Eq a => Graph a -> a -> a -> Bool
connected g a b = if (a `elem` (findPath (vertices g) (getParam g) b ) ) == True then True else False

测试代码

这是我的图表：Graph {vers = [-6,-3,5,3], edgs = [(-6,5),(3,-3),(-3,5)]}

代码 1：

ghci> connected g 3 5
True

代码 2：

ghci> connected g 3 5
False

我最好的猜测是，当我将参数从图 a 更改为元组列表 [(a,a)] 时，我的代码在这里停止工作，但我不明白为什么：

| otherwise = tp : findPath' vv w (adjacent ++ st)
where
    adjacent = [x | (x, y)<-w, y==tp] ++ [x | (y,x)<-w, y==tp]

我不能使用图 a, (..) 中的构造函数，因为它是不允许的:-( 因此我需要修改我的代码。

添加附加代码

data Graph a = Graph {
  vers :: [Vertex a],
  edgs    :: [Edge a]
} deriving (Show, Eq, Read)

neighbors :: Eq a => Graph a -> a -> [a]
neighbors (Graph x []) _ = []
neighbors (Graph x ((v, w) : xs)) a
     | a == v = w : neighbors (Graph x xs) a
     | a == w = v : neighbors (Graph x xs) a
     | (v, w) : xs == [] = []
     | otherwise = neighbors (Graph x xs) a

Answer 1

当我运行你 getParam 在你的示例输入 Graph {vers = [-6,-3,5,3], edgs = [(-6,5),(3,-3),(-3,5)]} 上运行时，我得到：

ghci> getParam g
[(-6,5),(-3,5),(5,-3)]

这里可以看到边(-3,5)和(5,-3)重复了，边(3,-3)消失了。所以，我认为你的 removeElements 功能太简单了。您也许可以尝试先对元组进行排序然后删除重复项的函数：

import Data.List (nub)

...

sortTuple :: Ord a => (a, a) -> (a, a)
sortTuple (x, y)
  | x <= y = (x, y)
  | otherwise = (y, x)

removeElements :: Ord a => [(a, a)] -> [(a, a)]
removeElements xs = nub (map sortTuple xs)

-- also change the types of some other functions:
getParam :: Ord a => Graph a -> [(a,a)]
connected :: Ord a => Graph a -> a -> a -> Bool

使用该函数我得到 getParam g == [(-6,5),(-3,3),(-3,5)] 和 connected g 3 5 == True.

但我还想知道你为什么不直接使用 getParams g = edgs g？

图搜索算法失败

Graph search algorithm fails

haskell

我要修改的代码

我的修改尝试

测试代码

添加附加代码