[算法] 使用邻接矩阵表示图
下面的代码是用邻接矩阵的方式来对图进行表示。其中展示了图的生成，边的插入，删除，图的销毁等操作。
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;
}
页:
[1]