Graphs

[simonsan]

I think Graph data structure, on its own, is too wide topic to cover in a couple of pages. As a rule, complexity of algorithms on graphs directly depends their representation. What kind of representation we will choose depends on our use case. Factors to take into account:

• type of graphs: complete graph, trees, directed, undirected, etc.
• compute intensive: speed/complexity of algorithms is important, for example depending on representation DFS algorithm may work in O(n^2) or O(n + m).
• scarce memory (embedded systems for example)
• what kind of algorithm we implement: parallel, distributed...
• Is graph dynamic?: we constantly add/remove vertices/edges...
• amortised cost: for example amortised costs are given in documentations for some data structures.

Let me give a simple example. Say, I know my graph changes (new edges or vertex) once a day, but the graph is almost complete and in my algorithms I traverse neighbours of a single vertex not too often. I'd probably use adjacency matrix.

Or another example. If we know that our graph has too few edges and we do extensive DFS then matrix is a bad choice since it would have O(n^2) complexity, while using adj list we could reduce it to linear time O(n) if say m is linear in n.

Originally posted by @fade2black in https://github.com/rust-unofficial/patterns/issues/68#issuecomment-760524218

[simonsan]

Closed #68 to focus on discussing the topic here, may be reopened later to use it as a basis for a general Graphs intro.md, not sure.