数据结构——图的数组实现（邻接矩阵表示法）

Graph

　　　　　　基本知识这里不做介绍，可以去看<DSAA>或者<algorithm>.这里主要给出图的Ｃ语言实现。

首先我们要对图进行“抽象”，具体的找出关键能够描述图的关键信息，这里我简单的选取了vertex和edge，就是节点和节点所连同的路径。

下面是基于数组描述节点间关系的实现

graph.h

/************************************************************
code file	: graph.h
code writer	: EOF
code date	: 2014.11.22
e-mail		: [email protected]

code description:
	This file is a header file for out test program.
We abstract the data structure -- Graph here. And we also
declare some useful API to construct out naive graph :)

************************************************************/
#ifndef _GRAPH_H_
#define _GRAPH_H_

	#include <stdio.h>
	#include <stdlib.h>

	#define CONNECTED    1
	#define DISCONNECTED 0

	#define SUCCESS  0
	#define FAILED  -1
	struct graph
	{
		int num_vertex;
		int num_edge;

		char adjacent[0];
	};

	struct graph* init_graph(int vertex,int edge);
	void   release_graph(struct graph* p_graph);
	
	int add_edge(struct graph* p_graph,char from_v,char to_v);
	int print_graph(struct graph* p_graph);

#endif
           

init_graph.c 通过该函数实现graph的初始化

#include "graph.h"

struct graph* init_graph(int vertex,int edge)
{
	if(vertex <=0 || edge <= 0)
	{
		return NULL;
	}

	int temp = 0;

	struct graph* p_graph = NULL;
        p_graph = (struct graph*)malloc(sizeof(struct graph) + vertex*vertex);

	p_graph->num_vertex = vertex;
	p_graph->num_edge   = edge;

	//initialize the adjacent relationship
	for(temp = 0;temp < vertex*vertex;temp++)
	{
		p_graph->adjacent[temp] = 0;
	}
	
	return p_graph;
}
           

add_edge.c　该函数为from_v 和 to_v　两个节点建立连通关系。

/************************************************************
code file	: add_edge.c
code writer	: EOF
code date	: 2014.11.22
e-mail		: [email protected]

code description:
	This function will help us to add a new connection
between different vertex which is in the graph.

*************************************************************/
#include "graph.h"

int add_edge(struct graph* p_graph,char from_v,char to_v)
{
	if(!p_graph || from_v < 0 || to_v < 0)
	{
		return -1;
	}

	*((char*)(p_graph->adjacent)  + from_v*(p_graph->num_vertex) + to_v)  = 1;
	*((char*)(p_graph->adjacent)  + to_v*(p_graph->num_vertex)  + from_v) = 1;

	return 0;
}
           

release_graph.c 这里最后释放图

/************************************************************
code file	: release_graph.c
code writer	: EOF
code date	: 2014.11.22
e-mail		: [email protected]

code description:
	It's easy and convenient for us to call this API once
and free all the graph.

*************************************************************/
#include "graph.h"
#include "graph.h"
void release_graph(struct graph* p_graph)
{
	if(!p_graph)
	{
		return ;
	}

	free(p_graph);
}
           

最后是用于测试的主程序。

#include <stdio.h>
#include "graph.h"

int main()
{
	struct graph* p_graph = NULL;

	FILE* fp = fopen("./text.txt","r+");

	if(!fp)
	{
		printf("fopen() failed!\n");
		return 0;
	}

	int ret    = 0;
	int vertex = 0;
	int edge   = 0;

	int from_v = 0;
	int to_v   = 0;

	fscanf(fp,"%d",&vertex);
	fscanf(fp,"%d",&edge);

	p_graph = init_graph(vertex,edge);

	int temp = 0;
	for(temp;temp < edge;temp++)
	{
		/*
		**	I think it's necessary to check the returned value
		** of scanf() family.
		*/
		ret = fscanf(fp,"%d %d",&from_v,&to_v);
		if(ret != 2)
		{
			break;
		}

		add_edge(p_graph,from_v,to_v);
	}
	
	print_graph(p_graph);

	release_graph(p_graph);
	fclose(fp);
	return 0;
}
           

测试材料：文本文件text.txt

13
13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3
           

我们的测试结果：