知识分享 – 【图论-存图】邻接矩阵 邻接表 链式前向星

这篇文章主要来讲一下邻接矩阵 邻接表 链式前向星(本篇需要具备一定图的基础知识,至少邻接矩阵之前要会,这里主要讲解邻接表和链式前向星)

我不大喜欢说废话,所以直接上图

邻接矩阵:用二维数组存储点与点之间的关系,也就是这样

但是仔细想想,有很多不必要的空间浪费,比如说(2,5)这个空间就没有必要,那我们可以像一个办法来去掉这些多余的空间,邻接矩阵我们用的是二维数组,那这里我们想一下,根据每一个点到另一个点不同,如果要去掉那些无用点的话,每一个起点所对终点的数量不同,所以我们要用到动态数组。

而动态数组,在C语言里面我们用链表,如果是C++的话,用vector。最后就成这样

所以说我们这里每一层都是一个动态数组,然后动态数组里面存的是终点的标号,比如说1连了2和3,那就把2 3放到1的后面(注意,插入顺序不同,那遍历时的顺序也不同,如果是用的vector那遍历的顺序就是插入的顺序,如果是用的链表,那遍历的顺序就会倒过来,因为链表的插入通常使用头插法,当然,你使用尾插法也可以)

下面直接上代码

先来一个链表的

zhetypedef struct edgeNode{
    int index;//当前结点所对应的元素在头节点数组中的下标
    int value;
    edgeNode *next;//下一个兄弟
}edgeNode;
typedef struct vertexnode{
    int data;
    edgeNode *firstedge=NULL;
}vertexnode;
vector<vertexnode> V;

下面是用的vector

typedef struct edge{
    Bindex index;
    Value value;
}edge;
typedef struct vertex{
    int index;//可有可无,根据你设定的下标来,如果你把1存在V[0]的话就需要
    vector<edge>edge;
}vertex;
vector<vertex> V;

其中value代表的是权值,这个地方还可以简化(注意下标),直接用一个结构体,然后套个二维的vector就行了

vector<vector<edge> > V;

所以仔细一看,这不就是一个二维数组吗?没错,所以在一定程度上,我认为邻接表其实就是邻接矩阵把那些没必要的点给扣掉。

这里我就直接放深搜和广搜的源代码了

vector<bool>book;
void bfs(vector<vertex>V){
    queue<vertex>Que;
    Que.push(V[1]);
    book[Que.front().index]= true;
    while(!Que.empty()){
        //将当前标号的所有连接点入队
        int i=0;
        cout<<Que.front().index<<" ";
        while(i<Que.front().edge.size()){
            if (book[Que.front().edge[i].index]!=true) {
                Que.push(V[Que.front().edge[i].index]);
                book[Que.front().edge[i].index]=true;
            }
            i++;
        }
        Que.pop();
    }
}
void dfs(vector<vertex>V,int i){
    if (book[i]==true)return;
    cout<<V[i].index<<" ";
    book[V[i].index]=true;
    for (int j = 0; j < V[i].edge.size(); ++j) {
        if(book[V[i].edge[j].index]!=true){
            dfs(V,V[i].edge[j].index);
//            book[V[i].edge[j].index]=true;
        }
    }
}

边集数组

在讲链式前向星之前提一嘴这个,其实这个就是BellMan-Ford算法的存图方法,废话不说,直接上代码,顺便把BellMan-Ford也丢上来

#include <bits/stdc++.h>
using namespace std;
typedef struct edge{
    int u,v,w;
}edge;
int main(){
    int n,m;
    cin>>n>>m;
    edge e[m];
//边集数组存储方式
    for (int i = 0; i < m; ++i) {
        int u,v,w;
        cin>>u>>v>>w;
        e[i]={u,v,w};
    }
    int dis[n+1];
    fill(dis,dis+n+1,0x3f3f3f);
    dis[1]=0;
    for (int i = 1; i <= n-1; ++i) {
        for (int j = 0; j < m; ++j) {
            if(dis[e[j].v]>dis[e[j].u]+e[j].w){
                dis[e[j].v]=dis[e[j].u]+e[j].w;
            }
        }
    }
    //检查负权回路
    int flag=0;
    for (int j = 0; j < m; ++j)
        if (dis[e[j].v] > dis[e[j].u] + e[j].w) {
            flag = 1;
            break;
        }
    cout<<(dis[n]==0x3f3f3f?-1:dis[n]);
}

链式前向星

这里先放下代码,大家可以踩一下怎么搞

typedef struct edge{
    int to;//终点
    int w;//权重
    int next;//兄弟结点在e数组中的下标
}edge;
//这里使用动态数组,使用普通数组也是可以的
vector<edge>e;
vector<int>head;//建议从1开始存,其值是指向一个e的下标

其实链式前向星,我个人觉得,可以简单理解为邻接表的降为

细看操作

首先来看边的结构

假如,我们有一个无向图

假如说,我们输入一条边: 1 2 5

那这个时候,我们把e[0]的to设置为2,w设置为5。(在此之前head数组要初始化,建议值赋值为-1)

然后因为2 5我们存在e[0]里面的,又表示的是1->2这一条边,我们把它连接在head[1]的后面,本来head[1]=-1的,我们把-1赋值给e[0]的next;后面同理,如果又要插入一条边为1 4 3的话,那e[1]的话,存储的值就是:4 3 0(0是head[1]插入当前结点之前的值),这样我们就有把它像邻接表一样给连起来了。

当然如果你要弄成无向图的话,再反过来添加就可以了

如果是无向图的话,插入第一个点是这样的

然后,我们把1 4 3插入(这个图因为是无向图,所以这个地方,e的下标是2)

所以说这个插入顺序和链接顺序有点像栈,我们head存储的一定是最后一个插入的边的下标,下面我直接上代码

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

typedef struct edge{
    int to;
    int w;
    int next;
}edge;
//这里使用动态数组,使用普通数组也是可以的
vector<edge>e;
vector<int>head;
vector<bool>book;
void bfs(vector<int> head){
    queue<int>Q;
    Q.push(1);
    book[1]=true;
    int j=e[head[1]].to;
    while(!Q.empty()){
        int next=head[Q.front()];
        while(next!=-1){
            //这里做个处理,如果遇到走过了的,就跳过
            if(book[e[next].to]==true){
                next=e[next].next;
                continue;
            }
            j=e[next].to;
            Q.push(j);
            book[j]=true;
            next=e[next].next;
        }
        cout<<Q.front();
        Q.pop();
    }

}
int main(){
    int n,m;
    cin>>n>>m;
    for (int i = 0; i <= n; ++i) {
        head.push_back(-1);
        book.push_back(false);
    }
//    int cnt = 0;用普通数组的做法
    for (int i = 0; i < m; ++i) {
        int u,v,w;
        cin>>u>>v>>w;
        e.push_back({v,w,head[u]});
        head[u]=e.size()-1;
        e.push_back({u,w,head[v]});
        head[v]=e.size()-1;
//        e[cnt]={v,w,head[u]};用普通数组的做法
//        head[u]=cnt++;用普通数组的做法
//        e[cnt]={u,w,head[v]};用普通数组的做法
//        head[v]=cnt++;用普通数组的做法
    }
    bfs(head);
    return 0;
}

本文部分图片采集于CSDN博客链式前向星——最完美图解_rainchxy的博客-CSDN博客_链式前向星

正文完