本节我们来学习使用邻接表来表示图。假设有图如下:
邻接表表示法定义两个数据结构,顶点结构和弧结构。每一个顶点都有一个指针指向其出弧,也就是以当前基点为起始点,并记录着此弧所指向的下一节点索引号。每一个弧指向以这个顶点为起始点的下一条弧。例如上图使用邻接表来表示的结果为:
[0] -> (1, 15) [1] -> (3, 23) -> (4, 71) [2] -> (0, 27) -> (1, 92) -> (4, 36) [3] -> (3, 61) -> (4, 42) [4]
[1] -> (3, 23) -> (4, 71) 表示索引为1的顶点有2个出弧,第一个出弧的弧尾指向索引为3的顶点,这条弧的权重为23;第二个出弧的弧尾指向索引为4的顶点,权重为71。
对于无向图来说,弧记录了与它关联的两个顶点的索引,通过索引就可以找到相关的顶点。而对于有向图来说这种方式只记录了顶点的出弧,而想要取得顶点的入弧的信息则必须要遍历整张邻接表。这对图的操作是非常低效的。于是通常采用一个辅助邻接表来表示所有顶点入弧的信息,这个邻接表被称为逆邻接表:
[0] -> (2, 27) [1] -> (0, 15) -> (2, 92) [2] [3] -> (1, 23) -> (3, 61) [4] -> (1, 71) -> (2, 36) -> (3, 42)
[1] -> (0, 15) -> (2, 92) 表示索引为1的顶点有2个入弧,第一个出弧的弧头指向索引为0的顶点,这条弧的权重为15;第二个出弧的弧头指向索引为2的顶点,权重为92。
下面我们就来实现图的邻接表的表示:
//边或弧 typedef struct s_arccell { //权重 int weight; //弧尾顶点索引号end vertex index int v_index; //数据 void *data; //下一个弧结节 struct s_arccell *next; } s_arccell; typedef struct { //顶点数据 void *data; //出弧,以当前顶点为起始的弧 s_arccell *arccel_out; //入弧,以当前顶点为终止的弧 s_arccell *arccel_in; } s_vertex; //邻接表 typedef struct { //顶点数组 s_vertex *vertex; //顶点个数 int size; //显示顶点数据的回调函数 void (*visit_vertex)(); //显示弧数据的回调函数 void (*visit_arccell)(); } s_graph; //初始化图 bool graph_init(s_graph *graph, int vertex_size, void (*visit_vertex)(), void (*visit_arccell)()) { if (graph == null) { return false; } if (vertex_size <= 0) { return false; } //设置顶点个数 graph->size = vertex_size; //申请顶点内存 graph->vertex = (s_vertex *) malloc(sizeof(s_vertex) * vertex_size); //初始化顶点 for (int i = 0; i < vertex_size; i++) { graph->vertex[i].data = null; graph->vertex[i].arccel_out = null; graph->vertex[i].arccel_in = null; } //显示顶点数据的回调函数 graph->visit_vertex = visit_vertex; //显示弧数据的回调函数 graph->visit_arccell = visit_arccell; return true; } //销毁图 bool graph_destroy(s_graph *graph) { if (graph == null) { return false; } free(graph->vertex); return true; } /* * 设置顶点数据 * int index : 顶点索引号 * void *data : 数据指针 */ bool graph_set_vertex(s_graph *graph, int index, void *data) { if (graph == null) { return false; } graph->vertex[index].data = data; return true; } /* * 设置边或弧内存的权重及数据 * int sv_index : 起始顶点索引 * int ev_index : 终止顶点索引 * int weight : 权重 * void *data : 数据指针 */ bool graph_insert_arccell(s_graph *graph, int sv_index, int ev_index, int weight, void *data) { if (graph == null) { return false; } if (sv_index < 0 || sv_index >= graph->size) { return false; } if (ev_index < 0 || ev_index >= graph->size) { return false; } /*** * 出入弧 */ //新建一个弧 s_arccell *arccel_out = (s_arccell *) malloc(sizeof(s_arccell)); //弧数据 arccel_out->data = data; //权重 arccel_out->weight = weight; //弧尾关联的顶点索引号 arccel_out->v_index = ev_index; arccel_out->next = null; //如果顶点中第一条弧为空 if (graph->vertex[sv_index].arccel_out == null) { //设置顶点的每一条弧 graph->vertex[sv_index].arccel_out = arccel_out; } else { //找到顶点弧中最后一条弧 s_arccell *p = graph->vertex[sv_index].arccel_out; while (p->next != null) { p = p->next; } //追加新弧 p->next = arccel_out; } /*** * 入弧 */ //新建一个弧 s_arccell *arccel_in = (s_arccell *) malloc(sizeof(s_arccell)); //弧数据 arccel_in->data = data; //权重 arccel_in->weight = weight; //弧头关联的顶点索引号 arccel_in->v_index = sv_index; arccel_in->next = null; //如果顶点中第一条弧为空 if (graph->vertex[ev_index].arccel_in == null) { //设置顶点的每一条弧 graph->vertex[ev_index].arccel_in = arccel_in; } else { //找到顶点弧中最后一条弧 s_arccell *p = graph->vertex[ev_index].arccel_in; while (p->next != null) { p = p->next; } //追加新弧 p->next = arccel_in; } return true; } //显示图信息 bool graph_visit(s_graph *graph) { if (graph == null) { return false; } //循环顶点 for (int i = 0; i < graph->size; i++) { //显示顶点索引及数据 printf("[%d, ", i); graph->visit_vertex(graph->vertex[i].data); printf("]"); //显示顶点出度弧的权重及数据 s_arccell *p = graph->vertex[i].arccel_out; while (p != null) { printf(" -> (%d, %d, ", p->v_index, p->weight); graph->visit_arccell(p->data); printf(") "); p = p->next; } printf("\n"); } printf("\n"); //循环顶点 for (int i = 0; i < graph->size; i++) { //显示顶点索引及数据 printf("[%d, ", i); graph->visit_vertex(graph->vertex[i].data); printf("]"); //显示顶点出度弧的权重及数据 s_arccell *p = graph->vertex[i].arccel_in; while (p != null) { printf(" -> (%d, %d, ", p->v_index, p->weight); graph->visit_arccell(p->data); printf(") "); p = p->next; } printf("\n"); } return true; }
最后来写一个main函数构建邻接表:
#include <stdio.h> #include <stdlib.h> #include "graph.h" void visit_int(int *i) { if (i != null) { printf("%d", *i); } } int main(int argc, char **args) { //邻接表 s_graph graph; graph_init(&graph, 5, &visit_int, &visit_int); //顶点数据项 int *t0 = (int *) malloc(sizeof(int)); int *t1 = (int *) malloc(sizeof(int)); int *t2 = (int *) malloc(sizeof(int)); int *t3 = (int *) malloc(sizeof(int)); int *t4 = (int *) malloc(sizeof(int)); //顶点数据 *t0 = 53; *t1 = 43; *t2 = 12; *t3 = 54; *t4 = 75; //弧数据项 int *d0 = (int *) malloc(sizeof(int)); int *d1 = (int *) malloc(sizeof(int)); int *d2 = (int *) malloc(sizeof(int)); int *d3 = (int *) malloc(sizeof(int)); int *d4 = (int *) malloc(sizeof(int)); int *d5 = (int *) malloc(sizeof(int)); int *d6 = (int *) malloc(sizeof(int)); int *d7 = (int *) malloc(sizeof(int)); //弧数据 *d0 = 56; *d1 = 34; *d2 = 75; *d3 = 96; *d4 = 77; *d5 = 19; *d6 = 64; *d7 = 58; //设置顶点数据 graph_set_vertex(&graph, 0, t0); graph_set_vertex(&graph, 1, t1); graph_set_vertex(&graph, 2, t2); graph_set_vertex(&graph, 3, t3); graph_set_vertex(&graph, 4, t4); //插入弧数据 graph_insert_arccell(&graph, 0, 1, 15, d0); graph_insert_arccell(&graph, 1, 3, 23, d1); graph_insert_arccell(&graph, 1, 4, 71, d2); graph_insert_arccell(&graph, 2, 0, 27, d3); graph_insert_arccell(&graph, 2, 1, 92, d4); graph_insert_arccell(&graph, 2, 4, 36, d5); graph_insert_arccell(&graph, 3, 3, 61, d6); graph_insert_arccell(&graph, 3, 4, 42, d7); /* * 显示邻接表,格式如下: * [顶点索引, 顶点数据] -> (弧尾指向顶点的索引, 弧权重, 弧数据) -> (弧尾指向顶点的索引, 弧权重, 弧数据) */ graph_visit(&graph); //销毁邻接表 graph_destroy(&graph); return 0; }
运行结果:
[0, 53] -> (1, 15, 56) [1, 43] -> (3, 23, 34) -> (4, 71, 75) [2, 12] -> (0, 27, 96) -> (1, 92, 77) -> (4, 36, 19) [3, 54] -> (3, 61, 64) -> (4, 42, 58) [4, 75] [0, 53] -> (2, 27, 96) [1, 43] -> (0, 15, 56) -> (2, 92, 77) [2, 12] [3, 54] -> (1, 23, 34) -> (3, 61, 64) [4, 75] -> (1, 71, 75) -> (2, 36, 19) -> (3, 42, 58)
本例代码:
code path chapter.06/e.g.6.2/ 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号