最近,我在Stackoverflow中问了一个关于从图构建DFS树的问题,并了解到它可以通过使用状态单子简单地实现。
haskell中的DFS
虽然DFS要求仅跟踪访问的节点,以便我们可以使用“设置”或“列表”或某种线性数据结构来跟踪访问的节点,但BFS需要“访问的节点”和“队列”数据结构来完成。
我的BFS伪代码是
Q = empty queue
T = empty Tree
mark all nodes except u as unvisited
while Q is nonempty do
u = deq(Q)
for each vertex v ∈ Adj(u)
if v is not visited
then add edge (u,v) to T
Mark v as visited and enq(v)
从伪代码中可以推断,我们每次迭代只需要做3个过程。
由于我们不使用递归遍历进行BFS搜索,因此我们需要一些其他遍历方法,例如while循环。我在hackage中查找了循环时包,但它似乎有些不推荐使用。
我假设的是,我需要某种这样的代码:
{-...-}
... = evalState (bfs) ((Set.singleton start),[start])
where
neighbors x = Map.findWithDefault [] x adj
bfs =do (vis,x:queue)<-get
map (\neighbor ->
if (Set.member neighbor vis)
then put(vis,queue)
else put ((Set.insert neighbor vis), queue++[neighbor]) >> (addToTree neighbor)
) neighbors x
(vis,queue)<-get
while (length queue > 0)
我知道这种实现是非常错误的,但这应该为我认为BFS应该如何实现提供极简的观点。此外,我真的不知道如何规避对do块使用while循环。(即我应该使用递归算法来克服它还是应该考虑完全不同的策略)
考虑到我在上面链接的上一个问题中找到的一个答案,似乎答案应该是这样的:
newtype Graph a = Graph (Map.Map a [a]) deriving (Ord, Eq, Show)
data Tree a = Tree a [Tree a] deriving (Ord, Eq, Show)
bfs :: (Ord a) => Graph a -> a -> Tree a
bfs (Graph adj) start = evalState (bfs') ((Set.singleton start),[start])
where
bfs' = {-part where I don't know-}
最后,如果由于某种原因(我认为不是),使用状态单变量实现BFS是不可能的,请纠正我的错误假设。
我在Haskell中看到了一些不使用状态单子的BFS的例子,但是我想了解更多关于状态单子是如何处理的,并且找不到任何使用状态单子实现BFS的例子。
提前感谢。
编辑:我用状态单子提出了一些算法,但我陷入了无限循环。
bfs :: (Ord a) => Graph a -> a -> Tree a
bfs (Graph adj) start = evalState (bfs' (Graph adj) start) (Set.singleton start)
bfs' :: (Ord a) => Graph a -> a -> State (Set.Set a) (Tree a)
bfs' (Graph adj) point= do
vis <- get
let neighbors x = Map.findWithDefault [] x adj
let addableNeighbors (x:xs) = if Set.member x vis
then addableNeighbors(xs)
else x:addableNeighbors(xs)
let addVisited (vis) (ns) = Set.union (vis) $ Set.fromList ns
let newVisited = addVisited vis $ addableNeighbors $ neighbors point
put newVisited
return (Tree point $ map (flip evalState newVisited) (map (bfs' (Graph adj)) $ addableNeighbors $ neighbors point))
EDIT2:以一些空间复杂度为代价,我想出了一个解决方案,可以使用图返回和队列处理来获取BFS图。尽管它不是生成BFS树/图的最佳解决方案,但它可以工作。
bfs :: (Ord a) => Graph a -> a -> Graph a
bfs (Graph adj) start = evalState (bfs' (Graph adj) (Graph(Map.empty)) [start]) (Set.singleton start)
bfs':: (Ord a) => Graph a -> Graph a -> [a] -> State (Set.Set a) (Graph a)
bfs' _ (Graph ret) [] = return (Graph ret)
bfs' (Graph adj) (Graph ret) (p:points)= do
vis <- get
let neighbors x = Map.findWithDefault [] x adj
let addableNeighbors ns
| null ns = []
| otherwise = if Set.member (head ns) vis
then addableNeighbors(tail ns)
else (head ns):addableNeighbors(tail ns)
let addVisited (v) (ns) = Set.union (v) $ Set.fromList ns
let unVisited = addableNeighbors $ neighbors p
let newVisited = addVisited vis unVisited
let unionGraph (Graph g1) (Graph g2) = Graph (Map.union g1 g2)
put newVisited
bfs' (Graph adj) (unionGraph (Graph ret) (Graph (Map.singleton p unVisited))) (points ++ unVisited)
EDIT3:我添加了图形到树的转换函数。在EDIT2和EDIT3中运行函数将生成BFS树。在计算时间方面,它不是最好的算法,但我相信对于像我这样的新手来说,它是直观和容易理解的:)
graphToTree :: (Ord a) => Graph a -> a -> Tree a
graphToTree (Graph adj) point = Tree point $ map (graphToTree (Graph adj)) $ neighbors point
where neighbors x = Map.findWithDefault [] x adj
我的解决方案基于逐级工作(与BFS有关),另请参阅此问题和答案。
一般的想法是:假设我们已经知道BFS每个级别之前的访问元素集作为集合列表。然后我们可以逐级遍历图,更新我们的集合列表,在途中构造输出Tree
。
诀窍在于,在这种逐级遍历之后,我们将在每个级别之后获得访问的元素集。这与每个级别之前的列表相同,只是移动了一个。因此,通过绑定结,我们可以使用移位输出作为过程的输入。
import Control.Monad.State
import qualified Data.Map as M
import Data.Maybe (fromMaybe, catMaybes)
import qualified Data.Set as S
import Data.Tree
newtype Graph a = Graph (M.Map a [a])
deriving (Ord, Eq, Show)
tagBfs :: (Ord a) => Graph a -> a -> Maybe (Tree a)
tagBfs (Graph g) s = let (t, sets) = runState (thread s) (S.empty : sets)
in t
where
thread x = do
sets@(s : subsets) <- get
case M.lookup x g of
Just vs | not (S.member x s) -> do
-- recursively create sub-nodes and update the subsets list
let (nodes, subsets') = runState
(catMaybes `liftM` mapM thread vs) subsets
-- put the new combined list of sets
put (S.insert x s : subsets')
-- .. and return the node
return . Just $ Node x nodes
_ -> return Nothing -- node not in the graph, or already visited
在以下示例中运行tagBfs example ple2'b'
it
example2 :: Graph Char
example2 = Graph $ M.fromList
[ ('a', ['b', 'c', 'd'])
, ('b', ['a'])
, ('c', [])
, ('d', [])
]
生产
Just (Node {rootLabel = 'b',
subForest = [Node {rootLabel = 'a',
subForest = [Node {rootLabel = 'c',
subForest = []},
Node {rootLabel = 'd',
subForest = []}
]}
]}
)
将图转换为Tree
广度优先比简单地搜索图广度优先要困难一点。如果您正在搜索图,您只需要从单个分支返回。将图转换为树时,结果需要包括来自多个分支的结果。
我们可以使用比< code>Graph a更通用的类型来搜索或转换成树。我们可以搜索任何具有函数< code>a -的东西或将它们转换成树
breadthFirstSearchUnseen:: Ord r => (a -> r) -> -- how to compare `a`s
(a -> Bool) -> -- where to stop
(a -> [a]) -> -- where you can go from an `a`
[a] -> -- where to start
Maybe [a]
将函数转换为包含最早深度的每个可访问节点的树具有类似于
shortestPathTree :: Ord r => (a -> r) -> -- how to compare `a`s
(a -> l) -- what label to put in the tree
(a -> [a]) -> -- where you can go from an `a`
a -> -- where to start
Tree l
我们可以稍微更一般地从任意数量的节点开始,并构建一个包含每个最早深度可访问节点的 Forest
。
shortestPathTrees :: Ord r => (a -> r) -> -- how to compare `a`s
(a -> l) -- what label to put in the tree
(a -> [a]) -> -- where you can go from an `a`
[a] -> -- where to start
[Tree l]
执行到树的转换并不能真正帮助我们进行搜索,我们可以对原始图形执行广度优先搜索。
import Data.Sequence (viewl, ViewL (..), (><))
import qualified Data.Sequence as Seq
import qualified Data.Set as Set
breadthFirstSearchUnseen:: Ord r => (a -> r) -> (a -> Bool) -> (a -> [a]) -> [a] -> Maybe [a]
breadthFirstSearchUnseen repr p expand = combine Set.empty Seq.empty []
where
combine seen queued ancestors unseen =
go
(seen `Set.union` (Set.fromList . map repr $ unseen))
(queued >< (Seq.fromList . map ((,) ancestors) $ unseen))
go seen queue =
case viewl queue of
EmptyL -> Nothing
(ancestors, a) :< queued ->
if p a
then Just . reverse $ ancestors'
else combine seen queued ancestors' unseen
where
ancestors' = a:ancestors
unseen = filter (flip Set.notMember seen . repr) . expand $ a
在上面的搜索算法中维护的状态是一个 Seq
队列,其中包含接下来要访问的节点和一组
已看到的节点。如果我们跟踪已经访问过的节点,那么如果我们找到多个路径到相同深度的节点,我们可以多次访问同一节点。在我写这个广度第一次搜索的答案中有一个更完整的解释。
根据我们的一般搜索,我们可以轻松编写搜索<code>图
import qualified Data.Map as Map
newtype Graph a = Graph (Map.Map a [a]) deriving (Ord, Eq, Show)
bfsGraph :: (Ord a) => Graph a -> (a -> Bool) -> [a] -> Maybe [a]
bfsGraph (Graph adj) test = breadthFirstSearchUnseen id test ((Map.!) adj)
我们也可以自己写如何搜索树
。
import Data.Tree
bfsTrees :: (Ord a) => (a -> Bool) -> [Tree a] -> Maybe [a]
bfsTrees test = fmap (map rootLabel) . breadthFirstSearchUnseen rootLabel (test . rootLabel) subForest
以广度优先建造树木要困难得多。幸运的是数据。树
已经提供了从一元展开按广度优先顺序构建<code>树的方法。广度优先顺序将负责排队,我们只需要跟踪我们已经看到的节点的状态。
unfoldTreeM_BF
的类型为Monad m=
expandUnseen :: Ord r => (a -> r) -> (a -> l) -> (a -> [a]) -> a -> State (Set.Set r) (l, [a])
expandUnseen repr label expand a = do
seen <- get
let unseen = filter (flip Set.notMember seen . repr) . uniqueBy repr . expand $ a
put . Set.union seen . Set.fromList . map repr $ unseen
return (label a, unseen)
为了构建树,我们运行由unfoldForestM_BF构建的状态计算
。
shortestPathTrees :: Ord r => (a -> r) -> (a -> l) -> (a -> [a]) -> [a] -> [Tree l]
shortestPathTrees repr label expand = run . unfoldForestM_BF k . uniqueBy repr
where
run = flip evalState Set.empty
k = expandUnseen repr label expand
<code>uniqueBy</code>是一个<code>nubBy</code>利用<code>Ord</code>实例,而不是<code>Eq</code>。
uniqueBy :: Ord r => (a -> r) -> [a] -> [a]
uniqueBy repr = go Set.empty
where
go seen [] = []
go seen (x:xs) =
if Set.member (repr x) seen
then go seen xs
else x:go (Set.insert (repr x) seen) xs
我们可以根据一般的最短路径树构建从
Graph
s 编写构建最短路径树
shortestPathsGraph :: Ord a => Graph a -> [a] -> [Tree a]
shortestPathsGraph (Graph adj) = shortestPathTrees id id ((Map.!) adj)
我们可以将
Forest
过滤为仅通过Forest
的最短路径。
shortestPathsTree :: Ord a => [Tree a] -> [Tree a]
shortestPathsTree = shortestPathTrees rootLabel rootLabel subForest
主要内容:深度优先搜索(简称“深搜”或DFS),广度优先搜索,总结前边介绍了有关图的 4 种存储方式,本节介绍如何对存储的图中的顶点进行遍历。常用的遍历方式有两种: 深度优先搜索和 广度优先搜索。 深度优先搜索(简称“深搜”或DFS) 图 1 无向图 深度优先搜索的过程类似于树的先序遍历,首先从例子中体会深度优先搜索。例如图 1 是一个无向图,采用深度优先算法遍历这个图的过程为: 首先任意找一个未被遍历过的顶点,例如从 V1 开始,由于 V1 率先访问过了,所以
在有向图的广度优先搜索(可能的循环)中,当一个节点退出队列时,其所有尚未访问的子节点都将进入队列,并且该过程将继续,直到队列为空为止。 有一次,我以另一种方式实现它,其中节点的所有子节点都排队,当节点出队时,检查访问状态。如果之前访问过正在退出队列的节点,则该节点将被丢弃,并继续到队列中的下一个节点。 但结果是错的。维基百科还说 深度优先搜索。。。。。。非递归实现类似于广度优先搜索,但在两个方面与
我正在研究BFS算法,我有一个关于如何将相邻节点插入队列的问题。 例如,假设我们正在处理一个无向图,我们希望执行BFS来输出图的内容,那么我们如何知道在从队列中取出一个初始节点后,相邻节点以什么顺序插入到队列中呢?还有,有没有办法修改邻居节点插入队列的方式? 任何帮助都将不胜感激,谢谢。
本文向大家介绍Javascript中的广度优先搜索遍历,包括了Javascript中的广度优先搜索遍历的使用技巧和注意事项,需要的朋友参考一下 BFS在访问子顶点之前先访问邻居顶点,并且在搜索过程中使用队列。以下是BFS的工作方式- 访问相邻的未访问顶点。将其标记为已访问。显示它。将其插入队列。 如果找不到相邻的顶点,请从队列中删除第一个顶点。 重复规则1和规则2,直到队列为空。 让我们看一下BF
我有一个无向连通图。我使用邻接矩阵实现了它,它是一个2维数组。 据我所知,DFS在兄弟节点之前访问子节点。BFS先于孩子探望兄弟姐妹。 这两个我是这样实现的: 如果让我执行一个从D到E的DFS,是D、C、a、E还是D、E。我以为DFS和BFS必须访问每个节点,在这种情况下B不能访问。我不知道我应该如何改变我目前的方法来满足这些要求。
我在处理一个单词搜索问题。我正确地实现了dfs搜索,但在其他地方有一些琐碎的错误。