程序员经验分享-hwhale

数据结构-图

2023-11-04

目录

问题 A: 邻接矩阵存储的图，节点的出度和入度计算(附加代码模式)

问题 B: 算法7-12：有向无环图的拓扑排序

问题 C: 有向图是否存在环？

问题 D: 是否为有效的拓扑序列

问题 E: 案例6-2.6：最短工期

问题 F: 图-节点的最早发生时间

问题 G: 图-节点的最迟发生时间

问题 H: 图-边的最早发生时间

问题 I: 图-边的最迟发生时间

问题 J: 图-图的关键路径

仅作储存代码用。

问题 A: 邻接矩阵存储的图，节点的出度和入度计算(附加代码模式)

题目描述

可以用邻接矩阵的方式去存储一个图，要求计算这种方式下每个节点的入度和出度。
本题为附加代码模式，以下代码为自动附加在同学们提交的代码后面。在本题的提示中有代码框架，请同学们拷贝后，修改，再注释掉部分代码，最后提交。
 

// please comment the following code when you submit to OJ

int main(){

    //freopen("/config/workspace/answer/test.in","r",stdin);

    Graph g;

    cin >> g.nodeNumber;

    int inDegree[g.nodeNumber] = {0}, outDegree[g.nodeNumber] = {0};

    for(int i=0;i<g.nodeNumber;i++){

        for(int j=0;j<g.nodeNumber;j++){

            cin >> g.adjMatrix[i][j];

        }

    }

    CalculateDegree(g, inDegree, outDegree);

    for(int i=0;i<g.nodeNumber;i++){

        cout << inDegree[i] << " " << outDegree[i] << endl;

    }

    return 0;

}

输入格式

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。 注意输入的邻接矩阵不一定为对称矩阵，即输入的图一定是可能是有向图，也可能是无向图。

输出格式

对每一个节点，输出其入度和出度

输入样例 复制

4
0 1 0 1
1 0 0 0
0 0 0 1
1 0 1 0

输出样例 复制

2 2
1 1
1 1
2 2

数据范围与提示

代码框架如下：

#include <iostream>

#include <cstdio>

using namespace std;

#define MAX_SIZE 100

struct Graph{

    int nodeNumber;

    int adjMatrix[MAX_SIZE][MAX_SIZE];

};

// 计算每个节点的出度和入度

void CalculateDegree(const Graph& g, int inDegree[], int outDegree[]){

    

}

// please comment the following code when you submit to OJ

int main(){

    // freopen("/config/workspace/answer/test.in","r",stdin);

    Graph g;

    cin >> g.nodeNumber;

    int inDegree[g.nodeNumber] = {0}, outDegree[g.nodeNumber] = {0};

    for(int i=0;i<g.nodeNumber;i++){

        for(int j=0;j<g.nodeNumber;j++){

            cin >> g.adjMatrix[i][j];

        }

    }

    CalculateDegree(g, inDegree, outDegree);

    for(int i=0;i<g.nodeNumber;i++){

        cout << inDegree[i] << " " << outDegree[i] << endl;

    }

    return 0; 

}

#include<bits/stdc++.h>
using namespace std;
 
#define MAX_SIZE 100
 
struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE];
};
 
void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}
 
// int main()
// {
//     Graph g;
//     cin>>g.nodeNumber;
//     int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
//     for(int i=0;i<g.nodeNumber;i++)
//     {
//         for(int j=0;j<g.nodeNumber;j++)
//         cin>>g.adjMatrix[i][j];
//     }
//     CalculateDegree(g,inDegree,outDegree);
//     for(int i=0;i<g.nodeNumber;i++)
//     cout<<inDegree[i]<<" "<<outDegree[i]<<endl;
//     return 0;
// }

问题 B: 算法7-12：有向无环图的拓扑排序

题目描述

由某个集合上的一个偏序得到该集合上的一个全序，这个操作被称为拓扑排序。偏序和全序的定义分别如下：

若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。

设R是集合X上的偏序，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。

由偏序定义得到拓扑有序的操作便是拓扑排序。

拓扑排序的流程如下：

1.       在有向图中选一个没有前驱的顶点并且输出之；

2.       从图中删除该顶点和所有以它为尾的弧。

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

采用邻接表存储有向图，并通过栈来暂存所有入度为零的顶点，可以描述拓扑排序的算法如下：

在本题中，读入一个有向图的邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法判断此图是否有回路，如果没有回路则输出拓扑有序的顶点序列。

输入格式

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个整数，如果为1，则表示第i个顶点有指向第j个顶点的有向边，0表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。

输出格式

如果读入的有向图含有回路，请输出“ERROR”，不包括引号。 如果读入的有向图不含有回路，请按照题目描述中的算法依次输出图的拓扑有序序列，每个整数后输出一个空格。 请注意行尾输出换行。

输入样例 复制

4
0 1 0 0
0 0 1 0
0 0 0 0
0 0 1 0

输出样例 复制

3 0 1 2

数据范围与提示

*** 提示已隐藏，点击此处可显示 ***

收起提示[-]

在本题中，需要严格的按照题目描述中的算法进行拓扑排序，并在排序的过程中将顶点依次储存下来，直到最终能够判定有向图中不包含回路之后，才能够进行输出。 另外，为了避免重复检测入度为零的顶点，可以通过一个栈结构维护当前处理过程中入度为零的顶点。

