Блог пользователя gdka

Автор gdka, история, 8 лет назад, По-английски

Hi,

I'm starting to solve problems in codeforces with Haskell. But I have had obstacles with the way to represent a graph. How can I do it efficiently?

Thanks :]

  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

You can basically do the same thing you would do in C++ or Java, so if you have a simple directed graph, an adjacency list representation could be adjList :: Array Int [Int], so for every vertex v, adjList ! v is the list of its adjacent vertices.

In fact, this type of graph representation is provided in the module Data.Graph (link), which is part of the containers package and can be used on Codeforces. That module even provides implementations of some graph algorithms out of the box, including topological sorting and finding BCCs.

In general though, Haskell is probably not the best suited language for graph algorithms, because many of them rely heavily on mutable data structures and are rather imperative in nature, which doesn't really fit Haskell's purely functional style.

So if your graph problem happens to be solvable using just Data.Graph you can use that, otherwise you might be better off using a different language instead. (That being said, you certainly can do it in Haskell, but for this you might want to read up on mutable arrays in Haskell).