前言
图的基础与遍历
图的存储方式
邻接表
List<int []>list[N];
list[x]存储x的所有出点的信息。
list[i][j]={first,second}其中first表示从i出发的某个出点的编号，second表示边权。
list[1]={{2,0},{3,0}} 1这个点有2和3连个出边
邻接矩阵
d[i][j]表示从i到j的边的距离（一般情况下为最短距离）
d[1,2]=0（表示从1到2有一条边）
d[4,3]=-1(不存在对应的边)
DFS（深度优先搜索）
一条道走到黑，走过的路不再走（一种情况尝试到底）
递归
搜索的要点：
1：选定初始状态
2：遍历当前初始状态或状态所产生的合法状态，产生的新状态进入递归
3：检查目标状态是否是合法状态，是则返回，否则继续遍历，重复2-3步骤
常用模板
public static void dfs(){
if(当前状态==目标状态){
return;
}
for(寻找新状态){
if(状态合法){
dfs(新状态);
}
}
}顺序不确定，只要走完就行
回溯
从一条路往前走，能进则进，不能进则退
全排列
回溯的模板与dfs的常用模板相同
public static void dfs(){
if(当前状态==目标状态){
return;
}
for(寻找新状态){
if(状态合法){
//标记当前状态已访问
dfs(新状态);
//撤销标记
}
}
}图论中的模板
boolean<N> v;//v[i]=true说明i点已经走过 标记数组
void dfs(int x){
v[x]=true;//进来对x，打上标记
for(int y:list[x]){
if(v[y]) continue;//已经打过标记的话，跳过
else dfs(y);//否则进入y这个结点
}
}BFS（宽度优先搜索）
一层一层往外走，每个点只走一次
通常用于求边权相等情况下的最短距离
BFS一般用队列来实现
boolean <N> vis;//标记数组,v[i]=true表示点已经走过了
queue<int> q;//q表示带拓展的队列
while(q.size>0){//只要队列不为空就一直走
int x=q.pop();//弹出来
if(v[x]) continue;
v[x]=true;//没有走过这个标记
for(int y:list[x]){
q.push(y);
}//遍历这个点的所有出点，压入队列中
}编号3891帮派弟位
问题描述
小明在游戏中参加了一个帮派，这一天他突然想知道自己在帮派中是什么地位，但是帮派的查询系统突然坏了，目前只能知道每个人的附属关系，请问你能帮帮他重建关系网并找出他的地位吗？
给定一个正整数 n ，代表该帮派的总人数，并且小明的序号是 m ，给出这 n 个人中每个人的附属关系，确保给出的关系网为一棵树。帮派地位的定义是按照自己手下有多少帮众决定的，注意手下的手下也算是自己的手下。如果手下的帮众相同则按序号较小的在前面。你能帮助小明找到自己的帮派地位吗？
输入格式
第一行，两个正整数 n (1≤n≤105) 和 m （1≤m≤n) ，代表该帮派的总人数以及小明的序号。
接下来 n−1 行，每行两个正整数，格式如下：
l r(1≤l,r≤n) ， 代表序号为 l 的人附属于序号为 r 的人。- 输出格式
一行，包含 11 个正整数，输出按手下人数多少排序后小明的排名。 - 样例输入
6 4 2 1 3 1 4 2 5 2 6 5样例输出
5
代码
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static List<Integer> []list;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int m=scan.nextInt();
list = new List[n+1];
for(int i=0;i<n+1;i++) {
list[i]=new ArrayList<>();
}//存储点
int []a=new int [n+1];//存储入度
for(int i=0;i<n-1;i++) {
int l=scan.nextInt();
int r=scan.nextInt();
list[r].add(l);
a[l]++;
}
int root=0;
for(int i=1;i<=n;i++) {//总人数是1-n
if(a[i]==0) {
root=i;
break;
}
}//找到根节点了
int []dp=new int[n+1];//每个结点值的大小
dfs(root,dp);
int ans=1;
for(int i=1;i<m;i++) {
if(dp[i]>=dp[m]) {
ans++;
}//前半部分
}
for(int i=m+1;i<n;i++) {
if(dp[i]>dp[m]) {
ans++;
}
}
System.out.println(ans);
}
public static void dfs(int root,int[] dp) {
for(int y:list[root]) {
dfs(y,dp);
dp[root]+=dp[y]+1;//子节点的子节点数量以及他自己
}
}
}
全排列问题（回溯）
问题描述
输入一个数组n，输出1到n的全排列。
代码
package lanqiaoyun;
import java.util.*;
public class quanpai {
static List<List<Integer>> list=new ArrayList<>();
//存放全排列
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int []v=new int [n+1];//表示当前数组访问
List<Integer> res=new ArrayList<>();
//当前集合存储了多少个元素
dfs(n,v,res);
for(List<Integer> x:list) {
for(int y:x) {
System.out.print(y+" ");
}
System.out.println("");
}
}
public static void dfs(int n,int[] v,List<Integer> res) {
if(res.size()==n) {
//表示当前集合中已经有n个元素，完成了全排列
list.add(new ArrayList<>(res));
return ;
}
for(int i=1;i<=n;i++) {
if(v[i]==1) {
continue;
}//不合法，当前数已经被访问过了
res.add(i);
v[i]=1;
dfs(n,v,res);
res.remove(res.size()-1);
v[i]=0;
}
}
}