#include<bits/stdc++.h>
using namespace std;
 
#define MAX_SIZE 100
 
struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE];
};
 
void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}
 
 
void mysort(Graph g,int indegree[])
{
    stack<int>s;
    int ans[g.nodeNumber];
    int index=0;
    int i=0;
    for(i=0;i<g.nodeNumber;i++)
    {
        if(!indegree[i])
        {
            g.adjMatrix[i][i]=1;
            s.push(i);
        }
    }
    while(s.size()!=0)
    {
        ans[index++]=s.top();
        i=s.top();
        s.pop();
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]!=0&&i!=j)
            {
                g.adjMatrix[i][j]=0;
                indegree[j]--;
            }
            if(g.adjMatrix[j][j]==0&&indegree[j]==0)
            {
                g.adjMatrix[j][j]=1;
                s.push(j);
            }
        }
    }
    if(index<g.nodeNumber)
    cout<<"ERROR"<<endl;
    else
    {
        for(int i=0;i<index;i++)
        cout<<ans[i]<<" ";
    }
     
}
int main()
{
    Graph g;
    cin>>g.nodeNumber;
    int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        cin>>g.adjMatrix[i][j];
    }
    CalculateDegree(g,inDegree,outDegree);
    mysort(g,inDegree);
    return 0;
}

问题 C: 有向图是否存在环？

题目描述

写程序判断有向图是否存在环。有向图的输入用n个二元组表示(u,v)，表示从u到v有一条有向边，起点是u，终点是v。

输入格式

输入包括多组测试数据，每组测试数据首先是正整数n和m，表示有向图有n个节点（编号从1到n），m条有向边，接下来是m行，每行为两个正整数u和v，用空格隔开，表示从节点u到节点v有一条有向边，u和v都大于等于1且小于等于n
最后一行为0 0，表示测试数据结束
有向图的节点个数不超过100个，边的个数不超过1000

输出格式

如果该有向图存在环，输出YES，否则输出NO

输入样例 复制

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

输出样例 复制

NO
YES
YES
#include<bits/stdc++.h>
using namespace std;
 
#define MAX_SIZE 100
 
struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE];
    int vexNumber;
};
 
void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}
 
 
void mysort(Graph g,int indegree[])
{
    stack<int>s;
    int ans[g.nodeNumber];
    int index=0;
    int i=0;
    for(i=0;i<g.nodeNumber;i++)
    {
        if(!indegree[i])
        {
            g.adjMatrix[i][i]=1;
            s.push(i);
        }
    }
    while(s.size()!=0)
    {
        ans[index++]=s.top();
        i=s.top();
        s.pop();
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]!=0&&i!=j)
            {
                g.adjMatrix[i][j]=0;
                indegree[j]--;
            }
            if(g.adjMatrix[j][j]==0&&indegree[j]==0)
            {
                g.adjMatrix[j][j]=1;
                s.push(j);
            }
        }
    }
    if(index<g.nodeNumber)
    cout<<"ERROR"<<endl;
    else
    {
        for(int i=0;i<index;i++)
        cout<<ans[i]<<" ";
    }
     
}
int main()
{
    Graph g;
    while(cin>>g.nodeNumber>>g.vexNumber)
    {
        if(g.nodeNumber==0&&g.vexNumber==0)
        break;
        int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
        for(int i=0;i<g.vexNumber;i++)
        {
            int x,y;
            cin>>x>>y;
            g.adjMatrix[x][y]=1;
        }
        if(g.vexNumber>=g.nodeNumber)
        cout<<"YES"<<endl;
        else
        cout<<"NO"<<endl;
    }
    return 0;
}

问题 D: 是否为有效的拓扑序列

题目描述

在一个有向无环图中，可能存在多种有效拓扑序列。以下图为例：


存在两种可行的拓扑序列：
0 1 2 3 4
0 2 1 3 4
本题会给出一个图，以及多个序列，你来判断每一个序列是否是该图的有效拓扑序列。

输入格式

第一行为2个正整数m和n，分别表示有向无环图的节点个数和边的数量。
接下来n行，代表n条边。分别是起点、终点、权重，以空格分隔。
（m<50,n<100）


接下来为一个正整数o，表示接下来会出现的序列个数。
（o<1000）
再往后是o个序列，序列中的每个值用空格隔开。

输出格式

按行输出：o个序列中，每一个序列是否为图的有效拓扑序列。
是的话输出：YES
不是的话输出：NO

输入样例 复制

5 6
0 1
0 2
1 3
2 3
2 4
3 4
3
0 1 2 3 4
0 2 1 3 4
0 1 3 2 4

输出样例 复制

YES
YES
NO
#include<bits/stdc++.h>
using namespace std;
 
#define MAX_SIZE 100
 
struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE]={0};
    int vexNumber;
};
 
