|
拓扑排序简介：
拓扑排序是对
有向无环图的顶点的一种排序，它使得如果存在一条从Vi到Vj的路径，那么在排序中Vi在Vj的前面。
如果图中含有回路，那么拓扑排序是不可能的。此外，拓扑排序不必是唯一的，任何合理的排序都可以。
对于上面的无环图:v1,v2,v5,v4,v3,v7,v6和v1,v2,v5,v4,v7,v3,v6都是合理的拓扑排序。
一个简单的求拓扑排序的思路：
1、先找出任意一个没有入边的顶点
2、然后显出该点，并将它和它邻接的所有的边全部删除。
3、然后，对图中其它部分做同样的处理。
图用邻接表表示法来存储：
左边的数组此时就有用了，用来保存每个顶点的信息，该数组中每个元素的数据结构为：
//保存每个顶点信息的数据结构
struct GraphNode{
int vertex;//当前顶点的标号
int inDegree;//当前顶点的入度
int topNum;//当前顶点的拓扑排序的顺序标号
};
图的邻接表示法的类的接口：
/*******************************************************
* 类名称： 邻接表图
********************************************************/
class Graph{
private:
int edge_num;//图边的个数
int vertex_num;//图的顶点数目
list
* graph_list;//邻接表
vector
nodeArr;//保存每个顶点信息的数组 public: Graph(){} Graph(char* graph[], int edgenum); ~Graph(); void print(); vector
topoSort();//拓扑排序 private: vector
get_graph_value(char* graph[], int columns); void addEdge(char* graph[], int columns); };
拓扑排序成员函数：
/*************************************************
* 函数名称：topoSort()
* 功能描述：对图中的顶点进行拓扑排序
* 参数列表：无
* 返回结果：返回顶点拓扑排序之后的结果
*************************************************/
vector
Graph::topoSort()
{
vector
topoSortArr; for(int count = 0; count < vertex_num; ++count){ //找到一个入度为0的顶点 int i; for(i = 0; i < vertex_num; ++i){ if((nodeArr[i].inDegree == 0)&&(nodeArr[i].vertex != -1)) break; } if(i == vertex_num) break; //此时顶点i的入度为0 //删除该点和删除与该点相邻的边 //并将与顶点i相连的顶点的入度减1 nodeArr[i].inDegree = -1; for(list
::iterator it = graph_list[i].begin(); it != graph_list[i].end(); ++it){ nodeArr[(*it).vertex].inDegree--; } topoSortArr.push_back(i); } return topoSortArr; }
测试函数：
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.print();
vector
topoSortArr = G.topoSort();
cout << "拓扑排序的结果: ";
for(unsigned i = 0; i < topoSortArr.size(); ++i)
cout << topoSortArr[i] << " ";
cout << endl;
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 //保存每个顶点信息的数据结构 struct GraphNode{ int vertex;//当前顶点的标号 int inDegree;//当前顶点的入度 int topNum;//当前顶点的拓扑排序的顺序标号 }; //图节点信息 typedef struct Node{ int edge_num;//边号 int src;//源点 int vertex;//自身 int weight;//边的权重 }Node; /******************************** |