• 备战蓝桥杯---图论基础理论


    图的存储:

    1.邻接矩阵:

    我们用map[i][j]表示i--->j的边权

    2.用vector数组(在搜索专题的游戏一题中应用过)

    3.用邻接表:

    下面是用链表实现的基本功能的代码:

    1. #include
    2. using namespace std;
    3. struct node{
    4. int dian,zhi;
    5. struct node* next;
    6. };
    7. void insert(int x,int y,int z){
    8. node *p=new node;
    9. p->dian=y;
    10. p->zhi=z;
    11. p->next=head[x];
    12. head[x]=p;
    13. }

    4.用伪邻接表(链式前向星)(注意第一个next=-1,开始直接memset head=-1即可)

    对于(1,3,30,-1)表示1的点指向3,边权为30,下一条边.

    我们把这个存在edge[1]里,并令head[1]=1;

    (3,6,10,-1),我们存在edge[2]里,并令head[3]=2;

    (1,2,10,head[1]),我们存在edge【3】里,并让head[1]=3;

    下面是实现的代码:

    1. #include
    2. using namespace std;
    3. struct node{
    4. int dian,zhi;
    5. int next;
    6. };
    7. void insert(int x,int y,int z){
    8. edge[++m].dian=y;
    9. edge[m].zhi=z;
    10. edge[m].next=head[x];
    11. head[x]=m;
    12. }

    欧拉图(前提是联通)

    如果图的一个路径包括每个边恰好一次,则为欧拉路径。

    欧拉路径+回路=欧拉回路。

    具有欧拉回路的图为欧拉图,具有欧拉路径但无欧拉回路的图为半欧拉图

    那么如何判断是否为欧拉图呢?

    对于无向图,等价于该图所有顶点的度数为偶数(一进一出)+联通。

    对于有向图,等价于该图所有顶点的入度==出度+联通。

    拓扑排序

    即按照一定的规则安排活动的先后次序(可能有多解)。

    现在给一张图,a--》b表示要完成b必须先完成a,那我们如何排序呢?

    1.先找没有前驱的点作为开始。

    2.把它连着的边给删除,产生更多没有前驱的点作为下一步,入度-1。

    3.删不动则无法完成

    具体实现中,我们不能总是去跑入度为0的点。

    于是,我们用一个队列。在删后发现入度为0的点就放入队列中即可。

    下面是实现的代码:

    1. #include
    2. using namespace std;
    3. int n,m,cnt;
    4. struct node{
    5. int dian;
    6. int next;
    7. }edge[1000000];
    8. int head[1010],inc[1010];
    9. queue<int> q;
    10. void insert(int x,int y){
    11. edge[++cnt].dian=y;
    12. edge[cnt].next=head[x];
    13. head[x]=cnt;
    14. }
    15. void tuopu(){
    16. for(int i=1;i<=n;i++){
    17. if(inc[i]==0) q.push(i);
    18. }
    19. int tot=0;
    20. while(!q.empty()){
    21. int x=q.front();
    22. q.pop();
    23. cout<
    24. tot++;
    25. for(int i=head[x];i!=-1;i=edge[i].next){
    26. inc[edge[i].dian]--;
    27. if(inc[edge[i].dian]==0){
    28. q.push(edge[i].dian);
    29. }
    30. }
    31. }
    32. if(tot!=n) cout<<-1;
    33. }
    34. int main(){
    35. cin>>n>>m;
    36. memset(head,-1,sizeof(head));
    37. for(int i=1;i<=m;i++){
    38. int x,y;
    39. cin>>x>>y;
    40. insert(x,y);
    41. inc[y]++;
    42. }
    43. tuopu();
    44. }

    拓扑排序的应用:

    1.判断一个有向图是否有环,无环的图所有点都可以拓扑排序。

    2.AOE网:

    对于第一个,我们只用在拓扑排序上维护时间的max即可。

    对于第二个,我们可以计算一下每一个活动的最早开始时间与最晚开始时间,因此我们相当于求最早开始时间等于最晚开始时间的点。

    那么,我们如何求最晚开始时间呢?

    我们只要从结尾反方向跑一回即可。

    下面是AC代码:

    1. #include
    2. using namespace std;
    3. int n,m,cnt;
    4. struct node{
    5. int dian;
    6. int next;
    7. int zhi;
    8. }edge[1000000];
    9. int head[1010],inc[1010],shijian[1010];
    10. queue<int> q;
    11. void insert(int x,int y,int z){
    12. edge[++cnt].dian=y;
    13. edge[cnt].next=head[x];
    14. edge[cnt].zhi=z;
    15. head[x]=cnt;
    16. }
    17. void tuopu(){
    18. for(int i=1;i<=n;i++){
    19. if(inc[i]==0){
    20. q.push(i);
    21. shijian[i]=0;
    22. }
    23. }
    24. while(!q.empty()){
    25. int x=q.front();
    26. q.pop();
    27. for(int i=head[x];i!=-1;i=edge[i].next){
    28. inc[edge[i].dian]--;
    29. shijian[edge[i].dian]=max(shijian[edge[i].dian],shijian[x]+edge[i].zhi);
    30. if(inc[edge[i].dian]==0){
    31. q.push(edge[i].dian);
    32. }
    33. }
    34. }
    35. }
    36. int main(){
    37. cin>>n>>m;
    38. memset(head,-1,sizeof(head));
    39. for(int i=1;i<=m;i++){
    40. int x,y,z;
    41. cin>>x>>y>>z;
    42. insert(x,y,z);
    43. inc[y]++;
    44. }
    45. tuopu();
    46. cout<
    47. }

  • 相关阅读:
    图像与点云三维重建算法
    9.复杂的例子:模块的使用和自定义模块
    外部中断1电下降沿平触发
    基于Matlab实现自动泊车(垂直泊车)
    前端调用DRI后端API出现跨域资源共享(CORS)问题解决办法
    DevSecOps 安全即代码基础指南
    【算法挨揍日记】day04——15. 三数之和、18. 四数之和
    mosquitto部署mqtt broker 并测试订阅与发布
    应用程序接口(API)安全的入门指南
    leetcode 977有序数组的平方(附容器未初始化的问题)
  • 原文地址:https://blog.csdn.net/cocoack/article/details/136108729