❔ Best data structure for graph?
I need to represent a directed graph, and I’m going to need to very rapidly do various operations when something happens at one node/vertex. I could represent my graph with Dictionaries, but is there a better way?
Q: What data structures are most appropriate to work with graphs?
8 Replies
Is there a type/class I should look into?
there isn't any built-in type for graphs, if that's what you're asking
why wouldn't you just model a
GraphNode that contains some data, plus a collection of pointers to other nodes?graph can be really diverse, so usually the storing approach depends on what algorithms you will run on it
a jagged array could be a start, but again there are many ways
thanks. That’s really what I was asking.
My current thought was something along the lines of:
public struct Node {…}
public class Graph {
public Dictionary<Node, List<Node>> edgeSet;
… graph-related methods}
I was mostly curious if there is a dat structure that might be more optimal
grapg is basically linked list pointing at both directions
You can represent a directed graph as an adjacency matrix. All nodes are in a list or array with length M and the MxM matrix will represent the edges between those nodes.
which would be a pretty space-inefficient representation, for large graphs, but would be highly efficient for traversal and manipulation
that DOES point out another representation you could use though
if each node has something like an ID that can be used as a key, you can build the graph as a
HashSet<> or Dictionary<> containing the directed edges as key pairs
or you can just use the object reference itself as the key, as long as you maintain reference integrity for the nodes, when building the edgesWas this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.