void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}
 
 
void judge(const Graph G,const int inDegree[], queue<int>a)
{
    Graph g=G;
    int indegree[g.nodeNumber];
    for(int i=0;i<g.nodeNumber;i++)
    indegree[i]=inDegree[i];
    int i=0;
    while(a.size()!=0)
    {
        i=a.front();
        if(indegree[a.front()]!=0)
        {
            cout<<"NO"<<endl;
            return ;
        }
        a.pop();
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1&&i!=j)
            {
                g.adjMatrix[i][j]=0;
                indegree[j]--;
            }
        }
    }
    cout<<"YES"<<endl;
    return ;
}
int main()
{
    Graph g;
    cin>>g.nodeNumber>>g.vexNumber;
    int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
    for(int i=0;i<g.vexNumber;i++)
    {
        int x,y;
        cin>>x>>y;
        g.adjMatrix[x][y]=1;
    }
    CalculateDegree(g,inDegree,outDegree);
    int n;
    cin>>n;
    while(n--)
    {
        int temp;
        queue<int>a;
        for(int i=0;i<g.nodeNumber;i++)
        {
            cin>>temp;
            a.push(temp);
        }
        judge(g,inDegree,a);
    }
    return 0;
}

问题 E: 案例6-2.6：最短工期

题目描述

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式

首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。

输出格式

如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

输入样例 复制

9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

输出样例 复制

18

数据范围与提示

如果有10万个里程碑顶点，但最后只有2个终点，则用扫描全部顶点的办法找最早结束时间比较大的那个顶点显然相当浪费。可以再加一个堆栈（或队列），将所有的终点入栈，则最后只需要检查这个栈里的顶点就可以了。试尝试这种思路。

#include<bits/stdc++.h>
using namespace std;
 
#define MAX_SIZE 100
 
struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE]={-1};
    int vexNumber;
};
 
void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]!=-1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}
 
 
void judge(const Graph G,const int inDegree[], queue<int>a)
{
    Graph g=G;
    int indegree[g.nodeNumber];
    for(int i=0;i<g.nodeNumber;i++)
    indegree[i]=inDegree[i];
    int i=0;
    while(a.size()!=0)
    {
        i=a.front();
        if(indegree[a.front()]!=0)
        {
            cout<<"NO"<<endl;
            return ;
        }
        a.pop();
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1&&i!=j)
            {
                g.adjMatrix[i][j]=0;
                indegree[j]--;
            }
        }
    }
    cout<<"YES"<<endl;
    return ;
}
int main()
{
    Graph g;
    int cnt=0;
    cin>>g.nodeNumber>>g.vexNumber;
    int dis[MAX_SIZE]={0};
    int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        g.adjMatrix[i][j]=-1;
    }
    for(int i=0;i<g.vexNumber;i++)
    {
        int x,y,time;
        cin>>x>>y>>time;
        g.adjMatrix[x][y]=time;
    }
    CalculateDegree(g,inDegree,outDegree);
    stack<int>s;
    for(int i=0;i<g.nodeNumber;i++)
    {
        if(inDegree[i]==0)
        {
            s.push(i);
            dis[i]=0;
        }
    }
    while(!s.empty())
    {
        int t=s.top();
        s.pop();
        cnt++;
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[t][i]!=-1)
            {
                inDegree[i]--;
                if(inDegree[i]==0)
                s.push(i);
                if(dis[t]+g.adjMatrix[t][i]>dis[i])
                dis[i]=dis[t]+g.adjMatrix[t][i];
            }
        }
    }
    if(cnt<g.nodeNumber)
    cout<<"Impossible"<<endl;
    else
    {
        int maxl=0;
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(dis[i]>maxl)
            maxl=dis[i];
        }
        cout<<maxl<<endl;
    }
    return 0;
}

问题 F: 图-节点的最早发生时间

题目描述

下图是一个有向无环图，节点内的数字表示该节点的序号，节点之间的连接线表示节点之间的连接方式，连接线上方的黑色数字表示该连接线的权重。
最早发生时间：从前往后，前驱节点到当前节点所需时间，取最大值
本题要求：求出有向无环图中每一个节点的最早发生时间（示例图中每一个节点的最早发生时间以节点上方的黄色数字标出）
 

输入格式

第一行为2个正整数m和n，分别表示有向无环图的节点个数和边的数量。
接下来n行，代表n条边。分别是起点、终点、权重，以空格分隔。
（m<50,n<100）

输出格式

按行输出有向无环图中每一个节点最早发生时间，按照节点的序号从小到大输出。
如样例中，0、1、2、3、4号节点的最早发生时间分别是0、3、3、7、11。
则按行输出0、3、3、7、11。

输入样例 复制

5 6
0 1 3
0 2 3
1 3 2
2 3 4
2 4 4
3 4 4

输出样例 复制

0
3
3
7
11

数据范围与提示

#include<bits/stdc++.h>
using namespace std;
 
#define MAX_SIZE 100
 
struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE]={-1};
    int vexNumber;
};
 
