• 博客访问： 532902
• 博文数量： 54
• 博客积分： 3812
• 博客等级： 上校
• 技术积分： 992
• 用 户 组： 普通用户
• 注册时间： 2007-04-16 20:53

2010年（10）

2009年（24）

2008年（20）

2009-03-24 14:11:01

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

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 #include #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 #include #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