|
图的表示：
邻接矩阵表示法：
对于上面一个有向图的一种简单的表示方法是使用二维数组，称为邻接矩阵表示法。
如果是无向图，对于每条边(u, v),将二维数组元素arr[u][v]值设置为true;否则该数组元素为false；
如果是有向图，对于每条边(u, v),将二维数组元素arr[u][v]值设置为该边的权重;否则该数组元素设置为一个很大的数值或是一个很小的数组（根据具体情景设置）；
虽然邻接矩阵表示法比较简单，但是需要的空间比较大，适合于稠密类型的图。
邻接表表示法：
另一种表示方法是使用邻接表表示法，该方法适合于稀疏类型的图。
其实左边的数组也可以不用，如果有需要的话可以加上用来保存各个顶点的信息。一般实现的话根据右边链表数组的顺序就可以知道每个顶点对应的链表。
图中节点的数据结构：
//图节点信息
typedef struct Node{
int edge_num;//边号
int src;//源点
int vertex;//自身
int weight;//边的权重
}Node;
图的邻接表表示法的类接口：
/*******************************************************
* 类名称： 邻接表图
********************************************************/
class Graph{
private:
int edge_num;//图边的个数
int vertex_num;//图的顶点数目
list
* graph_list;//邻接表
public:
Graph(){}
Graph(char* graph[], int edgenum);
~Graph();
void print();//以邻接表的形式打印图信息
private:
vector
get_graph_value(char* graph[], int columns);//获得每条边的数据 void addEdge(char* graph[], int columns); };
测试函数：
1、读取图文件中的数据，图中的数据格式为下面所示：
0,0,1,1
1,0,2,2
2,0,3,1
第1列为边的标号，第2列为边的起点，第3列为边的终点，第4列为边的权重。
/****************************************************************
* 函数名称：read_file
* 功能描述: 读取文件中的图的数据信息
* 参数列表: buff是将文件读取的图信息保存到buff指向的二维数组中
* spec是文件中图最大允许的边的个数
* filename是要打开的图文件
* 返回结果：无
*****************************************************************/
int read_file(char ** const buff, const unsigned int spec, const char * const filename)
{
FILE *fp = fopen(filename, "r");
if (fp == NULL)
{
printf("Fail to open file %s, %s.\n", filename, strerror(errno));
return 0;
}
printf("Open file %s OK.\n", filename);
char line[MAX_LINE_LEN + 2];
unsigned int cnt = 0;
while ((cnt < spec) && !feof(fp))
{
line[0] = 0;
fgets(line, MAX_LINE_LEN + 2, fp);
if (line[0] == 0) continue;
buff[cnt] = (char *)malloc(MAX_LINE_LEN + 2);
strncpy(buff[cnt], line, MAX_LINE_LEN + 2 - 1);
buff[cnt][4001] = 0;
cnt++;
}
fclose(fp);
printf("There are %d lines in file %s.\n", cnt, filename);
return cnt;
}
2、释放刚才读取的文件中的图的数据信息
/****************************************************************
* 函数名称：release_buff
* 功能描述: 释放刚才读取的文件中的图的数据信息
* 参数列表: buff是指向文件读取的图信息
* valid_item_num是指图中边的个数
* 返回结果：void
*****************************************************************/
void release_buff(char ** const buff, const int valid_item_num)
{
for (int i = 0; i < valid_item_num; i++)
free(buff[i]);
}
3、主测试函数
int main(int argc, char *argv[])
{
char *topo[5000];
int edge_num;
char *demand;
int demand_num;
char *topo_file = argv[1];
edge_num = read_file(topo, 5000, topo_file);
if (edge_num == 0)
{
printf("Please input valid topo file.\n");
return -1;
}
Graph G(topo, edge_num);//创建一个图对象G
G.print();//以邻接表的形式打印图信息
release_buff(topo, edge_num);
return 0;
}
图的邻接表表示法类的源代码：
#ifndef GRAPH_H
#define GRAPH_H
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std; #define MAX_VERTEX_NUM 600 //图节点信息 typedef struct Node{ int edge_num;//边号 int src;//源点 int vertex;//自身 int weight;//边的权重 }Node; /******************************************************* * 类名称： 邻接表图 ********************************************************/ class Graph{ private: int edge_num;//图边的个数 int vertex_num;//图的顶点数目 list
* graph_list;//邻接表 public: Graph(){} Graph(char* graph[], int edgenum); ~Graph(); void print();//以邻接表的形式打印图信息 private: vector
get_graph_value(char* graph[], int columns);//获得每条边的数据 void addEdge(char* graph[], int columns); }; /******************************** |