void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]!=-1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}
 
 
void judge(const Graph G,const int inDegree[], queue<int>a)
{
    Graph g=G;
    int indegree[g.nodeNumber];
    for(int i=0;i<g.nodeNumber;i++)
    indegree[i]=inDegree[i];
    int i=0;
    while(a.size()!=0)
    {
        i=a.front();
        if(indegree[a.front()]!=0)
        {
            cout<<"NO"<<endl;
            return ;
        }
        a.pop();
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1&&i!=j)
            {
                g.adjMatrix[i][j]=0;
                indegree[j]--;
            }
        }
    }
    cout<<"YES"<<endl;
    return ;
}
int main()
{
    Graph g;
    int cnt=0;
    cin>>g.nodeNumber>>g.vexNumber;
    int dis[MAX_SIZE]={0};
    int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        g.adjMatrix[i][j]=-1;
    }
    for(int i=0;i<g.vexNumber;i++)
    {
        int x,y,time;
        cin>>x>>y>>time;
        g.adjMatrix[x][y]=time;
    }
    CalculateDegree(g,inDegree,outDegree);
    stack<int>s;
    for(int i=0;i<g.nodeNumber;i++)
    {
        if(inDegree[i]==0)
        {
            s.push(i);
            dis[i]=0;
        }
    }
    while(!s.empty())
    {
        int t=s.top();
        s.pop();
        cnt++;
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[t][i]!=-1)
            {
                inDegree[i]--;
                if(inDegree[i]==0)
                s.push(i);
                if(dis[t]+g.adjMatrix[t][i]>dis[i])
                dis[i]=dis[t]+g.adjMatrix[t][i];
            }
        }
    }
    if(cnt<g.nodeNumber)
    cout<<"Impossible"<<endl;
    else
    {
        int maxl=0;
        for(int i=0;i<g.nodeNumber;i++)
        {
            cout<<dis[i]<<endl;
        }
    }
    return 0;
}

问题 G: 图-节点的最迟发生时间

题目描述

下图是一个有向无环图，节点内的数字表示该节点的序号，节点之间的连接线表示节点之间的连接方式，连接线上方的黑色数字表示该连接线的权重。
最迟发生时间：后序节点的最迟发生时间减去此边权值，取最小值
本题要求：通过逆拓扑序，求出有向无环图中每一个节点的最迟发生时间（示例图中每一个节点的最迟发生时间以节点上方的红色数字标出）
 

输入格式

第一行为2个正整数m和n，分别表示有向无环图的节点个数和边的数量。
接下来n行，代表n条边。分别是起点、终点、权重，以空格分隔。
（m<50,n<100）
 

输出格式

按行输出有向无环图中每一个节点最迟发生时间，按照节点的序号从小到大输出。
如样例中，0、1、2、3、4号节点的最迟发生时间分别是0、5、3、7、11。
则按行输出0、5、3、7、11。

输入样例 复制

5 6
0 1 3
0 2 3
1 3 2
2 3 4
2 4 4
3 4 4

输出样例 复制

0
5
3
7
11

数据范围与提示

#include<bits/stdc++.h>
using namespace std;
 
#define MAX_SIZE 100
 
struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE]={-1};
    int vexNumber;
};
 
void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]!=-1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}
 
 
void judge(const Graph G,const int inDegree[], queue<int>a)
{
    Graph g=G;
    int indegree[g.nodeNumber];
    for(int i=0;i<g.nodeNumber;i++)
    indegree[i]=inDegree[i];
    int i=0;
    while(a.size()!=0)
    {
        i=a.front();
        if(indegree[a.front()]!=0)
        {
            cout<<"NO"<<endl;
            return ;
        }
        a.pop();
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1&&i!=j)
            {
                g.adjMatrix[i][j]=0;
                indegree[j]--;
            }
        }
    }
    cout<<"YES"<<endl;
    return ;
}
int main()
{
    Graph g;
    cin>>g.nodeNumber>>g.vexNumber;
    int dis[MAX_SIZE]={0};
    int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        g.adjMatrix[i][j]=-1;
    }
    for(int i=0;i<g.vexNumber;i++)
    {
        int x,y,time;
        cin>>x>>y>>time;
        g.adjMatrix[x][y]=time;
    }
    CalculateDegree(g,inDegree,outDegree);
    stack<int>s;
    stack<int>s1;
    stack<int>s2;
    for(int i=0;i<g.nodeNumber;i++)
    {
        if(inDegree[i]==0)
        {
            s.push(i);
        }
        if(outDegree[i]==0)
        {
            s1.push(i);
            s2.push(i);
        }
    }
    while(!s.empty())
    {
        int t=s.top();
        s.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[t][i]!=-1)
            {
                inDegree[i]--;
                if(inDegree[i]==0)
                s.push(i);
                if(dis[t]+g.adjMatrix[t][i]>dis[i])
                dis[i]=dis[t]+g.adjMatrix[t][i];
            }
        }
    }
    int outdegree[MAX_SIZE]={0};
    for(int i=0;i<g.nodeNumber;i++)
    outdegree[i]=outDegree[i];
    while(!s1.empty())
    {
        int t=s1.top();
        s1.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[i][t]!=-1)
            {
                outDegree[i]--;
                if(outDegree[i]==0)
                s1.push(i);
                dis[i]=dis[t]-g.adjMatrix[i][t];
            }
        }
    }
    while(!s2.empty())
    {
        int t=s2.top();
        s2.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[i][t]!=-1)
            {
                outdegree[i]--;
                if(outdegree[i]==0)
                s2.push(i);
                if(dis[t]-g.adjMatrix[i][t]<dis[i])
                dis[i]=dis[t]-g.adjMatrix[i][t];
            }
        }
    }
    for(int i=0;i<g.nodeNumber;i++)
    cout<<dis[i]<<endl;
}

