What are the easiest ways to represent edges for a graph? I mean the list? in the programming language C

Question

how can we represent a graph as a list of edges? in programming in C?

Answer 1

There are three general ways to do this:

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

• Additivity Lists: An array of V linked lists. Each i-th list in the array is a list of edges that leave the i-th vertex.

• List of edges: just a list of tuples of (u, v) edges.

Different are suitable for different purposes. Personally, I think adjacency lists are the most useful, but if you have a very tight graph, adjacency matrix can improve performance and memory usage.

Answer 2

If you want to keep exactly the edges, use the weight matrix: int** M; , where M[i][t] is the length of the edge between i and t vertices.

If your graph graphs have a weight of 1, you can save the graph in the adjacency matrix, where M[i][t] is:

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

If you request a structure critical to memory usage, save your graph in a linked list, where each vertex has a structure:

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

So, you will have an array of Vertex structures, each of which contains a pointer to the next one to which it is connected. For example, here is a list of linked lists:

• 1 → 3 → 4
• 2 → 5
• 3 → 4
• 4 → 3
• 5 → 2

Answer 3

If you really do not want to implement the presentation yourself, as a training exercise or for more control, consider using a library such as igraph which is a C library for presenting and processing charts. Or go into one level of abstraction - create adjacency lists or edge lists yourself, but use the glib features instead.