图的几种存储方式

hdzgx 2019-11-19

展开全文

图的几种存储结构：

1、邻接矩阵

2、邻接表

3、链式前向星

4、C++中vector的邻接表实现（补充）

（一）邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵。

邻接矩阵的好处：

（1）直观、简单、好理解

（2）方便检查任意一对定点间是否存在边

（3）方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

（4）方便计算任一顶点的度

对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。

对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。

邻接矩阵的局限性：时间复杂度O(n^2），空间复杂度O(n^2)

（1）浪费空间。对于稠密图还是很合算的。

但是对于稀疏图（点很多而边很少）有大量无效元素。

（2）浪费时间。要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。

bb这么多，我们直接来以OJ此专题第一题为例

这题二维数组map不能用int，会爆内存，bool可以自己百度，简而言之就是用于逻辑判断，只有true和false两种情况。

bool类型在存储二值变量，或者说只有真假时，更具优势，因为只有0和1即false和true，省空间

（int型的0和1都是4字节，bool都是1字节）

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
bool map[5001][5001];
int main()
{
    int n,m;
    int u,v;
    int q;
    while(~scanf("%d %d",&n,&m))
    {
        memset(map,false,sizeof(map));
        while(m--)
        {
            scanf("%d %d",&u,&v);
            map[u][v]=true;
        }
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d %d",&u,&v);
            if(map[u][v])
            {
                printf("Yes\n");
            }else
            {
                printf("No\n");
            }
        }
    }
    return 0;
}

（二）邻接表

图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。

在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。

邻接表的特点如下：

（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。

（2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。

（3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。

（4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
    int data;
    struct node *next;
};
int main()
{
    int n, u, j, i, v;
    struct node *p, *a[5050];
    while(~scanf("%d", &n))
    {
        for(i = 0; i < n; i++)
            a[i] = NULL;
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < n; j++)
            {
                scanf("%d", &u);                       //审清题意
                if(u == 1)
                {
                    if(a[i] == NULL)
                    {
                        p = (struct node *)malloc(sizeof(struct node));
                        p -> data = j;
                        p -> next = NULL;
                        a[i] = p;
                    }
                    else
                    {
                        p = (struct node *)malloc(sizeof(struct node));
                        p -> next = a[i] -> next;
                        p -> data = j;
                        a[i] -> next = p;
                    }
                }
            }
        }
        int q;
        scanf("%d", &q);
        while(q--)
        {
            scanf("%d%d", &u, &v);
            p = a[u];
            int flag = 0;
            while(p)
            {
                if(p -> data == v)
                {
                    flag = 1;
                    break;
                }
                p = p -> next;
            }
            if(flag)
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

（三）链式前向星

https://blog.csdn.net/Binary_Heap/article/details/78209086

1. 结构

这里用两个东西：

1 结构体数组edge存边，edge[i]表示第i条边,

2 head[i]存以i为起点的第一条边(在edge中的下标)


struct edge{
	int to;     //这条边的终点 
	int w;      //权值 
        int next;   //下一条边的存储下标(默认0) 
}e[500010];

2.增边

若以点u为起点的边新增了一条，在edge中的下标为cnt.

那么edge[++cnt].next=head[u];然后head[u]=cnt.

即每次新加的边作为第一条边，最后倒序遍历


void add(int u, int v, int w) 
{   
        e[cnt].to = v;
	e[cnt].w = w;
        e[cnt].next = head[u];//cnt为边的计数，从1开始计 
	head[u] = cnt++;    //第一条边为当前边 
}

3. 遍历

遍历以st为起点的边

for(int i=head[st]; i!=0; i=edge[i].next)

i 开始为第一条边，每次指向下一条(以0为结束标志) （若下标从0开始，next应初始化-1）

链式前向星主要是用来优化的，可以用来优化BFS，SPFA算法等等。在做最短路的时候一直T就是因为没有用链式前向星存边导致的超时，所以这个坑我先和你们说下。

（四）vector的邻接表（补充）

vector是C++STL里面的一个东西，简单的来说就是一个可变长的数组，你可以通过往它里面压入数据来使它变长，

想深入了解的可以自己百度一波，还是以这道题为例：

#include<iostream>
#include<cstdio>
#include<vector>//注意这个头文件不能丢，要么你就去用万能头
using namespace std;
#define N 500001
vector<int>MAP[N];//可以理解为二维的，每个MAP可以包含若干项，这些项是以当前编号点为起点
int main()
{
    int n,m,u,v,i;
    while(~scanf("%d %d",&n,&m))
    {
        while(m--)
        {
            scanf("%d %d",&u,&v);
            MAP[u].push_back(v);//扩充
        }
        int q;
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d %d",&u,&v);
            int len=MAP[u].size();
            int flag=0;
            for(i=0;i<len;i++)
            {
                if(MAP[u][i]==v)
                {
                    flag=1;
                }
            }
            if(flag)
            {
                cout<<"Yes"<<endl;
            }else
            {
                cout<<"No"<<endl;
            }
        }
        for(int i=0; i<N; i++)
        {
            MAP[i].clear();
        }
    }
    return 0;
}