问题 H: 图-边的最早发生时间

题目描述

下图是一个有向无环图，节点内的数字表示该节点的序号，节点之间的连接线表示节点之间的连接方式，连接线上方的黑色数字表示该连接线的权重。
本题要求：求出有向无环图中每一个边的最早发生时间（示例图中每一个边的最早发生时间以边旁边的黄色数字标出）
 

输入格式

第一行为2个正整数m和n，分别表示有向无环图的节点个数和边的数量。
接下来n行，代表n条边。分别是起点、终点、权重，以空格分隔。
（m<50,n<100）
 

输出格式

按行输出有向无环图中每一个边的最早发生时间，按照输入样例中边的输入次序输出。
如输入样例中，边的输入次序为：
0-->1
0-->2
1-->3
2-->3
2-->4
3-->4
则输出样例中，按行分别输出上述边的最早发生时间：0、0、3、3、3、7

输入样例 复制

5 6
0 1 3
0 2 3
1 3 2
2 3 4
2 4 4
3 4 4

输出样例 复制

0
0
3
3
3
7

数据范围与提示

#include<bits/stdc++.h>
using namespace std;

#define MAX_SIZE 100

struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE]={-1};
    int edgNumber;
};

struct edg{
    int start;
    int end;
    int time;
}a[MAX_SIZE];

void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]!=-1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}


void judge(const Graph G,const int inDegree[], queue<int>a)
{
    Graph g=G;
    int indegree[g.nodeNumber];
    for(int i=0;i<g.nodeNumber;i++)
    indegree[i]=inDegree[i];
    int i=0;
    while(a.size()!=0)
    {
        i=a.front();
        if(indegree[a.front()]!=0)
        {
            cout<<"NO"<<endl;
            return ;
        }
        a.pop();
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1&&i!=j)
            {
                g.adjMatrix[i][j]=0;
                indegree[j]--;
            }
        }
    }
    cout<<"YES"<<endl;
    return ;
}
int main()
{
    Graph g;
    cin>>g.nodeNumber>>g.edgNumber;
    int dis[MAX_SIZE]={0};
    int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        g.adjMatrix[i][j]=-1;
    }
    for(int i=0;i<g.edgNumber;i++)
    {
        int x,y,time;
        cin>>x>>y>>time;
        g.adjMatrix[x][y]=time;
        a[i].start=x;
        a[i].end=y;
        a[i].time=time;
    }
    CalculateDegree(g,inDegree,outDegree);
    stack<int>s;
    stack<int>s1;
    stack<int>s2;
    for(int i=0;i<g.nodeNumber;i++)
    {
        if(inDegree[i]==0)
        {
            s.push(i);
        }
        if(outDegree[i]==0)
        {
            s1.push(i);
            s2.push(i);
        }
    }
    while(!s.empty())
    {
        int t=s.top();
        s.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[t][i]!=-1)
            {
                inDegree[i]--;
                if(inDegree[i]==0)
                s.push(i);
                if(dis[t]+g.adjMatrix[t][i]>dis[i])
                dis[i]=dis[t]+g.adjMatrix[t][i];
            }
        }
    }
    // for(int i=0;i<g.nodeNumber;i++)
    // cout<<dis[i]<<endl;
    for(int i=0;i<g.edgNumber;i++)
    {
        a[i].time=dis[a[i].start];
    }
    int outdegree[MAX_SIZE]={0};
    for(int i=0;i<g.nodeNumber;i++)
    outdegree[i]=outDegree[i];
    while(!s1.empty())
    {
        int t=s1.top();
        s1.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[i][t]!=-1)
            {
                outDegree[i]--;
                if(outDegree[i]==0)
                s1.push(i);
                dis[i]=dis[t]-g.adjMatrix[i][t];
            }
        }
    }
    while(!s2.empty())
    {
        int t=s2.top();
        s2.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[i][t]!=-1)
            {
                outdegree[i]--;
                if(outdegree[i]==0)
                s2.push(i);
                if(dis[t]-g.adjMatrix[i][t]<dis[i])
                dis[i]=dis[t]-g.adjMatrix[i][t];
            }
        }
    }
    for(int i=0;i<g.edgNumber;i++)
    cout<<a[i].time<<endl;
}

问题 I: 图-边的最迟发生时间

题目描述

下图是一个有向无环图，节点内的数字表示该节点的序号，节点之间的连接线表示节点之间的连接方式，连接线上方的黑色数字表示该连接线的权重。
本题要求：求出有向无环图中每一个边的最迟发生时间（示例图中每一个边的最迟发生时间以边旁边的红色数字标出）


 

输入格式

第一行为2个正整数m和n，分别表示有向无环图的节点个数和边的数量。

接下来n行，代表n条边。分别是起点、终点、权重，以空格分隔。

（m<50,n<100）
 

输出格式

按行输出有向无环图中每一个边的最迟发生时间，按照输入样例中边的输入次序输出。
如输入样例中，边的输入次序为：
0-->1
0-->2
1-->3
2-->3
2-->4
3-->4
则输出样例中，按行分别输出上述边的最迟发生时间：2、0、5、3、7、7

输入样例 复制

