CODEWITHSUNDEEP
clistgraph
stefideltz
stefideltz

Reputation: 39

How can I represent edges for a graph in terms of a list?

How can we represent a graph as a list of edges?

Upvotes: 3

Views: 4899

Answers (3)

gcbenison
gcbenison

Reputation: 11963

Unless you really want to implement the representation yourself, as a learning exercise or to have more control, consider using a library such as igraph which is a C library for representing and manipulating graphs. Or go one abstraction level down - build adjacency lists or edge lists yourself, but use the list-building capabilities of glib rather than rolling your own.

Upvotes: 0

shybovycha
shybovycha

Reputation: 12225

If you wanna store exactly edges, use matrix of weights: int** M;, where M[i][t] is the length of the edge between i and t vertices.

If your graph edges have weight of 1, you could store graph in adjacency matrix, where M[i][t] equals to:

  • 0 if there is no edges between i and t vertices
  • 1 if there is edge from i to t
  • alpha if i == t and there is a loop in i (or t) vertex

If you requre structure, critical for memory usage, store your graph in the linked list, where each vertex has structure:

struct Vertex
{
  int N;
  Vertex* next;
};

So you would have array of Vertex structures, each containing pointer to the next it is connected to. For example, here is some linked-list-graph:

  • 1 -> 3 -> 4
  • 2 -> 5
  • 3 -> 4
  • 4 -> 3
  • 5 -> 2

Upvotes: 1

Peter Alexander
Peter Alexander

Reputation: 54270

There's three common ways of doing this:

  1. Adjacency matrix: A V * V table of edge weights, where the ith column on the jth row is the weight of the edge between vertices i and j. If there is no edge, infinity is often used (or you can use some sentinel value, like -1).

  2. Adjacency lists: An array of V linked lists. Each ith list in the array is a list of edges leaving the ith vertice.

  3. Edge list: Simply a list of tuples (u, v) of edges.

Different ones are suitable for different purposes. Personally I find the adjacency lists to be the most useful, but if you have a very dense graph then an adjacency matrix can improvement performance and memory usage.

Upvotes: 6

Related Questions