树和图的存储和图的深搜与宽搜

图的存储

树是一种特殊的图，即无环连通图

有向图：a到b，无向图：a-b：建立a到b和b到a，是一种特殊的有向图

有向图的存储方式1：邻接矩阵：开一个二维数组，存储边的信息，用得少

有向图的存储方式2：邻接表：有n个点，在每个节点上开一个单链表，存储这个点可以走到的点

#include<stdio.h>
#include<string.h>

const int N=10010;
int h[N],e[N],ne[N],idx;

void add(int a,int b) //存储从a到b的一条边
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
	//当前的点存储为b，然后让idx指向原先表头指向的点，然后表头指向idx
}

int main()
{
	memset(h,-1,sizeof h);
	//将所有表头都置为-1
}

图的深度优先遍历

#include<stdio.h>
#include<string.h>

const int N=10010;
int h[N],e[N],ne[N],idx;
int n,m;
int st[N];   //用来判断该点是否已经搜索过了，搜索过就存1

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

void dfs(int u)
{
	st[u]=1;  //标记一下，该点已经被搜过了
	
	for(int i=h[u];i!=-1;i=ne[i]) 
	//从该点开始搜索该点下的链表，即搜索该点可到达的点
	{
		int j=e[i];  
		if(!st[j]) dfs(j);  
	//如果该点没有搜索到过，就继续深搜该点下的链表
	}
}

int main()
{
	memset(h,-1,sizeof h);
    
    dfs(1);
}

应用举例1：树的重心

问题分析：把1删掉最大连通块个数是4，把2删掉个数是6……最后输出最小的最大连通块

#include<stdio.h>
#include<string.h>

const int N=10010;
int h[N],e[N],ne[N],idx;
int n,m;
int st[N];   

int ans=N;

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

int dfs(int u)
{
	st[u]=1;  
	
    int sum=1,res=0;
	for(int i=h[u];i!=-1;i=ne[i])
	//从当前节点开始往下搜索遍历链表里的各个点
	{
		int j=e[i];
		//e[i]是当前这个点的序号   
		if(!st[j])
		{
			int s=dfs(j);    //s代表某节点下面其中一个分支的连通块数量
			res=max(res,s);  //这里的res保存该点下面所有分支里最大的连通块
			sum+=s;          //sum是为了最后计算n—sum，即算除了该节点下面以外的连通块
		} 
	}
	res=max(res,n-sum);      //这里的res保存删掉该点后的最大连通块
	
	ans=min(ans,res);        //答案
	
	return sum;
	//每一次调用这个dfs函数，返回的是sum，即该点分支下面的连通块总数
}

int main()
{
	scanf("%d",&n);
	getchar();
	memset(h,-1,sizeof h);
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		add(a,b),add(b,a);
    //对于无向图的建立，只需要在add(a,b)之后再来一个add(b,a)即可
	}
    
    dfs(1);
    printf("%d",ans);
    
    return 0;
}

图的宽度优先遍历

#include<stdio.h>
#include<string.h>

int h[500],e[500],ne[500],idx;
//h数组以点的编号为下标，e数组存储这点的编号
int d[500];
//记录当前点是否已经被宽搜过了
int q[500];
//队列里存储的就是我们要逐个遍历链表进行宽搜的点的序号

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

int bfs(int u)
{
	int hh=0,tt=0;
	q[0]=u;
	//q[0]=u,代表从u节点开始宽搜
	
    while(hh<=tt)
    {
    	int t=q[hh++];
    	//队头出队，准备对队头进行宽搜
    	
    	for(int i=h[t];i!=-1;i=ne[i])
    	//遍历队头下面的链表，即对队头所指向的所有点进行搜索
    	{
    		int j=e[i];
    	    //取到e[i]：队头所指向的一个点
    		if(d[j]==-1)
    		//如果e[i]该点没有被搜索过，那么就进入搜索
    		{
    			q[++tt]=j;
    			//将e[i]该点入队，之后还要对该点所指向的所有点进行宽搜
			}
		}
	}
}

int main()
{
	memset(d,-1,sizeof d);
	
	bfs(1);
}

应用举例1：图中点的层次：给定一个n个点m条边的有向图，所有边的长度都是1，点的编号为1~n，请你求出1号点到n号点的最短距离，如果从1号点不能走到n号点，则输出-1

#include<stdio.h>
#include<string.h>

int h[500],e[500],ne[500],idx;
int q[500];
int d[500];
int n,m;

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

int bfs()
{
	int hh=0,tt=0;
	q[0]=1;
	
	d[1]=0;
	
	while(hh<=tt)
	{
		int t=q[hh++];
		
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(d[j]==-1)
			{
				d[j]=d[t]+1;
				//本题的解题逻辑，计算出第n个点是第几层搜索到的，即最短路径
				q[++tt]=j;
			}
		}
	}
	
	return d[n];
}

int main()
{
	memset(d,-1,sizeof d);
	int a,b;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d %d",&a,&b);
		add(a,b);
	}
	
	printf("%d",bfs());
}

应用举例2：求有向图的拓扑序列：给定一个n个点m条边的有向图，请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1

（拓扑序列，如1指向2，2指向3，1指向3，则1 2 3就是一个拓扑序列，因为1在2,3前，2在3前，如果有环则不存在拓扑序列，因此拓扑序列也被叫做有向无环图）

解题思路：入度和出度的概念，入度：有多少条边指向自己，出度：有多少条边往外指出

所有入度为0的点，都可以直接入队，然后对这些已经入队的点进行宽搜，先入队其中入度为1的点，然后入度为2的点……最后队列中所存的顺序就是拓扑序列

#include<stdio.h>
#include<string.h>

const int N=500;
int n,m,a,b;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
//d数组存的是每个点的入度，q数组队列存储拓扑序列

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

int topsort()
{
	int hh=0,tt=-1;
	for(int i=0;i<n;i++)
	{
		if(!d[i]) q[++tt]=i;
	}
    //先把所有入度为0的点都存入队列中
	
	while(hh<=tt)
	{
		int t=q[hh++];
        //取出队头，准备对队头指向的点进行宽搜
	    
	    for(int i=h[t];i!=-1;i=ne[i])
        //在for循环里对队头下连的所有点进行宽搜
	    {
	    	int j=e[i];
	    	d[j]--;
            //删掉这条边，也就是按顺序存入入度为1，入度为2……的点
	    	if(d[j]==0) q[++tt]=j;
            //当删掉之后入度为0，将该点入队
		}
	}
	
	return tt-n+1; //返回值是用来判断是否存在拓扑序列的，如果队列个数不为n，则没有该序列
}

int main()
{
	scanf("%d %d",&n,&m);
	memset(h,-1,sizeof h);
	for(int i=0;i<m;i++)
	{
		scanf("%d %d",&a,&b);
		add(a,b);
		d[b]++;
	}
	
	if(!topsort())
	{
		for(int i=0;i<n;i++) printf("%d",q[i]);
		puts("");
	}
	else puts("-1");
	
	return 0;
}