图的存储结构：邻接矩阵（邻接表）&链式前向星

【概念】疏松图&稠密图：

疏松图指，点连接的边不多的图，反之（点连接的边多）则为稠密图。

Tips：邻接矩阵与邻接表相比，疏松图多用邻接表，稠密图多用邻接矩阵。

邻接矩阵：

开一个二维数组graph[ ][ ]来记录图中点a与点b之间是否连通，初始化为0（或者-1之类的看情况）；如果图中有可忽略的重边（如只需重边中的最小边或最大边），则保存需要的那条边的边权，但如果有无法忽略的重边，就一定不要用邻接矩阵。
int graph[MAXN][MAXN];

void graphInit()

{

    memset(graph,0,sizeof(graph));

}

void graph_addEdge(int from,int to)

{

    graph[from][to]=1;  

    //如果是有边权的图，把权值赋给graph[from][to]

    //如果是无向无重边图，可以写成graph[from][to]=graph[to][from]=X（对称矩阵）;

}

邻接表：

依旧给每个节点编号，邻接表就是在结构体里声明一个to，由点a指向所连接的点b，就是vertex[a].to.push_back(b);记得要初始化。

而且，因为邻接表是用vector存边（push_back），所以不必担心重边丢失的情况；不过，使用邻接表存储图的话，对于两点之间是否连通的查询，相比邻接矩阵，邻接表处于劣势（因为在邻接表里必须遍历整个当前点的to才能判断是否与另一点连通）。
//用vector实现

struct node

{

    vector<int> to;

    //如果要挂边权，就在结构体里增加 int val;即可

}vertex[MAXN];

void graph_init(int n)

{

    for(int i=1;i<=n;i++)

        vertex[i].to.clear();

}

void graph_addEdge(int from,int to)

{

    vertex[from].to.push_back(to);

    //如果是无向边，则写成以下两步：

    //vertex[from].to.push_back(to);

    //vertex[to].to.push_back(from);

}

链式前向星：

本质上是图上所有边以某种特殊方式组成的链表。

通过加边方法，可以知道，如何查询一个点连出的边的方法：

要查询一个点的连出边，我们要先查head，知道这个点最近添加的那条边在哪里（查询结果在这里是j），然后比这条边早一些添加的就是next[j]，再早一点的就是next[next[j]]，更早一点的是next[next[next[j]]]，再早一点的是……，就这样我们一直往时间添加时间更早的边查，直到查到空节点（用来标记链表结束）。

以下是链式前向星的模板，含加边操作、遍历操作的方法：

struct Graph

{

    int head[MAXN];  //每一个节点在容器（数组）中所对应的第一条边的位置

    int next[MAXN];  //每一条边在容器中所对应的同一起点的下一条边的位置

    int to[MAXN];  //真正存储某一条边指向哪一点

    //若要知道每条边的起点，还需开一个数组from[MAXN];

    inline void addEdge(int _from,int _to)

    {

        //加边的方法

        static int q=1;

        //q是静态变量，每次加边，都首先用q指示当前存储边的容器末端（暗示已经为end）

        to[q]=_to;  //在to的末端写入新加边的信息

        next[q]=head[_from];

        //head[_from]表示起点_from最近添加的一条边的位置，然后让新加边的next指向该边的位置

        head[_from]=q++;

        //修改head，使得最近添加的边更新为新边，同时末端向后移动（q++;）以供下一次添加使用

    }

} graph;

void iteration()

{

    //遍历的方法

    int now;  //now 是当前所处的节点编号

    for (int j=idx.head[now]; j; j=idx.next[j])

    {}

    //operate node j，j是now所连接的节点编号

}

上面注释太多，下面上一个比较实用的模板(￣▽￣)" ：

struct edge

{

    int next,to;

}E[MAXN];

int head[MAXN],Ecou;  //Ecou:边下标

void add_edge(int u,int v)

{

    E[Ecou].to=v;

    E[Ecou].next=head[u];

    head[u]=Ecou++;

}

void init(int n)

{

    Ecou=0;

    //memset(head,-1,sizeof(head);

    for(int i=1;i<=n;i++)

        head[i]=-1;

}

巴特西

图的存储结构：邻接矩阵（邻接表）&链式前向星

最新文章

热门文章