图的存储和遍历

Eric0521 / 2024-02-25 / 原文

一.存储

树是特殊的图
无向图是特殊的有向图所以只需考虑有向图如何存储即可

1.邻接矩阵空间复杂度o(n^2)-用的不多

2.邻接表(每一个节点都开一个单链表-存这个点可以走到哪个点)
注：内部点顺序无关紧要

二.遍历

(1)深度优先遍历DFS

AcWing-846

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'

using namespace std;

const int N=1e5+10;

int h[N];//头节点
int e[N*2],ne[N*2],idx;//与单链表一样
bool st[N];//判重数组
int ans=N;//最大值
int n;

void add(int x,int y)//与单链表插入一样
{
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}

int dfs(int u)//深度遍历图
{
    st[u]=true;//已经遍历过了
    int res=0;//代表删除u节点的树点个数的最大值
    int sum=1;//指根子树的点数
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            int s=dfs(j);//当前子树的大小
            res=max(res,s);//取最大值
            sum+=s;//是以u节点的树的一部分
        }
    }
    res=max(res,n-sum);//节点上面也要算
    
    ans=min(res,ans);
    
    return sum;
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);//初始化-1表示空节点
    
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);add(b,a);
    }
    
    dfs(1);
    
    cout<<ans<<endl;
    
    return 0;
}

(2)宽度优先遍历BFS

AcWing-847

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N=1e5+10;
queue<int> q;//队列
int h[N],e[N*2],ne[N*2];
int idx;//当前用到的下标
int n,m;
int d[N];//标记数组

void add(int a,int b)//插入
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int bfs()
{
    q.push(1);//起始点入队
    memset(d,-1,sizeof d);//初始化标记数组 -1表示没有遍历过
    d[1]=0;//起始点遍历过了
    
    while(!q.empty())//BFS
    {
        auto t=q.front();//取出队头元素
        q.pop();//elimate
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1)
            {
                d[j]=d[t]+1;//更新标记数组
                q.push(j);
            }
        }
    }
    
    return d[n];
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    
    cout<<bfs()<<endl;
    
    return 0;
}