5 6
0 1 3
0 2 3
1 3 2
2 3 4
2 4 4
3 4 4

输出样例 复制

2
0
5
3
7
7

数据范围与提示

#include<bits/stdc++.h>
using namespace std;

#define MAX_SIZE 100

struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE]={-1};
    int edgNumber;
};

struct edg{
    int start;
    int end;
    int time;
}a[MAX_SIZE];

void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]!=-1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}


void judge(const Graph G,const int inDegree[], queue<int>a)
{
    Graph g=G;
    int indegree[g.nodeNumber];
    for(int i=0;i<g.nodeNumber;i++)
    indegree[i]=inDegree[i];
    int i=0;
    while(a.size()!=0)
    {
        i=a.front();
        if(indegree[a.front()]!=0)
        {
            cout<<"NO"<<endl;
            return ;
        }
        a.pop();
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1&&i!=j)
            {
                g.adjMatrix[i][j]=0;
                indegree[j]--;
            }
        }
    }
    cout<<"YES"<<endl;
    return ;
}
int main()
{
    Graph g;
    cin>>g.nodeNumber>>g.edgNumber;
    int dis[MAX_SIZE]={0};
    int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        g.adjMatrix[i][j]=-1;
    }
    for(int i=0;i<g.edgNumber;i++)
    {
        int x,y,time;
        cin>>x>>y>>time;
        g.adjMatrix[x][y]=time;
        a[i].start=x;
        a[i].end=y;
        a[i].time=time;
    }
    CalculateDegree(g,inDegree,outDegree);
    stack<int>s;
    stack<int>s1;
    stack<int>s2;
    for(int i=0;i<g.nodeNumber;i++)
    {
        if(inDegree[i]==0)
        {
            s.push(i);
        }
        if(outDegree[i]==0)
        {
            s1.push(i);
            s2.push(i);
        }
    }
    while(!s.empty())
    {
        int t=s.top();
        s.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[t][i]!=-1)
            {
                inDegree[i]--;
                if(inDegree[i]==0)
                s.push(i);
                if(dis[t]+g.adjMatrix[t][i]>dis[i])
                dis[i]=dis[t]+g.adjMatrix[t][i];
            }
        }
    }
    // for(int i=0;i<g.nodeNumber;i++)
    // cout<<dis[i]<<endl;
    int outdegree[MAX_SIZE]={0};
    for(int i=0;i<g.nodeNumber;i++)
    outdegree[i]=outDegree[i];
    while(!s1.empty())
    {
        int t=s1.top();
        s1.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[i][t]!=-1)
            {
                outDegree[i]--;
                if(outDegree[i]==0)
                s1.push(i);
                dis[i]=dis[t]-g.adjMatrix[i][t];
            }
        }
    }
    while(!s2.empty())
    {
        int t=s2.top();
        s2.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[i][t]!=-1)
            {
                outdegree[i]--;
                if(outdegree[i]==0)
                s2.push(i);
                if(dis[t]-g.adjMatrix[i][t]<dis[i])
                dis[i]=dis[t]-g.adjMatrix[i][t];
            }
        }
    }
    for(int i=0;i<g.edgNumber;i++)
    {
        a[i].time=dis[a[i].end]-a[i].time;
    }
    for(int i=0;i<g.edgNumber;i++)
    cout<<a[i].time<<endl;
}

问题 J: 图-图的关键路径

题目描述

下图是一个有向无环图，节点内的数字表示该节点的序号，节点之间的连接线表示节点之间的连接方式，连接线上方的黑色数字表示该连接线的权重。
本题要求：求出有向无环图中的每一个关键路径及其发生时间（示例图中每一个边的最早/最迟发生时间以边旁边的黄色/红色数字标出）


 

输入格式

第一行为2个正整数m和n，分别表示有向无环图的节点个数和边的数量。
接下来n行，代表n条边。分别是起点、终点、权重，以空格分隔。
（m<50,n<100）

输出格式

按行输出有向无环图中的所有关键路径及其发生时间，按照输入样例中边的输入次序输出。
如输入样例中，边的输入次序为：
0-->1
0-->2
1-->3
2-->3
2-->4
3-->4
则输出样例中，按行上述次序依次输出其中的关键路径及其发生时间：
0-->2:0
2-->3:3
3-->4:7


注意：输入数据中边的顺序不一定符合“行优先”规则。

输入样例 复制

5 6
0 1 3
0 2 3
1 3 2
2 3 4
2 4 4
3 4 4

输出样例 复制

0-->2:0
2-->3:3
3-->4:7

数据范围与提示

#include<bits/stdc++.h>
using namespace std;

#define MAX_SIZE 100

struct Graph{
    int nodeNumber;
    int adjMatrix[MAX_SIZE][MAX_SIZE]={-1};
    int edgNumber;
};

struct edg{
    int start;
    int end;
    int maxtime;
    int mintime;
}a[MAX_SIZE];

void CalculateDegree(const Graph& g,int inDegree[],int outDegree[])
{
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]!=-1)
            {
                outDegree[i]++;
                inDegree[j]++;
            }
        }
    }
}


