Algorithms‎ > ‎

Graph

#define MAXV 1000


struct edgenode {

    int y;

    int weight;

    struct edgenode *next;

};


typedef struct {

    edgenode *edges[MAXV + 1];

    int degree[MAXV + 1];

    int nvertices;

    int nedges;

    bool directed;

} graph;


void initialize_graph(graph *g, bool directed)

{

    int i;

    

    g->nvertices = 0;

    g->nedges = 0;

    g->directed = directed;

    

    for (i = 1; i < MAXV; i++)

    {

        g->degree[i] = 0;

        g->edges[i] = NULL;

    }

}


void insert_edge(graph *g, int x, int y, bool directed)

{

    edgenode *p;

    p = (edgenode *)malloc(sizeof(edgenode));

    

    p->weight = NULL;

    p->y = y;

    p->next = g->edges[x];

    

    g->edges[x] = p;

    g->degree[x]++;

    if (directed == false)

        insert_edge(g, y, x, true);

    else

        g->nedges++;

}


// To read the graph from command line

void read_graph(graph *g, bool directed)

{

    int i;

    int m;

    int x, y, weight;

    

    initialize_graph(g, directed);

    scanf("%d %d", &(g->nvertices), &m);

    

    for (i = 1; i <= m; i++)

    {

        scanf("%d %d", &x, &y);

        insert_edge(g, x, y, directed);

    }

}


// Create a sample graph

void load_graphA(graph *g, bool directed)

{

    initialize_graph(g, directed);

    g->nvertices = 7;

  

    insert_edge(g, 1, 2, directed);

    insert_edge(g, 1, 3, directed);

    insert_edge(g, 1, 7, directed);

    insert_edge(g, 2, 3, directed);

    insert_edge(g, 3, 4, directed);

    insert_edge(g, 3, 5, directed);

    insert_edge(g, 4, 5, directed);

    insert_edge(g, 5, 6, directed);

    insert_edge(g, 5, 7, directed);

    insert_edge(g, 1, 6, directed);

}


void print_graph(graph *g)

{

    int i;

    edgenode *p;

    

    for (i = 1; i <= g->nvertices; i++)

    {

        printf("%d: ", i);

        p = g->edges[i];

        while (p != NULL)

        {

            printf(" %d", p->y);

            p = p->next;

        }

        printf("\n");

    }

}


int main(int argc, const char * argv[]) {

    graph *myGraph = (graph *)malloc(sizeof(graph));

    read_graph(myGraph, false);

    // Or

    load_graphA(myGraph, false);

    

    print_graph(myGraph);

    return 0;

}