图的存储——邻接表

1、邻接表与邻接矩阵

1.1 图的存储方式

一般分为邻接表和邻接矩阵
邻接矩阵：就是用横纵坐标来表示不同结点的编号，矩阵中的值(0,1)表示两个结点间是否相连。这样空间复杂度就需要O(N²)，只适用于稀疏图。
邻接表：这是算法中常用的存储图的方式。它为每一个结点创建一个链表，每一个链表存储该结点可以到达的所有结点。

1.2 邻接表的创建

//创建邻接表需要的数组
int e[N],h[N],ne[N],idx=0;  //idx仅表示数组的索引，e数组上存储的才是真正的值。
//h数组指每一个结点能够直接到达的结点。ne数组表示指向的下一个结点。
void add(int x ,int y){  //x表示源结点，y表示目的结点
  e[idx]=y;        //当前的idx还没有被使用过，所以指新的结点，该表达式用来记录新结点的值。
  ne[idx]=h[x];    //插入新结点
  h[x]=idx;        //将新结点作为表头
  idx++;          
}

int main(){
  //。。。。
  memset(h,-1,sizeof(h));    //-1作为链表的结束标志
}

2、用邻接表实现树的遍历

2.1深度优先遍历

例题：数的重心
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式
第一行包含整数n，表示树的结点数。
接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。

输出格式
输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。

数据范围
1≤n≤105

源代码

#include <iostream>
#include <cstring>
using namespace std;

int e[200010],h[100010],ne[200010],idx=0;
int ans=100000;
int n;
bool vist[100010];

int add(int x,int y){
    e[idx]=y,ne[idx]=h[x];h[x]=idx++;
}

int dfs(int x){
    vist[x]=true;
    int sum=1,res=0;
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!vist[j]){
            int temp=dfs(j);
            res=max(res,temp);
            sum+=temp;
        }
    }
    res=max(res,n-sum);
    ans=min(res,ans);
    return sum;
}

int main(){
    scanf("%d",&n);
    memset(h,-1,sizeof(h));
    for(int i=0;i<n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

2.2 广度优先遍历

题目
给定一个n个点m条边的有向图，图中可能存在重边和自环。
所有边的长度都是1，点的编号为1~n。
请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。

输入格式
第一行包含两个整数n和m。
接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式
输出一个整数，表示1号点到n号点的最短距离。

数据范围
1≤n,m≤105

源代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N=100010;

int e[100010],h[100010],ne[100010],idx=0;
int vist[N];
int n,m;

void add(int x,int y){
    e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}

int bfs(int x){
    queue<int> q;
    q.push(x);
    vist[x]=0;
    while(q.size()){
        int temp=q.front();
        q.pop();
        for(int i=h[temp];i!=-1;i=ne[i]){
            int j=e[i];
            if(vist[j]==-1){
                q.push(j);
                vist[j]=vist[temp]+1;
            }
            if(j==n)
                return vist[n];
        }
    }
    return -1;
}

int main(){
    memset(h,-1,sizeof(h));
    memset(vist,-1,sizeof(vist));
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    cout<<bfs(1)<<endl;
    return 0;
}