void judge(const Graph G,const int inDegree[], queue<int>a)
{
    Graph g=G;
    int indegree[g.nodeNumber];
    for(int i=0;i<g.nodeNumber;i++)
    indegree[i]=inDegree[i];
    int i=0;
    while(a.size()!=0)
    {
        i=a.front();
        if(indegree[a.front()]!=0)
        {
            cout<<"NO"<<endl;
            return ;
        }
        a.pop();
        for(int j=0;j<g.nodeNumber;j++)
        {
            if(g.adjMatrix[i][j]==1&&i!=j)
            {
                g.adjMatrix[i][j]=0;
                indegree[j]--;
            }
        }
    }
    cout<<"YES"<<endl;
    return ;
}
int main()
{
    Graph g;
    cin>>g.nodeNumber>>g.edgNumber;
    int dis[MAX_SIZE]={0};
    int inDegree[g.nodeNumber]={0},outDegree[g.nodeNumber]={0};
    for(int i=0;i<g.nodeNumber;i++)
    {
        for(int j=0;j<g.nodeNumber;j++)
        g.adjMatrix[i][j]=-1;
    }
    for(int i=0;i<g.edgNumber;i++)
    {
        int x,y,time;
        cin>>x>>y>>time;
        g.adjMatrix[x][y]=time;
        a[i].start=x;
        a[i].end=y;
        a[i].maxtime=time;
        a[i].mintime=time;
    }
    CalculateDegree(g,inDegree,outDegree);
    stack<int>s;
    stack<int>s1;
    stack<int>s2;
    for(int i=0;i<g.nodeNumber;i++)
    {
        if(inDegree[i]==0)
        {
            s.push(i);
        }
        if(outDegree[i]==0)
        {
            s1.push(i);
            s2.push(i);
        }
    }
    while(!s.empty())
    {
        int t=s.top();
        s.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[t][i]!=-1)
            {
                inDegree[i]--;
                if(inDegree[i]==0)
                s.push(i);
                if(dis[t]+g.adjMatrix[t][i]>dis[i])
                dis[i]=dis[t]+g.adjMatrix[t][i];
            }
        }
    }
    // for(int i=0;i<g.nodeNumber;i++)
    // cout<<dis[i]<<endl;
    for(int i=0;i<g.edgNumber;i++)
    a[i].mintime=dis[a[i].start];
    int outdegree[MAX_SIZE]={0};
    for(int i=0;i<g.nodeNumber;i++)
    outdegree[i]=outDegree[i];
    while(!s1.empty())
    {
        int t=s1.top();
        s1.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[i][t]!=-1)
            {
                outDegree[i]--;
                if(outDegree[i]==0)
                s1.push(i);
                dis[i]=dis[t]-g.adjMatrix[i][t];
            }
        }
    }
    while(!s2.empty())
    {
        int t=s2.top();
        s2.pop();
        for(int i=0;i<g.nodeNumber;i++)
        {
            if(g.adjMatrix[i][t]!=-1)
            {
                outdegree[i]--;
                if(outdegree[i]==0)
                s2.push(i);
                if(dis[t]-g.adjMatrix[i][t]<dis[i])
                dis[i]=dis[t]-g.adjMatrix[i][t];
            }
        }
    }
    for(int i=0;i<g.edgNumber;i++)
    {
        a[i].maxtime=dis[a[i].end]-a[i].maxtime;
    }
    for(int i=0;i<g.edgNumber;i++)
    {
        if(a[i].mintime==a[i].maxtime)
        {
            cout<<a[i].start<<"-->"<<a[i].end<<":"<<a[i].maxtime<<endl;
        }
    }
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

数据结构-图 的相关文章

  • java kotlinlang_Kotlin与Java互操作

    1 Kotlin 调用Javaimport java util fun demo source List val list ArrayList for item in source list add item for i in 0 sour

  • redis基本命令

    转 https www cnblogs com woshimrf p 5198361 html 目录 全局操作 1 redis是key value存储的 放在内存中 并在磁盘持久化的数据结构存储系统 2 redis提供原子自增操作incr

  • 学习算法之路（转载）

    第一阶段 练经典常用算法 下面的每个算法给我打上十到二十遍 同时自己精简代码 因为太常用 所以要练到写时不用想 10 15分钟内打完 甚至关掉显示器都可以把程序打 出来 1 最短路 Floyd Dijstra BellmanFord 2 最

