토폴로지 정렬 및 관건 경로

46162 단어 데이터 구조
토폴로지 정렬 의 실현:
보조 배열:
  • int Indegree [100]: 각 노드 를 저장 하 는 전구 결점 개수
  • tops [10]: 정렬 된 순 서 를 저장 하 는 데 사 용 됩 니 다. 각 노드 의 입도 와 출 도 를 계산 해 야 하기 때문에 십자 링크 를 사 용 했 습 니 다.

  • 프로 세 스
  • 각 결점 의 전구 결점 개 수 를 계산 하여 indegree 에 기록한다.
  • 전구 결점 개수 가 0 인 결점 을 창고 에 넣 기;
  • 스 택 이 비어 있 지 않 을 때 출력 스 택 의 정점 은 tops 에 가입 합 니 다.모든 '차 결산 점' 을 끝 점 으로 하 는 결산 점 을 옮 겨 다 니 며 이 결산 점 의 입 도 를 1 로 줄 이 고 이 결산 점 의 입 도 를 0 으로 하면 스 택 에 가입 합 니 다.
  • #include
    #include
    using namespace std;
    struct Node
    {
        int from;
        int to;
        Node * head_same;
        Node * tail_same;
    };
    struct First_Node
    {
        string name;
        Node * in_node;
        Node * out_node;
    };
    struct Graph
    {
        int Vex_num, Edge_num;
        First_Node * Arr;
    };
    int Get_Location(Graph T, string name)
    {
        for(int i = 1; i <= T.Vex_num; i++)
        {
            if(T.Arr[i].name == name)
                return i;
        }
        return -1;
    }
    void Create_Graph(Graph & T)
    {
        cin>>T.Vex_num>>T.Edge_num;
        T.Arr = new First_Node[T.Vex_num + 1];
        for(int i = 1; i <= T.Vex_num; i++)
        {
            cin>>T.Arr[i].name;
            T.Arr[i].in_node = nullptr;
            T.Arr[i].out_node = nullptr;
        }
        int x, y; string n1, n2;
        for(int i = 1; i <= T.Edge_num; i++)
        {
            cin>>n1>>n2;
            x = Get_Location(T,n1);
            y = Get_Location(T,n2);
            Node * s = new Node;
            s->from = x;s->to = y;
            s->head_same = T.Arr[y].in_node;
            T.Arr[y].in_node = s;
            s->tail_same = T.Arr[x].out_node;
            T.Arr[x].out_node = s;
        }
    }
    void Find_Indegree(Graph T,int Indegree[])
    {
        for(int i = 1; i <= T.Vex_num; i++)
        {
            int num = 0;
            Node * s = T.Arr[i].in_node;
            while(s != nullptr)
            {
                num++;
                s = s->head_same;
            }
            Indegree[i] = num;
        }
    }
    void Topo_Sort(Graph T)
    {
        int Indegree[10];
        Find_Indegree(T,Indegree);
        stack<int> S;
        for(int i = 1; i <= T.Vex_num; i++)
        {
            if(Indegree[i] == 0)
                S.push(i);
        }
        int m = 1, tops[10];
        while(!S.empty())
        {
            int k = S.top();S.pop();
            tops[m] = k;
            m++;
            Node * s = T.Arr[k].out_node;
            while(s != nullptr)
            {
                k = s->to;
                Indegree[k]--;
                if(Indegree[k] == 0)
                    S.push(k);
                s = s->tail_same;
            }
        }
        if(m - 1 == T.Vex_num)
        {
            for(int i = 1; i <= T.Vex_num; i++)
                cout<<tops[i]<<"\t";
        }else{
            cout<<0;
        }
    }
    int main()
    {
        Graph T;
        Create_Graph(T);
        Topo_Sort(T);
    }
    /*
    6 8
    v1 v2 v3 v4 v5 v6
    v1 v6
    v1 v5
    v1 v3
    v2 v3
    v3 v4
    v4 v6
    v5 v6
    v5 v4
    */
    

    중요 경로
    #include
    #include
    #include
    using namespace std;
    struct Node
    {
        int from;
        int to;
        Node * head_same;
        Node * tail_same;
        int time;
    };
    struct First_Node
    {
        string name;
        Node * in_node;
        Node * out_node;
    };
    struct Graph
    {
        int Vex_num, Edge_num;
        First_Node * Arr;
    };
    int Get_Location(Graph T, string name)
    {
        for(int i = 1; i <= T.Vex_num; i++)
        {
            if(T.Arr[i].name == name)
                return i;
        }
        return -1;
    }
    void Create_Graph(Graph & T)
    {
        cin>>T.Vex_num>>T.Edge_num;
        T.Arr = new First_Node[T.Vex_num + 1];
        for(int i = 1; i <= T.Vex_num; i++)
        {
            cin>>T.Arr[i].name;
            T.Arr[i].in_node = nullptr;
            T.Arr[i].out_node = nullptr;
        }
        int x, y, time; string n1, n2;
        for(int i = 1; i <= T.Edge_num; i++)
        {
            cin>>n1>>n2>>time;
            x = Get_Location(T,n1);
            y = Get_Location(T,n2);
            Node * s = new Node;
            s->from = x;s->to = y;
            s->head_same = T.Arr[y].in_node;
            T.Arr[y].in_node = s;
            s->tail_same = T.Arr[x].out_node;
            T.Arr[x].out_node = s;
            s->time = time;
        }
    }
    bool Topo_Sort(Graph T,int topo[])
    {
        int Indegree[10];
        for(int i = 1; i <= T.Vex_num; i++)
        {
            int num = 0;
            Node * s = T.Arr[i].in_node;
            while(s != nullptr)
            {
                num++;
                s = s->head_same;
            }
            Indegree[i] = num;
        }
        int m = 1;stack<int> S;
        for(int i = 1; i <= T.Vex_num; i++)
            if(Indegree[i] == 0) S.push(i);
        while(!S.empty())
        {
            int k = S.top();S.pop();
            topo[m] = k;m++;
            Node * s = T.Arr[k].out_node;
            while(s != nullptr)
            {
                int j = s->to;
                Indegree[j]--;
                if(Indegree[j] == 0)
                    S.push(j);
                s = s->tail_same;
            }
        }
        if(m - 1 != T.Vex_num)
            return 0;
        else
            return 1;
    }
    void CriticalPath(Graph T)
    {
        int topo[10];
        if(!Topo_Sort(T,topo))
            return;
        int ve[10],vl[10];
        memset(ve,0,sizeof(ve));
        for(int i = 1; i <= T.Vex_num; i++)
        {
            Node * s = T.Arr[topo[i]].out_node;
            while(s != nullptr)
            {
                if(ve[topo[i]] + s->time > ve[s->to])
                    ve[s->to] = ve[topo[i]] + s->time;
                s = s->tail_same;
            }
        }
        for(int i = 1; i <= T.Vex_num; i++)
            vl[i] = ve[T.Vex_num];
        for(int i = T.Vex_num; i >= 1; i--)
        {
            Node * s = T.Arr[topo[i]].in_node;
            while(s != nullptr)
            {
                if(vl[s->from] > vl[s->to] - s->time)
                    vl[s->from] = vl[s->to] - s->time;
                s = s->head_same;
            }
        }
        for(int i = 1; i <= T.Vex_num; i++)
        {
            Node * s = T.Arr[i].out_node;
            int e, l;
            while(s != nullptr)
            {
                e = ve[i];
                l = vl[s->to] - s->time;
                if(e == l)
                    cout<<T.Arr[i].name<<"\t"<<T.Arr[s->to].name<<endl;
                s = s->tail_same;
            }
        }
    }
    int main()
    {
        Graph T;
        Create_Graph(T);
        CriticalPath(T);
    }
    /*
    9 11
    v1 v2 v3 v4 v5 v6 v7 v8 v9
    v1 v2 6
    v1 v3 4
    v1 v4 5
    v2 v5 1
    v3 v5 1
    v5 v7 9
    v5 v8 7
    v7 v9 2
    v8 v9 4
    v4 v6 2
    v6 v8 4
    */
    
    

    좋은 웹페이지 즐겨찾기