[算法] 使用邻接矩阵表示图

萧闫子 · 发表于 2014-1-10 14:18:13

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

graph.h

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

Edge EDGE(int, int);

typedef struct graph *Graph;

Graph graphinit(int);

void graphinserte(Graph, Edge);

void graphremovee(Graph, Edge);

Graph graphcopy(Graph);

void graphdestroy(Graph);

void graphshow(Graph);

graph.c

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

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

Edge EDGE(int v, int w)
{
      Edge e;
      e.v = v;
      e.w = w;

      return e;
}

int **matrixint(int r, int c, int val)
{
      int i, j;

      int **t = (int**)malloc(r * sizeof(int*));
      if (t == NULL)
            return NULL;
      for (i = 0; i < r; i++)
      {
            t[i = (int*)malloc(c * sizeof(int));
            if (t[i == NULL)
            {
                     while (--i >= 0)
                              free(t[i);
                     return NULL;
            }
      }

      for (i = 0; i < r; i++)
            for (j = 0; j < c; j++)
                     t[i[j = val;
      return t;
}

Graph graphinit(int v)
{
      Graph g;

      g = (Graph)malloc(sizeof(*g));
      g->v = v;
      g->e = 0;
      g->adj = matrixint(v, v, 0);

      return g;
}

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

      if (g->adj[v[w == 0)
            g->e++;
      g->adj[v[w = 1;
      g->adj[w[v = 1;
}

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

      if (g->adj[v[w == 1)
            g->e--;
      g->adj[v[w = 0;
      g->adj[w[v = 0;
}

void graphshow(Graph g)
{
      int i, j;
      printf("%d vertices, %d edges\n", g->v, g->e);

      for (i = 0; i < g->v; i++)
      {
            printf("%2d: ", i);
            for (j = 0; j < g->v; j++)
                     if (g->adj[i[j == 1)
                              printf(" %2d", j);
            printf("\n");
      }
}

void graphdestroy(Graph g)
{
      int i;

      for (i = 0; i < g->v; i++)
            free(g->adj[i);
      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++)
            graphinserte(g, e[i);

      graphshow(g);

      graphdestroy(g);
      return 0;
}

帐号		自动登录	找回密码
密码			注册