数据结构实战

        本节我们来学习使用邻接表来表示图。假设有图如下：

        邻接表表示法定义两个数据结构，顶点结构和弧结构。每一个顶点都有一个指针指向其出弧，也就是以当前基点为起始点，并记录着此弧所指向的下一节点索引号。每一个弧指向以这个顶点为起始点的下一条弧。例如上图使用邻接表来表示的结果为：

[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