How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?

When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge (i, j) just stored in the list of edges of i or on the list of edges of j. Other times, it's important to have an (i, j) on i and a (j, i) on j.

I was wondering how do you call graph representations of one type and graph representations of the other type? Without concrete names to give to each one of them, code or even conversations about certain algorithms get confusing really fast.

Your second kind of representation is simply called the adjacency list representation. It's a standard representation for graph data structures.

To my knowledge, there is no standard name for your first kind of representation; it's a weird and non-standard kind of representation. That's probably because it's not sufficient for most algorithms on undirected graphs (most algorithms require more), whereas the adjacency list representation is sufficient for most algorithms on undirected graphs. So, it would be rare to find situations where your first kind of representation is sufficient and useful.

You say that your first kind of representation is sufficient for Kruskal's algorithm, but this might be a bit misleading. In fact, Kruskal's algorithm is fine with something even more minimal: merely having a list of all edges is sufficient for Kruskal's algorithm. In other words, Kruskal's algorithm does not require the edge (i,j) to be associated with either i or j (it's OK if it's not associated with either, as long as you have a list of all edges).

In general, your first kind of representation does not seem like a natural choice for any graph algorithm that I can think of right now, so it's not surprising if it doesn't have a standard name.

StackExchange Computer Science Q#43290, answer score: 2