算法（图+递归排序）

Bertha 。 2022-12-07 11:44 142阅读 0赞

## 图 ##

### 图的深度优先遍历 邻接矩阵 ###

import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    // 图的深度优先遍历
    // 采用 邻接矩阵 存储图的数据
    // 包含非连通图的遍历， 返回遍历结果集合，打印
    class MGraph{ 
         int n; //顶点数
         int e; //边数
         String[] vertex; // 顶点数组，存储定点编号，这里为String类型，如果顶点编号为[0 n-1],则可以不需要这个数组
         int[][] edges; // 邻接矩阵 n*n
    }
    
    public class DfsGraph { 
    
        public static void main(String[] args) { 
           // Scanner in=new Scanner(System.in);
            //new 一个图的实例
            MGraph graph=new MGraph();
            // 创建图
            creatGraph(graph);
            //打印图
            printg(graph);
            //对图进行遍历
           List<String> res= dfsGraph(graph);
            //打印遍历结果
            for (int i=0;i<res.size();i++){ 
                System.out.println(res.get(i));
            }
        }
        // 如果是连通图， 只调用此方法。给定图 和 起始点，开始遍历
        public  static String dfs( MGraph g,int start,int[] visitd,StringBuilder sb){ 
            visitd[start]=1;
           sb.append(g.vertex[start]);
            for(int i=0;i<g.n;i++){ 
                if(g.edges[start][i]>0 && visitd[i]==0){ 
                    dfs(g,i,visitd,sb);
                }
            }
            return sb.toString();
        }
        // 对图进行遍历，考虑非连通图
        public  static  List<String> dfsGraph(MGraph g){ 
             int[] visitd=new int[g.n];
             List<String> res=new ArrayList<>();
             for(int i=0;i<g.n;i++){ 
                 if(visitd[i]==0){ 
                     res.add(dfs(g,i,visitd,new StringBuilder()));
                 }
             }
            return res;
        }
    
        //根据输入，创建图的邻接矩阵
        public  static  void creatGraph(MGraph graph){ 
            Scanner in=new Scanner(System.in);
            //输入顶点数
            System.out.println("输入顶点数n");
            graph.n=in.nextInt();
            graph.vertex=new String[graph.n];
            graph.edges=new int[graph.n][graph.n];
    
            //输入顶点编号 可选
            System.out.println("输入顶点编号");
            for (int i=0;i< graph.n;i++){ 
                graph.vertex[i]=in.next();
            }
            //输入 边的信息 可变
            System.out.println("输入 边的信息 ");
            for (int i=0;i<graph.edges.length;i++){ 
                for (int j=0;j<graph.edges.length;j++){ 
                    graph.edges[i][j]=in.nextInt();
                }
            }
        }
        //打印图
        public  static  void  printg(MGraph g){ 
            for(int i=0;i<g.n;i++){ 
                System.out.print(g.vertex[i]+" ");
            }
            System.out.println();
            for (int i=0;i<g.n;i++){ 
                for (int j=0;j<g.n;j++){ 
                    System.out.print(g.edges[i][j]+" ");
                }
                System.out.println();
            }
        }
    }

### 广度优先遍历 邻接矩阵 ###

import java.util.*;
    
    //图的 广度优先遍历
    // 采用 邻接矩阵 存储图的数据
    // 包含非连通图的遍历， 返回遍历结果集合，打印
    class Graph{ 
        int n; //顶点数
        int e; //边数
        String[] vertex; // 顶点数组，存储定点编号，这里为String类型，如果顶点编号为[0 n-1],则可以不需要这个数组
        int[][] edges; // 邻接矩阵 n*n ，存放边的权值
    }
    
    public class BfsGraph { 
        public static void main(String[] args) { 
            //new 一个图的实例
            Graph graph=new Graph();
            // 创建图
            creatGraph(graph);
            //打印图
           // printg(graph);
            //对图进行遍历
            List<String> res= bfsGraph(graph);
            //打印遍历结果
            for (int i=0;i<res.size();i++){ 
                System.out.println(res.get(i));
            }
    
        }
        // 如果是连通图， 只调用此方法。给定图 和 起始点，开始遍历
        public  static String bfs( Graph g,int start,int[] visitd,StringBuilder sb){ 
            visitd[start]=1;
            sb.append(g.vertex[start]);
            Queue<Integer> que=new LinkedList<>();
            que.add(start);
            while (!que.isEmpty()){ 
                int index=que.poll();
                for(int i=0;i<g.n;i++){ 
                    if(visitd[i]==0 && g.edges[index][i]>0){ 
                        visitd[i]=1;
                        sb.append(g.vertex[i]);
                        que.add(i);
                    }
                }
            }
            return sb.toString();
        }
        // 对图进行遍历，考虑非连通图
        public  static  List<String> bfsGraph(Graph g){ 
            int[] visitd=new int[g.n];
            List<String> res=new ArrayList<>();
            for(int i=0;i<g.n;i++){ 
                if(visitd[i]==0){ 
                    res.add(bfs(g,i,visitd,new StringBuilder()));
                }
            }
            return res;
        }
    
        //根据输入，建立邻接矩阵
        public  static  void creatGraph(Graph graph){ 
            Scanner in=new Scanner(System.in);
            //输入顶点数
            System.out.println("输入顶点数n");
            graph.n=in.nextInt();
            graph.vertex=new String[graph.n];
            graph.edges=new int[graph.n][graph.n];
    
            //输入顶点编号 可选
            System.out.println("输入顶点编号");
            for (int i=0;i< graph.n;i++){ 
                graph.vertex[i]=in.next();
            }
            //输入 边的信息 可变
            System.out.println("输入 边的信息 ");
            for (int i=0;i<graph.edges.length;i++){ 
                for (int j=0;j<graph.edges.length;j++){ 
                    graph.edges[i][j]=in.nextInt();
                }
            }
        }
    }

