邻接矩阵以及邻接表(彻底搞懂到自己会用)

邻接矩阵：

f[i][j]//表示i到j有没有边,以及是否关联，存入权值

关联矩阵：
n行e列

f[i][j]//若有边，存入1,否则存入0

实例：

→ 当边数很稀疏时（m<<n^2）用相邻矩阵存图太浪费空间（有大量都是0）
→ 如何为更高效地存储图结构？把有值的元素放到一侧 其他的不存了

这就是邻接表的诞生！！！！！

→ 每个顶点创建一个链表 链表的每一项表示该顶点的一条出边/入边 （链表长度=该顶点的出度） 最简单的实现是vector
→ 如上存储结构称为邻接表 空间性能：O(n+m)（基本无浪费） 支持重边

好了，接下来进入正题

以前，我遇见要用到邻接表的图论题，我只有被吊打的份。（根本不会）。。那么，邻接表到底是什么？？ 我们用一个struct结构体，内含(next , to),我们再用一个数组head[N].

head[1]=5;//1号节点对应最后一条边
struct edge{int nxt,to;} e[N]; e[i].nxt[5]=10;//nxt表示5的下一条边
to[5]=4;//to表示边能到的节点
int cnt;//cnt用来遍历每条边

(原谅我没把结构体没打全)
储存方式：

struct edge{
    int nxt,to;
} e[M];
int head[N],cnt,vis[N],d[N],t,fa[N];
void add(int x,int y){
    e[++cnt]=(edge){head[x],y};//=  ++cnt; e[cnt].next=head[x],e[cnt].to=y;
    head[x]=cnt;
}

读入以及调用方式：

int n,m;
    cin>>n>>m;
    memset(head,0,sizeof head); cnt=0;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }

绝对正宗！！！

其实，也没那么难，对吧？？

邻接矩阵以及邻接表

原文：https://www.cnblogs.com/tushukai/p/11253566.html