月球美容计划之图的储存结构汇总

月球美容计划之图的储存结构汇总

大家好,又见面了,我是全栈君。

SJ图论非常流弊,为了省赛队里知识尽量广,我就直接把图continue,如今回想起来丫的全忘了,从头開始吧。

先写写图的存储,再写写最小生成树和最短路的几个经典算法,月球美容计划就能够结束了。0 0。拖了好久,还有非常多内容要写。- –

这次总结了邻接矩阵,邻接表。十字链表。邻接多重表,边集数组,这5种经常使用的图的储存结构,或许能当模板用吧。

 

 

邻接矩阵

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//邻接矩阵
int G[100][100];
int add1 (int i,int j,int w)
{
    G[i][j] = w;
	return 0;
}

int main()
{
    int i,n;
    
    //建图
	scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        add1 (a,b,w);
        //无向图加上
        add1 (b,a,w);
    }
    return 0;
}

邻接表

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//邻接表

struct dot
{
    int d;
    int w;
    struct dot *next;
};

struct hed
{
    int v;
    struct dot *next;
}head[100];

int add2(int i,int j,int w)
{
    struct dot * p;
    struct dot * t = new dot;

    t->d = j;
    t->w = w;
    t->next = NULL;

    if (head[i].next == NULL)
    {
        head[i].next = t;
        return 0;
    }

    p = head[i].next;

    while (p->next != NULL)
        p = p->next;

    p->next = t;

    return 0;
}

int main()
{
    int i,n;
	
	memset (head,0,sizeof (head));
    //建图
    scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        add2 (a,b,w);
        //无向图加上
        add2 (b,a,w);
    }
    return 0;
}

十字链表(有向图好用)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//十字链表

struct dot
{
    int d;
    int w;
    struct dot *next;
};

struct hed
{
    int v;
    struct dot *to;
    struct dot *next;
}head[100];

int add3(int i,int j,int w)
{
    struct dot * p;
    struct dot * t = new dot;

    t->d = j;
    t->w = w;
    t->next = NULL;

    //正邻接表构建
    if (head[i].next == NULL)
    {
        head[i].next = t;
    }else
    {
        p = head[i].next;

        while (p->next != NULL)
            p = p->next;

        p->next = t;
    }

    //逆邻接表打十字
    if (head[i].to == NULL)
    {
        head[i].to = t;
        return 0;
    }else
    {
        p = head[i].to;

        while (p->next != NULL)
            p = p->next;

        p->next = t;
    }

    return 0;
}

int main()
{
    int i,n;
	
	memset (head,0,sizeof (head));
    //建图
    scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        add3 (a,b,w);
    }
    return 0;
}

邻接多重表(无向图)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//邻接多重表(无向图)

struct dot
{
    int i,j;
    int w;
    struct dot *inext;
    struct dot *jnext;
};

struct hed
{
    int v;
    struct dot *next;
}head[100];

int add4(int i,int j,int w)
{
    struct dot *t = new dot;
    struct dot *p = NULL,*tp = NULL;

    t->i = i;
    t->j = j;
    t->w = w;
    t->inext = NULL;
    t->jnext = NULL;

    if (head[i].next == NULL)
    {
        head[i].next = t;
    }else
    {
        p = head[i].next;

        while (p != NULL)
        {
            tp = p;
            if (p->i == i)
                p = p->inext;
            else
                p = p->jnext;
        }

            if (tp->i == i)
                tp->inext = t;
            else
                tp->jnext = t;
    }

    if (head[j].next == NULL)
    {
        head[j].next = t;
    }else
    {
        p = head[j].next;

        while (p != NULL)
        {
            tp = p;
            if (p->i == j)
                p = p->inext;
            else
                p = p->jnext;
        }

        if (tp->i == j)
                tp->inext = t;
            else
                tp->jnext = t;
    }

    return 0;
}

int main()
{
    int i,n;

    memset (head,0,sizeof (head));
    //建图
    scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        add4 (a,b,w);
    }
    return 0;
}

 

边集数组

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//边集数组

struct e
{
    int i,j;
    int w;
    
}eg[100];

int cont;

int add5(int i,int j,int w)
{
    eg[cont].i = i;
    eg[cont].j = j;
    eg[cont].w = w;
    return 0;
}

int main()
{
    int i,n;
	
	memset (eg,0,sizeof (eg));
	cont = 0;
    //建图
    scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        //有向图无向图皆可
        add5 (a,b,w);
    }
    return 0;
}

边集数组之前向星

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//前向星
int head[100];

struct e
{
    int to;
    int fro;
    int w;
}eg[100];

int cont;
int add6 (int i,int j,int w)
{
    eg[cont].to = j;
    eg[cont].fro = head[i];
    eg[cont].w = w;
    head[i] = cont++;
	return 0;
}

int main()
{
    int i,n;

    memset (head,-1,sizeof (head));
    cont = 0;
    //建图
	scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        add6 (a,b,w);
        //无向图加上
        add6 (b,a,w);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115647.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号