CODEWITHSUNDEEP
c++performancedata-structuresgraph
danijar
danijar

Reputation: 34175

Datastructure for undirected graph edges with constant time complexity

I have a undirected graph where the nodes are stored in a flat array. Now I am looking for a data structure for the edges. It should have constant time complexity for getting all edges of a given node. An edge contains two node indices and additional information such as a weight.

The only way I see is duplicating the data, one sorted by the left node and another sorted by the right node.

vector<vector<int>> left, right;

But I would like to prevent duplicating the edges.

Upvotes: 1

Views: 620

Answers (2)

MoonBun
MoonBun

Reputation: 4402

Make a vector of vectors.

Each node will have a vector of all the nodes it has.

You should build this during the graph creation.

Upvotes: 1

Bernhard Barker
Bernhard Barker

Reputation: 55589

It sounds like you just want an adjacency list representation.

In this representation, each node would store a list of all its connected edges.

For an undirected graph, you can have each endpoint both store the edge.

There isn't really a way to get the connected edges for a node in constant time without some duplication. But you can just store a pointer, reference or unique ID (which can be an index in an edge array, for example) to the actual edge, preventing the need to actually have 2 copies of it floating around.

Upvotes: 3

Related Questions