树和图的存储与遍历 思想+模板代码

树和图的存储与遍历 思想+模板代码 树和图的存储

树的本质是连通的无环图

图分为

有向图无向图

无向图是特殊的有向图
所以对树和图的存储，最本质的其实就是去存储有向图

有两种结构：

邻接矩阵
缺陷：
1.不能存储重边，只能保留两个点之间的一条边
2.空间复杂度为O（n2）,比较费存储空间，只适用于稠密图邻接表
为每个结点开一条表示其所有邻接点的单链表，链表上每个结点就是其邻接点
链表内部的邻接点次序无关紧要，为方便起见，插入邻接点统一在表头插入
一般用数组模拟，数组模拟的效率>vector

int h[N],e[N],ne[N],idx;
//h[N] 表示每个结点（邻接表头）的数组，存放邻接表的第一个结点编号（该点的第一个邻边的编号）
//e[N] 表示邻接表的链表中结点的值
//ne[N] 表示结点的下一个结点的编号
//idx   表示开辟新空间的分配符
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

不断使用add函数把边往邻接表里加，这样便可以把图存储起来。

---

图的遍历 广度优先遍历

直接套广度优先遍历的模板即可

//题目背景：AcWing 847.图中点的层次
int h[N],e[N],ne[N],idx;
int d[N];
bool st[N];
int bfs()
{
    queue q;
    q.push(1);
    st[1]=true;
    while(!q.empty())
    {
        int t=q.front();
        if(t==n)
            return d[n];
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            if(!st[e[i]])
            {
                d[e[i]]=d[t]+1;
                q.push(e[i]);
                st[e[i]]=true;
            }
        }
    }
    return -1;
}

---

拓扑排序

不是所有图都可以进行拓扑排序
只有有向无环图才可以进行拓扑排序
有向无环图也称为拓扑图
一个有向无环图，一定至少存在一个入度为0的点。
拓扑排序不是唯一的。

//题目背景：AcWing 848.有向图的拓扑排序
#include
#include
#include
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],hh=0,tt=-1;    //队列
int r[N];  //入度表
bool st[N];  //记录点是否被访问过
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool bfs()
{
    int i;
    for(i=1;i<=n;i++)      //刚开始遍历一遍所有点，把天然入度为0的点都加进去
        if(r[i]==0)        //不然只加一个，另外其他一开始天然就入度为0的点后面不会被访问到
        {
            q[++tt]=i;
            st[i]=true;
        }
    while(hh<=tt)
    {
        int t=q[hh];
        hh++;
        for(i=h[t];i!=-1;i=ne[i])
        {
            if(!st[e[i]])   //如果没有被访问过
            {
                r[e[i]]--;   //入度--
                if(r[e[i]]==0)   //如果刚好入度为0了
                {
                    q[++tt]=e[i];   //入队
                    st[e[i]]=true;  //记录下已经被访问过了
                }
            }
        }
    }                           //判断是否拓扑排序成功的方法：
    
    if(tt==n-1)                 //2.因为数组模拟队列，队尾tt的位置可以反映从头到尾一共有多少元素进过队
        return true;
    else
        return false;
}
int main()
{
    memset(h,-1,sizeof(h));
    int a,b;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        r[b]++;  //入度+1 维护一个入度表
    }
    if(bfs())      //因为是用数组模拟的队列，所以hh++出队操作本质上并没有删除点，而是后移了，这种方法给了我们输出拓扑排序序列的可能
        for(int i=0;i 
 
深度优先遍历 
// 需要标记数组st[N],  遍历节点的每个相邻的便
void dfs(int u) {
    st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            dfs(j);
        }
    }
}
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://www.outofmemory.cn/zaji/5715226.html