使用邻接表表示图

    下面的代码是用邻接矩阵的方式来对图进行表示。其中展示了图的生成，边的插入，删除，图的销毁等操作。

 

graph.h

typedef struct
{
        int v;
        int w;
}Edge;

typedef struct graph *Graph;

Graph graphinit(int);

int graphinserte(Graph, Edge);

void graphremovee(Graph, Edge);

Graph graphcopy(Graph);

void graphdestroy(Graph);

void graphshow(Graph);


graph.c

#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

typedef struct node* link;
struct node
{
        int v;
        link next;
};

struct graph
{
        int v;
        int e;
        link *adj;
};

Graph graphinit(int v)
{
        int vi;
        Graph g = (Graph)malloc(sizeof(*g));
        if (g == NULL)
                return NULL;

        g->v = v;
        g->e = 0;
        g->adj = (link*)malloc(v * sizeof(link));
        if (g->adj == NULL)
        {
                free(g);
                return NULL;
        }

        for (vi = 0; vi < v; vi++)
                g->adj[vi] = NULL;
        return g;
}

int graphinserte(Graph g, Edge e)
{
        int v = e.v;
        int w = e.w;

        link tmp1, tmp2;

        tmp1 = (link)malloc(sizeof(*tmp1));
        if (tmp1 == NULL)
                return -1;
        tmp2 = (link)malloc(sizeof(*tmp2));
        if (tmp2 == NULL)
        {
                free(tmp1);
                return -1;
        }

        tmp1->v = w;
        tmp1->next = g->adj[v];
        g->adj[v] = tmp1;

        tmp2->v = v;
        tmp2->next = g->adj[w];
        g->adj[w] = tmp2;

        g->e++;

        return 0;
}

void graphshow(Graph g)
{
        int i;
        link x;

        printf("%d vertices, %d edges\n", g->v, g->e);

        for (i = 0; i < g->v; i++)
        {
                printf("%2d: ", i);
                x = g->adj[i];
                while (x != NULL)
                {
                        printf(" %2d", x->v);
                        x = x->next;
                }
                printf("\n");
        }
}

void graphdestroy(Graph g)
{
        link x, tmp;
        int i;

        for (i = 0; i < g->v; i++)
        {
                x = g->adj[i];
                while (x != NULL)
                {
                        tmp = x;
                        x = x->next;
                        free(tmp);
                }
        }
        free(g->adj);
}


main.c

#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

int main()
{
        Graph g;
        int i, j;
        int ver = 13;


        Edge e[] = {{0, 5},{5, 4}, {7, 8}, {4, 3}, {0, 2}, {9, 11}, {0, 1}, {11, 12}, {5, 3}, {9, 12}, {9, 10}, {6, 4}, {0, 6}};
        j = sizeof(e) / sizeof(e[0]);

        g = graphinit(ver);
        if (g == NULL)
        {
                printf("init graph error\n");
                exit(1);
        }


        for (i = 0; i < j; i++)
                if (graphinserte(g, e[i]) < 0)
                {
                        printf("insert error\n");
                        break;
                }

        graphshow(g);

        graphdestroy(g);
        return 0;
}


gcc -Wall main.c graph.c -o main

./main