数据结构 拓扑排序

注：有向无环图（DAG图）
AOV网：用顶点表示活动，用弧表示活动之间的优先关系的有向图称为顶点表示活动的网

注：AOV网一定是有向无环图

拓扑序列：对于一个有n个顶点的有向图，顶点序列v1,v2...vn若满足从顶点vi到vj有一条路径，则顶点序列中vi必在vj之前，这样的一个顶点序列为一个拓扑序列

拓扑排序：对一个有向无环图构造拓扑排序的过程（同时还可以判断图内部是否成环）
    1.在有向图中选一个没有前驱的顶点并输出
    2.从图中删除该顶点和所有以他为尾的弧
    重复上述两步，直至全部顶点均已输出，或者当前图不存在无前驱的顶点为止，后一种情况说明有向图中存在环

应用：拓扑序列，关键路径

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//引入一个栈，用于保存所有入度为零的的点的下标
class Stack_Node
{
public:
    int data;
    Stack_Node* next;
};
class m_Stack
{
public:
    Stack_Node* head;
public:
    m_Stack()
    {
        head = new Stack_Node;
        if (head == nullptr)
        {
            cout << "开辟失败" << endl;
        }
        else
        {
            head->next = nullptr;
        }
    }
    void m_push(int k)
    {
        Stack_Node* s = new Stack_Node;
        s->data = k;
        s->next = head->next;
        head->next = s;
    }
    int m_pop()
    {
        if (head->next == nullptr)
        {
            cout << "栈空" << endl;
            return -1;
        }
        else
        {
            int ret(0);
            Stack_Node* p = head->next;
            head->next = p->next;
            ret = p->data;
            delete p;
            p = nullptr;
            return ret;
        }
    }
};


//邻接表存有向图
class List_Node
{
public:
    int data;//邻接点下标
    List_Node* next;
};
class Graph_Node
{
public:
    char data;//顶点编号
    List_Node* first;//出边链表头指针
};
class Graph
{
public:
    int size1;//点的个数
    int size2;//边的个数
    Graph_Node* g;//邻接表
    int* ind;//入度数组
    char* topo;//拓扑序列
public:
    Graph(int sz1,int sz2):size1(sz1),size2(sz2)
    {
        g = new Graph_Node[sz1];
        ind = new int[sz1];
        topo = new char[sz1];
        if (g == nullptr || ind == nullptr || topo == nullptr)
        {
            cout << "开辟失败" << endl;
        }
        else
        {
            //初始化点
            for (int i = 0; i < sz1; ++i)
            {
                cin >> g[i].data;
                g[i].first = nullptr;
                ind[i] = 0;
                topo[i] = 0;
            }
            //输入边
            char x(0);
            char y(0);
            int xi(0);
            int yi(0);
            for (int i = 0; i < sz2; ++i)
            {
                cin >> x >> y;

                //找x,y对应下标
                xi = find(x);
                yi = find(y);

                //y为x邻接点
                List_Node* s = new List_Node;
                s->data = yi;
                //进行头插
                s->next = g[xi].first;
                g[xi].first = s;
                //统计y入度
                ind[yi]++;
            }
        }
    }
    int find(char k)
    {
        for (int i = 0; i < size1; ++i)
        {
            if (g[i].data == k)
            {
                return i;
            }
        }
        return -1;
    }
    bool topo_sort()
    {
        bool flag = false;//判断能否找到拓扑序列
        //引入一个栈，用于保存所有入度为零的的点的下标
        m_Stack s;
        for (int i = 0; i < size1; ++i)
        {
            if (ind[i] == 0)
            {	
                s.m_push(i);
            }
        }
        int v_i(0);//出栈点的下标
        //j为topo数组下标
        for (int i = 0,j = 0; i < size1; ++i,++j)
        {
            v_i = s.m_pop();
            if (v_i == -1)
            {
                flag = false;//找不到拓扑序列
                break;
            }
            //删除（并没有真正删除，只是入度减一）
            topo[j] = g[v_i].data;
            List_Node* p = g[v_i].first;
            int a(0);//存储入度数组下标
            while (p != nullptr)
            {
                a = p->data;
                ind[a]--;
                if (ind[a] == 0)
                {
                    s.m_push(a);
                }
                p = p->next;
            }
            if (i == size1 - 1)
            {
                flag = true;
            }
        }
        if (flag == false)
        {
            cout << "该图带环，无拓扑序列" << endl;
            return flag;
        }
        else
        {
            cout << "该图拓扑序列为：" << endl;
            for (int i = 0; i < size1; ++i)
            {
                cout << topo[i] << ' ';
            }
            return flag;
        }
    }
};
int main()
{
    Graph g(6, 8);
    g.topo_sort();
    return 0;
}
/*
6 8
A B C D E F
A B
A C
A D
C B
C E
F D
F E
D E
*/