數據結構與算法——有向無環圖的拓撲排序C++實現

拓撲排序簡介：

拓撲排序是對有向無環圖的頂點的一種排序，它使得如果存在一條從Vi到Vj的路徑，那麼在排序中Vi在Vj的前面。 如果圖中含有回路，那麼拓撲排序是不可能的。此外，拓撲排序不必是唯一的，任何合理的排序都可以。

對於上面的無環圖:v1,v2,v5,v4,v3,v7,v6和v1,v2,v5,v4,v7,v3,v6都是合理的拓撲排序。

一個簡單的求拓撲排序的思路：

1、先找出任意一個沒有入邊的頂點 2、然後顯出該點，並將它和它鄰接的所有的邊全部刪除。 3、然後，對圖中其它部分做同樣的處理。

圖用鄰接表表示法來存儲：

參考博客：數據結構與算法——圖的鄰接表表示法類的C++實現

左邊的數組此時就有用了，用來保存每個頂點的信息，該數組中每個元素的數據結構為：

//保存每個頂點信息的數據結構
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; 

/*******************************************************
*  類名稱： 鄰接表圖
********************************************************/ 
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;
}

/*************************************************
*  函數名稱：print
*  功能描述：將圖的信息以鄰接表的形式輸出到標准輸出
*  參數列表：無
*  返回結果：無
*************************************************/
void Graph::print()
{
    cout << "******************************************************************" << endl; 
    //for(int i = 0 ; i < MAX_VERTEX_NUM; ++i){
    for(int i = 0 ; i < vertex_num; ++i){
        if(graph_list[i].begin() != graph_list[i].end()){
            cout << i << "-->";
            for(list::iterator it = graph_list[i].begin(); it != graph_list[i].end(); ++it){
                cout << (*it).vertex << "(邊號:" << (*it).edge_num << ",權重:" << (*it).weight << ")-->";
            }
            cout << "NULL" << endl;
        }
    }

    cout << "******************************************************************" << endl; 
}

/*************************************************
*  函數名稱：get_graph_value
*  功能描述：將圖的每一條邊的信息保存到一個數組中
*  參數列表: graph：指向圖信息的二維數組
             columns:圖的第幾條邊
*  返回結果：無
*************************************************/
vector Graph::get_graph_value(char* graph[], int columns)
{
    vector v;
    char buff[20];
    int i = 0, j = 0, val;
    memset(buff, 0, 20);

    while((graph[columns][i] != '\n') && (graph[columns][i] != '\0')){
        if(graph[columns][i] != ','){
            buff[j] = graph[columns][i];
            j++;
        }
        else{
            j = 0;
            val = atoi(buff); 
            v.push_back(val);
            memset(buff, 0, 20);
        }
        i++;
    }
    val = atoi(buff); 
    v.push_back(val);

    return v;
}



/*************************************************
*  函數名稱：addEdge
*  功能描述：將圖的每一條邊的信息加入圖的鄰接表中
*  參數列表：graph：指向圖信息的二維數組
             columns:圖的第幾條邊
*  返回結果：無
*************************************************/
void Graph::addEdge(char* graph[], int columns)
{
    Node node;
    vector v = get_graph_value(graph, columns);

    node.edge_num = v[0];
    node.src = v[1];
    node.vertex = v[2];
    node.weight = v[3];


    //根據頂點的標號，求的總的頂點數目
    if(node.vertex > vertex_num)
        vertex_num = node.vertex;

    //要考慮重復的邊，但是邊的權重不一樣
    for(list::iterator it = graph_list[node.src].begin(); it != graph_list[node.src].end(); ++it){
        if((*it).vertex == node.vertex){
            if((*it).weight > node.weight){
                (*it).weight = node.weight;   
            }
            return;
        }
    }

    //將信息寫入到保存每個頂點的數組中
    nodeArr[node.src].vertex = node.src;
    nodeArr[node.vertex].vertex = node.vertex;
    nodeArr[node.vertex].inDegree++;//入度加1 

    graph_list[node.src].push_back(node);
}


/*************************************************
*  函數名稱：構造函數
*  功能描述：以鄰接表的形式保存圖的信息,並保存必須經過的頂點
*  參數列表：graph：指向圖信息的二維數組
             edgenum:圖的邊的個數
*  返回結果：無
*************************************************/
Graph::Graph(char* graph[], int edgenum):nodeArr(MAX_VERTEX_NUM)
{
    edge_num =  edgenum; 
    vertex_num = 0;
    graph_list = new list[MAX_VERTEX_NUM+1];

    //對保存頂點信息的數組進行初始化，如果vertext=-1表示沒有該頂點
    for(int i = 0; i < MAX_VERTEX_NUM; ++i){
        nodeArr[i].vertex = -1;
        nodeArr[i].inDegree = 0;
        nodeArr[i].topNum = -1;
    }

    for(int i = 0; i < edgenum; ++i){
        addEdge(graph, i);   
    }

    vertex_num++;
}


/*************************************************
*  函數名稱：析構函數
*  功能描述：釋放動態分配的內存
*  參數列表：無
*  返回結果：無
*************************************************/
Graph::~Graph()
{
    delete[] graph_list;
}

#endif

測試函數的源代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include "graphTopoSort.h"

#define MAX_LINE_LEN 4000

int read_file(char ** const buff, const unsigned int spec, const char * const filename);
void release_buff(char ** const buff, const int valid_item_num);

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;
}

/****************************************************************
*   函數名稱：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;
}

/****************************************************************
*   函數名稱：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]);
}

測試用例：

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

運行結果：