prim's algorithm

gistfile1.c

#include "zombies.h"

t_graph *prim(t_graph *graph, int s) {
    t_graph *prim;
    if(graph != NULL && graph->v > 0 && graph->e > 0) {
        prim = new_graph(graph->v);
        unsigned int i;
        unsigned int j;
        int visited[graph->v];
        int known;
        known = 0;
        visited[known] = s;
        add_vertex(prim, graph->vertices[s].name, graph->vertices[s].strength, known++);
        int max;
        int max_dst;
        int src;
        int weight;
        // for a directed graph
        while(known < graph->v) {
            for(i = 0; i < known; i++) {
                // for each element that has been visited
                // find the neighbors of i
                src = visited[i];
                max = -1;
                max_dst = -1;
                for(j = 0; j < graph->v; j++) {
                    if(!contains(visited, j, known)){
                        if(graph->digraph == TRUE) {
                            if(graph->am[src][j] != 0 || graph->am[j][src] != 0) {
                                // there is a connection between src and j - if INF, treat as 0
                                weight = graph->am[src][j] - graph->am[j][src];  // calculate the net weight
                                weight *= (weight < 0) ? -1 : 1;  // get the absolute value of weight
                                max_dst = (weight > max) ? j : max_dst;
                                max = (weight > max) ? weight : max;
                            }
                        } else {
                            if(graph->am[src][j] > 0) {
                                // there is a connection between src and j - if INF, treat as 0
                                weight = graph->am[src][j];
                                max_dst = (weight > max) ? j : max_dst;
                                max = (weight > max) ? weight : max;
                            }
                        }
                    }
                }
                if(max_dst > 0) {
                    // max_dst is the next node to add to our network
                    visited[known] = max_dst;
                    add_vertex(prim, graph->vertices[max_dst].name, graph->vertices[max_dst].strength, known++);
                    add_edge(prim, src, max_dst, max);
                }
            }
        }
    }
    return prim;
}

boolean contains(int *array, int item, int length) {
    unsigned int i;
    for(i = 0; i < length; i++) {
        if(array[i] == item)
            return TRUE;
    }
    return FALSE;
}

void print_visited(int *p, int v) {
    unsigned int i;
    puts("----------- PRIM'S ALGORITHM -----------");
    for(i = 0; i < v; i++) {
        printf("%d ", p[i]);
    }
    printf("\n");
    puts("\n----------- PRIM'S ALGORITHM -----------");
}