有向图--拓扑排序

拓扑排序方法：

①从有向图中选一个没有前驱的顶点且输出之。

②从有向图中删除该顶点和所有以他为尾的弧。

重复上述两步，直至所有顶点已输出，或当期图中不存在无前驱的顶点为止。后一种情况说明有向图中有环！

 

1. 采用邻接矩阵存储

//图的邻接矩阵存储表示
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}
typedef enum {OK, ERROR} Status;
typedef struct ArcCell{
    int adj;        //顶点关系类型。对于无权图，用0或1表示相邻否。对于有权图，则为权值类型。
    string info;    //该弧所携带的信息
}ArcCell, AdjMatrix;
typedef struct {
    int vexs[MAX_VERTEX_NUM];   //顶点向量
    AdjMatrix arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];             //邻接矩阵
    int vexnum, arcnum;         //图的当前顶点数和弧数
    GraphKind kind;             //图的种类标志
}MGraph;

//图的邻接矩阵存储表示 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网} typedef enum {OK, ERROR} Status; typedef struct ArcCell{ int adj; //顶点关系类型。对于无权图，用0或1表示相邻否。对于有权图，则为权值类型。 string info; //该弧所携带的信息 }ArcCell, AdjMatrix; typedef struct { int vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph; 

 

2. 用函数构造一个有向图

void CreateDGTest(MGraph &G)
{   //构造一个有向图
    int i,j;
    G.kind = DN;
    //数组a[11][2]用来存储有向边
    int a[13][2] = { {0,1}, {0,2}, {0,3}, {1,4}, {2,4}, {3,5}, {4,6}, {4,7}, {5,7}, {6,8}, {7,8}, {2,1}, {7,6}};
    G.vexnum = 9;
    G.arcnum = 13;
    for(i=0; i
        G.vexs[i] = i;
    for(i=0; i
        for(j=0; j
        {
            G.arcs[i][j].adj = 0;
            G.arcs[i][j].info = "";
        };
    for(i=0; i
        G.arcs[a[i][0]][a[i][1]].adj = 1;
}

void CreateDGTest(MGraph &G) { //构造一个有向图 int i,j; G.kind = DN; //数组a[11][2]用来存储有向边 int a[13][2] = { {0,1}, {0,2}, {0,3}, {1,4}, {2,4}, {3,5}, {4,6}, {4,7}, {5,7}, {6,8}, {7,8}, {2,1}, {7,6}}; G.vexnum = 9; G.arcnum = 13; for(i=0; i

 

3. 拓扑排序函数

Status TopologicalSortT(MGraph G)
{   //有向图采用邻接矩阵存储
    //若G无回路，则输出G的顶点的一个拓扑序列，并返回OK，否则ERROR
    int i,j;
    int indegree[MAX_VERTEX_NUM];       //存储各顶点入度
    int topo[MAX_VERTEX_NUM];           //存储顶点拓扑序列
    int num=0;                          //计数已经输出/存储的顶点
    int sp=-1;                          //存储下一步需要删除的边的尾的前一点
    for(i=0; i
    {   //计算各顶点入度
        indegree[i] = 0;
        for(j=0; j
            if(G.arcs[j][i].adj != 0 && i!=j)
                indegree[i]++;
        if(indegree[i]==0)
        {
            topo[num] = i;
            num++;
        }
    }
    while(sp < num)
    {   //sp
        sp++;
        for(i=0; i
            if(G.arcs[sp][i].adj != 0)
            {
                indegree[i]--;
                if(indegree[i] == 0)
                {
                    topo[num] = i;
                    num++;
                }
            }
    };
    if(num
        return ERROR;
    cout<<"拓扑序列如下：";
    for(i=0; i
        cout<
    cout<
    return OK;
}

Status TopologicalSortT(MGraph G) { //有向图采用邻接矩阵存储 //若G无回路，则输出G的顶点的一个拓扑序列，并返回OK，否则ERROR int i,j; int indegree[MAX_VERTEX_NUM]; //存储各顶点入度 int topo[MAX_VERTEX_NUM]; //存储顶点拓扑序列 int num=0; //计数已经输出/存储的顶点 int sp=-1; //存储下一步需要删除的边的尾的前一点 for(i=0; i

 

4. 拓扑排序函数-利用堆栈

Status TopologicalSortStack(MGraph G)
{   //有向图采用邻接矩阵存储
    //借助堆栈实现
    //若G无回路，则输出G的顶点的一个拓扑序列，并返回OK，否则ERROR
    int i,j;
    int indegree[MAX_VERTEX_NUM];       //存储各顶点入度
    int num=0;                          //计数已经输出/存储的顶点
    LinkStack S;
    InitStack(S);
    for(i=0; i
    {   //计算各顶点入度
        indegree[i] = 0;
        for(j=0; j
            if(G.arcs[j][i].adj != 0 && i!=j)
                indegree[i]++;
        if(indegree[i]==0)  //零入度顶点进栈
            Push(S,i);
    }
    while(!StackEmpty(S))
    {   //栈非空
        Pop(S, i);
        cout<
        ++num;      //对输出顶点计数
        for(j=0; j
            if(G.arcs[i][j].adj != 0)   //对顶点i的每个邻接点入度减1
            {
                indegree[j]--;
                if(indegree[j] == 0)    //若入度减为0，则进栈
                    Push(S, j);
            }
    };
    if(num//该图有有向回路
        return ERROR;
    return OK;
}

Status TopologicalSortStack(MGraph G) { //有向图采用邻接矩阵存储 //借助堆栈实现 //若G无回路，则输出G的顶点的一个拓扑序列，并返回OK，否则ERROR int i,j; int indegree[MAX_VERTEX_NUM]; //存储各顶点入度 int num=0; //计数已经输出/存储的顶点 LinkStack S; InitStack(S); for(i=0; i

 

5. 测试用主函数

view plaincopy to clipboardprint?

int main()
{
    MGraph gra3;
    CreateDGTest(gra3);
    if(TopologicalSortT(gra3) != OK)
        cout<<"该有向图存在环！"<
    return 0;
}

http://blog.csdn.net/hustspy1990/article/details/6044098