数据结构实战

        图的数组表示法比较简单，使用一个二维数组来表示图中两两节点之间边（无向图）或弧（有向图）的关系。例如有如下有向图：

        数组表示为：

     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