图的拓扑排序,AOV,完整实现,C++描述

body, table{font-family: 微软雅黑; font-size: 13.5pt}
table{border-collapse: collapse; border: solid gray; border-width: 2px 0 2px 0;}
th{border: 1px solid gray; padding: 4px; background-color: #DDD;}
td{border: 1px solid gray; padding: 4px;}
tr:nth-child(2n){background-color: #f8f8f8;}

AOV网(Ativity On Vertex Network):
  在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网——AOV。

拓扑序列:
  设 G = (V,E) 是一个具有n个顶点的有向图,V中的顶点序列V1,V2,……,Vn,满足若从顶点Vi到Vj有一条路径,则在顶点序列中顶点Vi必须在Vj之前。这样的一个顶点序列叫做拓扑序列。

拓扑排序:
  对一个有向图构造拓扑序列的过程。构造过程中如果网的顶点全部输出,表示不存在环(回路)的AOV网;否则不是AOV网。

拓扑排序算法:
图的拓扑排序,AOV,完整实现,C++描述
图的拓扑排序,AOV,完整实现,C++描述

AOV:3 → 1 → 2 → 6 → 0 → 4 → 5 → 8 → 7 → 12 → 9 → 10 → 13 → 11

图的拓扑排序,AOV,完整实现,C++描述
/* AOV.h */
#ifndef __AOV_H__
#define __AOV_H__
#include<iostream>
#include"Graph.h"
namespace meihao
{
        //边表结点
        typedef struct EdgeNode
        {
                int vertexIdx;  //邻接点域,存放该结点在顶点表数组中的下标
                struct EdgeNode* next;  //存放下一个边表结点的位置
        }edgeNode,*pEdgeNode;
        //顶点表结点
        typedef struct VertexNode
        {
                int in;  //顶点入度
                int data;  //顶点与,存放顶点数据信息
                edgeNode* firstEdge;
        }vertexNode,*pVertexNode;
        void initDataStruct(const meihao::Graph& g,vertexNode*& vertexArr);  //根据图来初始化出我们要的顶点数组和对应的边表
        int TopologicalSort_AOV(const meihao::Graph& g);  //成功返回0,失败返回-1
};
#endif



/* testmain.cpp */
#include"AOV.h"
#include"Graph.h"
#include<iostream>
using namespace std;
int main()
{
        meihao::Graph g("data.txt");
        int ret = meihao::TopologicalSort_AOV(g);
        if(0==ret)
                cout<<"success!"<<endl;
        else
                cout<<"fail!"<<endl;
        system("pause");
}
图的拓扑排序,AOV,完整实现,C++描述
/* AOV.cpp */
#include"AOV.h"
#include<stack>
namespace meihao
{
        void initDataStruct(const meihao::Graph& g,vertexNode*& vertexArr)
        {
                int vertexNum = g.getGraphVertexNumber();
                vertexArr = new vertexNode[vertexNum]();  //建立顶点数组
                for(int idx=0;idx!=vertexNum;++idx)
                {
                        vertexArr[idx].data = idx;
                        vertexArr[idx].in = g.getInputDegree(idx);  //获取入度
                        vertexArr[idx].firstEdge = nullptr;
                }
                for(int idx=0;idx!=vertexNum;++idx)
                {
                        for(int iidx=0;iidx!=vertexNum;++iidx)
                        {
                                if(1==g.getGraphEdgeWeight(idx,iidx))
                                {
                                        edgeNode* tmp = new edgeNode();
                                        tmp->vertexIdx = iidx;
                                        tmp->next = vertexArr[idx].firstEdge;
                                        vertexArr[idx].firstEdge = tmp;
                                }
                        }
                }
        }
        int TopologicalSort_AOV(const meihao::Graph& g)
        {
                stack<int> zeroInputDegreeVertex;
                int vertexNum = g.getGraphVertexNumber();
                vertexNode* vertexArr = nullptr;  //建立顶点表数组
                initDataStruct(g,vertexArr);  //建立顶点边和对应的边表
                for(int idx=0;idx!=vertexNum;++idx)
                {
                        if(0==vertexArr[idx].in)
                        {
                                zeroInputDegreeVertex.push(idx);
                        }
                }
                //遍历输出拓扑排序
                int cnt = 0;  //统计拓扑排序输出的点数,如果cnt最后不等于图的顶点数,说明不是AOV
                while(!zeroInputDegreeVertex.empty())
                {
                        int idx = zeroInputDegreeVertex.top();
                        cout<<vertexArr[idx].data<<" ";  //输出一个度为0的顶点
                        zeroInputDegreeVertex.pop();
                        ++cnt;
                        for(edgeNode* node = vertexArr[idx].firstEdge;nullptr!=node;node=node->next)
                        { //删除了一个度为0的顶点,对应其出边表中的顶点的入得要减1
                                vertexArr[node->vertexIdx].in--;
                                if( 0==(vertexArr[node->vertexIdx].in) )
                                        zeroInputDegreeVertex.push( node->vertexIdx );
                        }
                }
                if(vertexNum==cnt)
                        return 0;
                else
                        return -1;
        }
};

上一篇:「Foundation」结构体


下一篇:Geo命令