### 图的广度优先搜索遍历 邻接表 存储 ###

//图的广度优先搜索遍历
    // 采用 邻接表 存储
    import java.util.*;
    
    //边节点
    class  ANode{ 
        int num; // 边所代表的顶点的序号
        ANode next; //该边所指向的下一条边
        int w; //该边的权值
    }
    
    //顶点节点
    class   VNode{ 
        ANode first; //指向节点的第一条边
        String name;  // 节点名字（编号） //可选
    
    }
    class Graph{ 
        int n; //图的节点数
        int e; // 边数
        List<VNode> vNode; // 邻接表
    }
    
    public class BfsAgraph { 
        public static void main(String[] args) { 
            Graph graph=new Graph();
            //建立邻接表
            creatGraph(graph);
            //深度优先搜索
            List<String> res=bfsAgraph(graph);
            //输出遍历结果
            for (int i=0;i<res.size();i++){ 
                System.out.print(res.get(i)+" ");
            }
        }
        //建立邻接表
        public  static  void  creatGraph(Graph g){ 
            Scanner in=new Scanner(System.in);
            //输入顶点个数：
            System.out.println("输入顶点个数：");
            int n=in.nextInt();
            g.n=n;
            g.vNode=new ArrayList<>();
            //输入 顶点编号 可选
            System.out.println("输入顶点编号：");
            for(int i=0;i<g.n;i++){ 
                VNode vn=new VNode();
                vn.name=in.next();
                vn.first=null;
                g.vNode.add(vn);
            }
            //输入 边的关系 l r w 可变
            //输入边数e
            System.out.println("输入边数 e：");
            g.e=in.nextInt();
            System.out.println("输入边,权重：");
            for (int i=0;i<g.e;i++){ 
                int l=in.nextInt();
                int r=in.nextInt();
                int w=in.nextInt();
                ANode arc=new ANode();
                arc.num=r;
                arc.w=w;
                arc.next= g.vNode.get(l).first;
                g.vNode.get(l).first=arc;
            }
        }
        //给定起点，开始遍历
        public  static  String bfs(Graph g,int start,int[] visited,StringBuilder sb){ 
            visited[start]=1;
            sb.append(g.vNode.get(start).name);
            ANode p;
            Queue<Integer> que=new LinkedList<>();
            que.add(start);
            while (!que.isEmpty()){ 
                int index=que.poll();
                p=g.vNode.get(index).first;
                while (p!=null){ 
                    if(visited[p.num]==0){ 
                        visited[p.num]=1;
                        sb.append(g.vNode.get(p.num).name);
                        que.add(p.num);
                    }
                    p=p.next;
                }
            }
            return sb.toString();
        }
        //包含非连通图的遍历
        public  static List<String> bfsAgraph(Graph g){ 
            int[] visited=new int[g.n];
            List<String> res=new ArrayList<>();
            for (int i=0;i<g.n;i++){ 
                if(visited[i]==0){ 
                    res.add(bfs(g,i,visited,new StringBuilder()));
                }
            }
            return res;
        }
    }

### 图的深度优先搜索遍历 邻接表 ###

