# Problem 87b

Extract nodes from a graph into a list in breadth-first order, without repeating any nodes.

## Example ``````
breadthFirst 'c' graph == ['c', 'b', 'f', 'g', 'k', 'h']
``````

## Unit Test

``````import Html
import List
import Set
import String

{-| A node has a value, degree and a color
-}
type alias Edge comparable =
( comparable, comparable )

type alias Graph comparable =
( List comparable, List (Edge comparable) )

{-| Given a graph and a starting node, return all nodes in breadth-first order.
-}
breadthFirst : comparable -> Graph comparable -> List comparable
breadthFirst start ( nodes, edges ) =
-- your implementation goes here
[]

main : Html.Html a
main =
Html.text
<| case test of
0 ->
"Your implementation passed all tests."

1 ->
"Your implementation failed one test."

x ->
"Your implementation failed " ++ (toString x) ++ " tests."

test : Int
test =
List.length
<| List.filter ((==) False)
[ String.fromList (breadthFirst 'a' graph87) == "abdc"
, String.fromList (breadthFirst 'g' graph80) == "gh"
, String.fromList (breadthFirst 'h' graph80) == "hg"
, String.fromList (breadthFirst 'g' graph84) == "gbcfkh"
, String.fromList (breadthFirst 'c' graph84) == "cbfghk"
, String.fromList (breadthFirst 'f' graph84) == "fbcghk"
, String.fromList (breadthFirst 'h' graph84) == "hgbcfk"
, String.fromList (breadthFirst 'k' graph84) == "kfbcgh"
, String.fromList (breadthFirst 'b' graph80) == "bcfk"
, String.fromList (breadthFirst 'c' graph80) == "cbfk"
, String.fromList (breadthFirst 'f' graph80) == "fbck"
, String.fromList (breadthFirst 'k' graph80) == "kfbc"
, String.fromList (breadthFirst 'k' graph80) == "kfbc"
, String.fromList (breadthFirst 'g' graph81) == "gh"
, String.fromList (breadthFirst 'h' graph81) == "hg"
-- either ordering is acceptable
, List.member (String.fromList (breadthFirst 'b' graph84)) [ "bcfgkh", "bcfghk" ]
]

graph80 =
( [ 'b', 'c', 'd', 'f', 'g', 'h', 'k' ]
, [ ( 'b', 'c' )
, ( 'b', 'f' )
, ( 'c', 'f' )
, ( 'f', 'k' )
, ( 'g', 'h' )
]
)

graph81 =
-- has a loop and parallel edges
( [ 'b', 'c', 'd', 'f', 'g', 'h', 'k' ]
, [ ( 'b', 'c' )
, ( 'b', 'f' )
, ( 'c', 'f' )
, ( 'f', 'k' )
, ( 'g', 'h' )
, ( 'g', 'h' )
, ( 'g', 'g' )
]
)

graph84 =
( [ 'b', 'c', 'd', 'f', 'g', 'h', 'k' ]
, [ ( 'b', 'c' )
, ( 'b', 'f' )
, ( 'b', 'g' )
, ( 'c', 'f' )
, ( 'f', 'g' )
, ( 'f', 'k' )
, ( 'g', 'h' )
]
)

{-| Simple graph, in dfs - "abdc", in bfs "abcd"
-}
graph87 =
( [ 'a', 'b', 'c', 'd' ]
, [ ( 'a', 'b' )
, ( 'a', 'c' )
, ( 'b', 'd' )
]
)
``````

# Hint

1. A small modification to the depth-first graph search can resolve solve this problem.

Solution