Minimum Spanning Tree using Prim's algorithm

I have implemented a Minimum Spanning Tree using Prim's Algorithm. Could someone give some about some improvements for code structure, conventions, performance, etc?

```
#include
#include
#include

#define MAX_INT 512

struct q_node
{
int val;
struct q_node next, prev;
} q_node;

struct queue
{
struct q_node head, tail;
} queue;

int graph[MAX_INT][MAX_INT] = {{0}};
int parent[MAX_INT] = {-1}, key[MAX_INT] = {-1}, adj[MAX_INT] = {-1};
int adj_top = 0;

struct queue *init_q()
{
struct queue *q = malloc(sizeof(struct queue));
q->head = NULL; q->tail = NULL;
return q;
}

void free_q(struct queue **q_ptr)
{
struct q_node q_temp = (q_ptr)->head, *q_temp2;
while (q_temp) {
q_temp2 = q_temp;
q_temp = q_temp->next;
free(q_temp2);
}
free(*q_ptr);
}

struct queue enqueue(struct queue q, int i)
{
struct q_node *q_temp = malloc(sizeof(struct q_node));
q_temp->prev = NULL;
q_temp->next = NULL;
q_temp->val = i;
if (q->head == NULL && q->tail == NULL) {
q->head = q_temp;
q->tail = q_temp;
} else {
q_temp->prev = q->tail;
q->tail->next = q_temp;
q->tail = q_temp;
}
return q;
}

int is_empty(struct queue *q)
{
return (q->head == NULL && q->tail == NULL) ? 1 : 0;
}

void traverse(struct queue *q)
{
struct q_node *q_inst = q->head;
if (q->head) {
do {
printf("%d ", q_inst->val);
q_inst = q_inst->next;
} while (q_inst != NULL);
}
printf("\n");
}

int extract_min(struct queue **q_ptr, int no_vert)
{
struct queue q = q_ptr;
struct q_node q_inst = q->head, q_temp = NULL;
int i, min_val = MAX_INT, min_head;

// i = q_inst->val;
while (q_inst != NULL) {
i = q_inst->val;
if (key[i] next;
// i = q_inst->val;
}
if (q_temp == q->head && q_temp == q->tail) {
q->head = NULL;
q->tail = NULL;
free(q_temp);
} els

I see some things that might help you improve your code.

Add comments

Prim's algorithm is well known, and the names of your functions are generally well chosen, but there are no comments in the code to aid the reader. Just a few well-chosen comments would be useful.

In particular the format of the input is not at all documented, leaving the user to reverse engineer the format by reading the code.

Consider a more user-friendly input format

Right now, the user must specify the numbers of vertices and edges and must give numeric node numbers. It would be nice, and wouldn't complicate your code much at all, if one could use letter or word designators for the nodes and to have the computer automatically count the edges.

Perform input sanitation

The scanf function is handy for well-formatted input but not particularly robust for general user input. For instance, if the use enters a negative number for a node number, this code doesn't catch that fact and attempts to address an array with a negative index value. On my machine, this cause a segfault and a program crash.

This could be avoided by doing error checking and by validating the return value from scanf (which returns the number of items scanned) and by examining the value. All of the inputs should probably be unsigned (with the possible exception of the link values), so the code should probably use the %u format specifier instead of %d.

Eliminate unused variables

Unused variables are a sign of poor code quality, so eliminating them should be a priority. In this code, main uses neither argc nor argv and so that function should be int main(). My compiler also tells me that
no_vert is unused in extract_min() and no_edge is unused in min_spantree(). Your compiler is probably also smart enough to tell you that, if you ask it to do so.

Eliminate unused functions

The traverse() function is not used. It appears that perhaps it was once used and then the only call commented out. Eliminating it makes the code easier to understand and maintain.

Eliminate unused headers

Nothing from the ` appears to actually have been used within this code, so it would be best to eliminate it.

Eliminate global variables where practical

The code declares and uses 5 global variables. Global variables obfuscate the actual dependencies within code and make maintenance and understanding of the code that much more difficult. It also makes the code harder to reuse. For all of these reasons, it's generally far preferable to eliminate global variables and to instead pass pointers to them. That way the linkage is explicit and may be altered more easily if needed. For example, to eliminate the adj_top global, the find_adj() function could be rewritten like this:

int find_adj(int u, int no_vert)
{
    int i;
    int adj_top = 0;
    for (i = 0; i < no_vert; i++) {
        if (graph[u][i] != 0) {
            adj[adj_top++] = i;
        }
    }
    return adj_top;
}

Within the context that it's called in min_spantree the call to it becomes:

int adj_top = find_adj(u, no_vert);
for (i = 0; i < adj_top; i++) { 
    ... 
}

Consider regularizing function names

The functions init_q, free_q, enqueue, is_empty, extract_min, isin_q, all deal with the same queue structure. In some places, as with init_q and free_q you have used a _q suffix which suggests this. I'd recommend extending and enhancing that practice and rename the functions q_init, q_free, q_push, q_is_empty, q_get_min, q_contains. By making the function names more regular, it's easy to see at a glance that any q_ function deals with a queue and the names are an attempt to concisely represent what the function does with the queue.

Check return values for malloc

The two places you use malloc in the code immediately use the return value as though it were a valid pointer. However, what if you're out of memory and the allocation failed? In such cases, malloc returns NULL and so the code would make a bad situation (out of memory) even worse by dereferencing NULL and causing a crash. Better is to simply add a check and abort if the return value is NULL before dereferencing.

Rethink your data structures

Prim's algorithm is designed to create a minimum spanning tree, but strangely enough, no tree structure is actually used within the code. That's not necessarily a problem, but it's worth thinking about. Also, the parent and key arrays are actually tightly coupled and one is never altered without the other. This strongly suggests that what is actually called for is an array of a struct containing both. Finally, the graph structure really only needs to be large enough to contain no_vert points. Dynamically, rather than statically allocating the size would reduce wasted space and clarify what it contains.

Eliminate redundant loops

Within min_spantree` the code loops through all vertices and initializes t

StackExchange Code Review Q#67251, answer score: 7