//图的深度优先搜索遍历
    // 采用 邻接表 存储
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    //边节点
    class  ArcNode{ 
        int num; // 边所代表的顶点的序号
        ArcNode next; //该边所指向的下一条边
        int w; //该边的权值
    }
    
    //顶点节点
    class   VerNode{ 
        ArcNode first; //指向节点的第一条边
        String name;  // 节点名字（编号） //可选
    
    }
    class AGraph{ 
        int n; //图的节点数
        int e; // 边数
        List<VerNode> vNode; // 邻接表
    }
    
    public class DfsAgraph { 
        public static void main(String[] args) { 
            AGraph graph=new AGraph();
            //建立邻接表
            creatGraph(graph);
            //深度优先搜索
            List<String> res=dfsAgraph(graph);
            //输出遍历结果
            for (int i=0;i<res.size();i++){ 
                System.out.print(res.get(i)+" ");
            }
        }
        //建立邻接表
        public  static  void  creatGraph(AGraph g){ 
            Scanner in=new Scanner(System.in);
            //输入顶点个数：
            System.out.println("输入顶点个数：");
            int n=in.nextInt();
            g.n=n;
            g.vNode=new ArrayList<>();
            //输入 顶点编号 可选
            System.out.println("输入顶点编号：");
            for(int i=0;i<g.n;i++){ 
                VerNode vn=new VerNode();
                g.vNode.add(vn);
                g.vNode.get(i).name=in.next();
    
            }
            //输入 边的关系 l r w 可变
            //输入边数e
            System.out.println("输入边数 e：");
            g.e=in.nextInt();
            System.out.println("输入边,权重：");
            for (int i=0;i<g.e;i++){ 
                int l=in.nextInt();
                int r=in.nextInt();
                int w=in.nextInt();
                ArcNode arc=new ArcNode();
                arc.num=r;
                arc.w=w;
                arc.next= g.vNode.get(l).first;
                g.vNode.get(l).first=arc;
            }
        }
        //给定起点，开始遍历
        public  static  String dfs(AGraph g,int start,int[] visited,StringBuilder sb){ 
            visited[start]=1;
            sb.append(g.vNode.get(start).name);
            ArcNode p=g.vNode.get(start).first;
            while (p!=null){ 
                if(visited[p.num]==0){ 
                    dfs(g,p.num,visited,sb);
                }
                p=p.next;
            }
            return sb.toString();
        }
        //包含非连通图的遍历
        public  static List<String> dfsAgraph(AGraph g){ 
            int[] visited=new int[g.n];
            List<String> res=new ArrayList<>();
            for (int i=0;i<g.n;i++){ 
                if(visited[i]==0){ 
                    res.add(dfs(g,i,visited,new StringBuilder()));
                }
            }
            return res;
        }
    }

## 一维 递归回溯 ##

### 字符串数组，按照字符串数组的顺序，对数组每一个元素取一个字符进行组合，有多少种组合 ###

import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    //一维递归回溯 字符串数组，按照字符串数组的顺序，对数组每一个元素取一个字符进行组合，有多少种组合，当组合出现重复字符时，在该组合后加上--circly 字符串
    public class Main1 { 
        static  List<String> res;
        static  String last="--cycley";
        public static void main(String[] args) { 
            Scanner in=new Scanner(System.in);
            String ss=in.nextLine();
            Scanner sc=new Scanner(ss);
            List<String> list=new ArrayList<>();
            while (sc.hasNext()){ 
                list.add(sc.next());
            }
            findAll(list);
            for(int i=0;i<res.size();i++){ 
                System.out.println(res.get(i));
            }
    
    
    
        }
         public  static  void findpath(List<String> list,int index, String sb,boolean flag){ 
            if(index==list.size()){ 
                if(!flag){ 
                   sb=sb+last;
                }
                res.add(sb);
                return;
            }
            for(int i=0;i<list.get(index).length();i++){ 
                if(sb.contains(list.get(index).charAt(i)+"")){ 
                   flag=false;
                }
                    findpath(list,index+1,sb+list.get(index).charAt(i),flag);
            }
            return;
    
         }
        public  static void findAll(List<String> list){ 
            res=new ArrayList<>();
            findpath(list,0,"",true);
        }
    }

### 全排列 ###

//对一个字符串序列 或 整数数组 排列，求所有排列结果 排列总数
    //以字符串为例
    public class Main2 { 
        static List<String> res;
        static  boolean[] visited;
        public static void main(String[] args) { 
            Scanner in=new Scanner(System.in);
            String str=in.next();
            findAll(str);
            for (int i=0;i<res.size();i++){ 
                System.out.println(res.get(i));
            }
    
        }
        public  static  void findRes(String str,int index,StringBuilder sb){ 
            if(index==str.length()){ 
                res.add(sb.toString());
                return;
            }
            for(int i=0;i<str.length();i++){ 
                if(!visited[i]){ 
                    sb.append(str.charAt(i));
                    visited[i]=true;
                    findRes(str,index+1,sb);
                    sb.deleteCharAt(sb.length()-1);
                    visited[i]=false;
                }
            }
            return;
        }
        public  static  void  findAll(String str){ 
            res=new ArrayList<>();
            visited=new boolean[str.length()];
            findRes(str,0,new StringBuilder());
        }
    }

### 组合问题 c(n,k) ###

