图的数组表示法比较简单,使用一个二维数组来表示图中两两节点之间边(无向图)或弧(有向图)的关系。例如有如下有向图:
数组表示为:
0 1 2 3 4 0 { --, --, --, 2, 11 }, 1 { 37, --, --, --, -- }, 2 { 12, --, --, --, 18 }, 3 { --, 13, --, --, 76 }, 4 { --, 43, --, --, -- }
也就是说,图有4个顶点,它们之间的关系可以用4X4的二维数组来表示,其中“--”表示“无穷大”。
下面来看一下实现代码:
//最大正整数 #define INFINITY (0x7FFFFFFF) //图 typedef struct { //顶点 int *vertex; //边 int **arccell; //顶点个数 int size; } s_graph; //初始化图 bool graph_init(s_graph *graph, int vertex_size) { if (graph == null) { return false; } if (vertex_size <= 0) { return false; } //设置顶点个数 graph->size = vertex_size; //申请顶点内存 graph->vertex = (int *) malloc(sizeof(int) * vertex_size); //申请边或弧内存 graph->arccell = (int **) malloc(sizeof(int *) * vertex_size); for (int i = 0; i < vertex_size; i++) { //顶点值默认为0 graph->vertex[i] = 0; graph->arccell[i] = malloc(sizeof(int) * vertex_size); for (int j = 0; j < vertex_size; j++) { //边的权重默认为无穷大 graph->arccell[i][j] = INFINITY; } } return true; } //销毁图 bool graph_destroy(s_graph *graph) { if (graph == null) { return false; } for (int i = 0; i < graph->size; i++) { free(graph->arccell[i]); } free(graph->arccell); free(graph->vertex); return true; } //设置顶点值 bool graph_set_vertex(s_graph *graph, int index, int val) { if (graph == null) { return false; } graph->vertex[index] = val; return true; } //设置边或弧内存的权重 bool graph_set_arccell(s_graph *graph, int i, int j, int weight) { if (graph == null) { return false; } graph->arccell[i][j] = weight; return true; } //显示图 bool graph_display(s_graph *graph) { if (graph == null) { return false; } for (int i = 0; i < graph->size; i++) { printf("%d ", graph->vertex[i]); } printf("\n\n"); for (int i = 0; i < graph->size; i++) { for (int j = 0; j < graph->size; j++) { if (graph->arccell[i][j] == INFINITY) { printf(" --, "); } else { printf("%3d, ", graph->arccell[i][j]); } } printf("\n"); } printf("\n"); return true; }
最后来编写main函数构建一个图:
#include <stdio.h> #include "graph.h" int main(int argc, char **args) { s_graph graph; graph_init(&graph, 5); for (int i = 0; i < 5; i++) { graph_set_vertex(&graph, i, i); } graph_set_arccell(&graph, 0, 1, 15); graph_set_arccell(&graph, 1, 4, 71); graph_set_arccell(&graph, 1, 3, 23); graph_set_arccell(&graph, 3, 4, 42); graph_set_arccell(&graph, 2, 4, 36); graph_set_arccell(&graph, 2, 0, 27); graph_set_arccell(&graph, 3, 3, 61); graph_set_arccell(&graph, 2, 1, 92); graph_display(&graph); graph_destroy(&graph); return 0; }
运行结果:
0 1 2 3 4 --, 15, --, --, --, --, --, --, 23, 71, 27, 92, --, --, 36, --, --, --, 61, 42, --, --, --, --, --,
本例代码:
code path chapter.06/e.g.6.1/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号