資料結構——圖的數組實作（鄰接矩陣表示法）

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
           

我們的測試結果：