随机推荐

  • Recent Advances in Deep Learning for Object Detection

    Recent Advances in Deep Learning for Object Detection Abstract 1 Introduction 2 Problem Settings 3 Detection Components

  • python修饰器原理_Python修饰器的函数式编程

    Python的修饰器的英文名叫Decorator 当你看到这个英文名的时候 你可能会把其跟Design Pattern里的Decorator搞混了 其实这是完全不同的两个东西 虽然好像 他们要干的事都很相似 都是想要对一个已有的模块做一些

  • 【RDMA】降低CPU除了RDMA (vbers）还是VMA ？

    前言 看介绍 像是mellonx针对其kernel bypass网卡 RDMA网卡 提供的一个lib库 该lib库对外提供socket api 使得用户的程序不需要修改就可以直接使用kernel bypass网卡 如RDMA网卡 我们都知道

  • FPGA内部结构及时序分析

    FPGA时序分析 FPGA内部基本结构 查找表概述 数据传输路径 时序分析模型 知识补充 注 本文内容来源于B站UP主小梅哥爱漂流的视屏内容 本人整理出来前三节课的视频笔记 对视频内容感兴趣的同学可以去看看小梅哥的视频 视频链接为https

  • String数组的创建

    string数组的定义有三种写法 String arr new String 10 创建一个长度为10的String 类型数组 String arr new String 10 String arr 张三 李四 前面两种写法是一样的 可以互

  • Window下编译FFmpeg(生成ffplay)

    第一步 百度或者官网下载mingw https ddd2 pc6 com xy1 mingw5 1 6 rar 解压后安装到c MinGW下 就是默认安装路径 注意安装时选择全部安装 避免有些东西没安装上 如下图 第二步 官网下载msys

  • opencv-python 银行卡卡号识别

    模板 银行卡 主要思路 用遮盖法 将无关紧要的上面和下面部分截掉 保留银行卡号差不多的位置 然后用opencv做图像处理 得到四个 连着数字的小框框 然后再在四个小框框里面提取出每一个单个的数字和模板里面的数字进行对比 难点是 如何使用op

  • 关于PCB走线及过孔的过流能力

    一 关于PCB走线的过流能力 PCB走线的过流能力都与哪些因素有关 目前考虑有走线线宽 铜箔厚度 走线长度 温升这些因素 下面我们逐个分析及整体分析 1 走线线宽 铜箔厚度以及走线长度对过流能力的影响 通过网上的收集及整理 统计出了下面的表

  • Android桌面悬浮窗进阶，QQ手机管家小火箭效果实现

    今天是2013年的最后一天了 这里首先提前祝大家新年快乐 同时 本篇文章也是我今年的最后一篇文章了 因此我想要让它尽量有点特殊性 比起平时的文章要多一些特色 记得在今年年初的时候 我写的第一篇文章是模仿360手机卫士的桌面悬浮窗效果 那么为

  • 在Vue组件中使用js（script标签）转换13位UTC格式的时间戳

    声明 代码来源AI 非本人原创 经测试实际可用

  • websocket-sdk 解决本地服务与浏览器之间的连接， 以及浏览器与服务器之间的数据传输

    最近由于项目业务需求 需要利用websocket完成本地服务与浏览器之间的数据传输 为了满足这个需求 这里自行封装了websocket sdk 这个工具 一 首先介绍下websocket sdk 它的作用 websocket sdk 已经处

  • 十条法则，让企业减少90%的勒索病毒攻击，勒索病毒解密，数据恢复

    建立完善的安全管理体系 企业应该建立完善的安全管理体系 包括安全策略 安全培训 应急响应等 确保每个员工都了解安全意识和操作规范 定期备份数据 企业需要建立定期备份机制 备份关键数据和系统 确保在发生勒索病毒攻击时 能够迅速恢复数据和系统

  • std::shared_ptr 与普通指针的转换

    shared ptr 是一个类 用模板支持很多类型 1 shared ptr到普通指针 shared ptr

  • Avalonia UI程序打包为deb安装包

    目录 相关依赖安装 打包前操作 进行打包 关于快捷方式的说明 相关依赖安装 全局安装打包工具 dotnet tool install global dotnet deb 向工程中安装相关打包依赖 将CMD命令行或PowerShell定位到工

  • jmeter常用插件介绍

    jmeter作为一个开源的接口性能测试工具 其本身的小巧和灵活性给了测试人员很大的帮助 但其本身作为一个开源工具 相比于一些商业工具 比如LoadRunner 在功能的全面性上就稍显不足 这篇博客 就介绍下jmeter的第三方插件jmete

  • C# 线程调用主线程中的控件

    由于项目的需要 最近几天一直在做串口和数据库 由于C 使用的时间不长 所以在编写代码和调试的过程中总是遇到意想不到的问题 比如在使用串口接收数据的时候 在接收数据事件中想把接收的数据放入一个textbox作显示 但是明明非常简单的代码 在编

  • 7-5 两个有序链表序列的交集 (20分) 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−

    7 5 两个有序链表序列的交集 20分 已知两个非降序链表序列S1与S2 设计函数构造出S1与S2的交集新链表S3 输入格式 输入分两行 分别在每行给出由若干个正整数构成的非降序序列 用 1表示序列的结尾 1不属于这个序列 数字用空格间隔

  • Intellij IDE 安装Golang插件出现GO SDK报错

    2019独角兽企业重金招聘Python工程师标准 gt gt gt 很多Java同学都是使用IDEA的 当然也可以直接使用 Gogland至少现在还是免费 谁也不知道什么时候又要收费了 所以我们选择了IDEA使用插件方式支持Golang的开

  • 规则引擎Drools使用 第十五篇 Spring Boot整合Drools

    在实际开发中 主要使用的还是以Spring Boot为主 所有下面介绍下Spring Boot整合Drools Spring Boot整合Drools 引入依赖

  • 数据结构-图

    目录 问题 A 邻接矩阵存储的图 节点的出度和入度计算 附加代码模式 问题 B 算法7 12 有向无环图的拓扑排序 问题 C 有向图是否存在环 问题 D 是否为有效的拓扑序列 问题 E 案例6 2 6 最短工期 问题 F 图 节点的最早发生

热门标签