//组合问题 c(n,k),n个数中选k个数，有多少种组合,
    public class Main3 { 
        static  List<String> res;
        public static void main(String[] args) { 
            Scanner in=new Scanner(System.in);
            int n=in.nextInt();
            int k=in.nextInt();
            findAll(n,k);
            for (int i=0;i<res.size();i++){ 
                System.out.println(res.get(i));
            }
    
        }
        public  static  void findAll(int n, int k,int start,StringBuilder sb){ 
            if(sb.length()==k){ 
                res.add(sb.toString());
                return;
            }
            for(int i=start;i<=n-k+1;i++){ 
                sb.append(i);
                findAll(n,k,i+1,sb);
                sb.deleteCharAt(sb.length()-1);
    
            }
            return;
    
        }
    
        public  static  void findAll(int n,int k){ 
            res=new ArrayList<>();
            findAll(n,k,0,new StringBuilder());
        }
    }

## 二维递归 ##

### 在矩阵中，寻找 给定字符串是否存在 ###

import java.util.Scanner;
    
    //在矩阵中，寻找 给定字符串是否存在
    public class Main1 { 
        static int[][] dre={ { -1,0},{ 0,1},{ 1,0},{ 0,-1}};
        static  boolean[][] visited;
    
    
        public static void main(String[] args) { 
            Scanner in=new Scanner(System.in);
            int n=in.nextInt();
            int m=in.nextInt();
            char[][] chars=new char[n][m];
            for (int i=0;i<chars.length;i++){ 
                for (int j=0;j<chars[0].length;j++){ 
                    chars[i][j]=in.next().charAt(0);
                }
            }
            String word=in.next();
           System.out.println(exit(chars,word));
        }
        public  static  boolean inRight(int x,int y,int m,int n){ 
            return  x>=0 && x<m && y>=0 && y<n;
        }
        public  static  boolean serch(char[][] chars,String word,int index,int x,int y){ 
            if(index==word.length()-1){ 
                return chars[x][y]==word.charAt(index);
            }
            if(chars[x][y]==word.charAt(index)){ 
                visited[x][y]=true;
                for (int i=0;i<4;i++){ 
                    int newx=x+dre[i][0];
                    int newy=y+dre[i][1];
                    if(inRight(newx,newy,chars.length,chars[0].length) && !visited[newx][newy]
                            && serch(chars,word,index+1,newx,newy)){ 
                        return  true;
                    }
                }
    
            }
            return  false;
        }
    
        public  static  boolean exit(char[][] chars,String word){ 
            if(chars.length<=0 || chars[0].length<=0 || word.length()<=0){ 
                return false;
            }
            visited=new boolean[chars.length][chars[0].length];
            for (int i=0;i<chars.length;i++){ 
                for (int j=0;j<chars[0].length;j++){ 
                    if(serch(chars,word,0,i,j)){ 
                        return true;
                    }
                }
            }
            return false;
    
        }
    }

### 二维数组 ，找出连续递减的路径 返回最长的路径长度 ###

//在矩阵中，二维数组 ，找出连续递减的路径 返回最长的路径长度
    public class Main2 { 
        static int[][] dre={ { -1,0},{ 0,1},{ 1,0},{ 0,-1}};
        static  boolean[][] visited;
        public static void main(String[] args) { 
            Scanner in=new Scanner(System.in);
            int n=in.nextInt();
            int m=in.nextInt();
            int[][] arr=new int[n][m];
            for (int i=0;i<arr.length;i++){ 
                for (int j=0;j<arr[0].length;j++){ 
                    arr[i][j]=in.nextInt();
                }
            }
            System.out.println(findMaxPath(arr));
    
        }
        public  static  boolean inRight(int x,int y,int m,int n){ 
            return  x>=0 && x<m && y>=0 && y<n;
        }
        public  static  int serch(int[][] arr, int x,int y,boolean[][] visited,int len){ 
            visited[x][y]=true;
                for (int i=0;i<4;i++){ 
                    int newx=x+dre[i][0];
                    int newy=y+dre[i][1];
                    if(inRight(newx,newy,arr.length,arr[0].length) && !visited[newx][newy]){ 
                        if(arr[newx][newy]<arr[x][y]){ 
                            len=Math.max(len,serch(arr,newx,newy,visited,len+1));
                    }
                }
    
            }
            return  len;
        }
    
        public  static  int  findMaxPath(int[][] arr){ 
            if(arr.length<=0 || arr[0].length<=0 ){ 
                return 0;
            }
            visited=new boolean[arr.length][arr[0].length];
            int maxres=0;
            for (int i=0;i<arr.length;i++){ 
                for (int j=0;j<arr[0].length;j++){ 
                    int max=serch(arr,i,j,visited,1);
                    maxres=Math.max(maxres,max);
                }
            }
            return maxres;
    
        }
    }