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

本文主要是介绍数据结构——图的数组实现（邻接矩阵表示法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Graph

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

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

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

graph.h

/************************************************************
code file	: graph.h
code writer	: EOF
code date	: 2014.11.22
e-mail		: jasonleaster@gmail.comcode 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  -1struct 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 relationshipfor(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		: jasonleaster@gmail.comcode 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		: jasonleaster@gmail.comcode 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

我们的测试结果：

  

这篇关于数据结构——图的数组实现（邻接矩阵表示法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---