kruskal implement in c adjacency list or adjacency matrix

Question

I am reading the textbook Introduction to Algorithms aka CLRS, I want to implement the mst using kruskal algorithm in c, what I want to know is, which graph implementation should I use, the adjacency list or adjacency matrix? I think it is not intuitive to sort the edges when using the adjacency list, the represent of edge in adjacency list is confusing when define the adjacency list like this:

typedef struct tagAdjList
{
    int endPointIndex;
    struct tagAdjList * next;
}AdjNode, *AdjList, *AdjPNode;

when sorting the edges, I want to using an array of pointers to pointing to the nodes defined above, the question is the struct defined above can't find the start point of the edge but the end point. So I changed the struct like this:

typedef struct tagAdjList
{
    int startPointIndex;
    int endPointIndex;
    struct tagAdjList * next;
}AdjNode, *AdjList, *AdjPNode;

what I want to ask is: is OK to define the adjancency list like this? or there are better practice? or I just should use the adjacency matrix(since I saw some people implement the kruskal using the matrix when searching the Internet)? why? Sorry for the poor English. any help will be appreciated.

Answer 1

For the purposes of implementing Kruskal's algorithm it does not matter in what way you represent your graph, because you never sort edges that belong to a vertex. Rather, you put all edges into a single array, and then sort that array in ascending order.

The representation of your graph does not matter, as long as you can walk it, and collect all edges into a single array (first, you walk the graph to count the edges, then allocate an array of sufficient capacity, and finally you walk the graph again, putting pointers to the edges into the dynamically allocated array).

Once the pointers to your edges are in an array, sort the array (for example, with qsort) and run Kruskal's algorithm. You will need to implement Disjoint Sets in order to merge forests efficiently; as long as you have no trouble implementing linked lists, implementing disjoint sets should give you absolutely no trouble.

Answer 2

The first structure you mention is the standard representation of (sparse) graphs. Note that you will need a weight field as well. I would keep this as the permanent representation of the graph, as long as it is sparse at least.

Yes, for Kruskal's you'll need a structure more like the latter as you need an explicit source vertex. I would define a different structure that doesn't have the linked list just for Kruskal's:

int startPointIndex;
int endPointIndex;
int weight;

You'll allocate an array of those structures, fill them in with the edges from the graph, sort them by weight, then scan through them doing disjoint set unions of the endpoints.