【数据结构】无向图的遍历（广度搜索和深度搜索）

桃扇骨 2022-04-04 05:08 153阅读 0赞

### 说明 ###

1.  以邻接表作为存储结构
2.  以用户指定的结点分别进行广度搜索和深度搜索
3.  相应的生成树的边集

### 运行截图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70]

### 源代码 ###

import java.util.*;
    
    public class AdjacencyList {
        
        public static void main(String[] args) {
        
    
            CreateGraph createGraph=new CreateGraph();
            createGraph.initGraph();
            createGraph.outputGraph();
            createGraph.DFSTraverse();
            createGraph.BFSTraverse();
            createGraph.show();
        }
    
    }
    class Vertex{
         //顶点类
        String vername;//顶点的名称
        Vertex nextNode;//邻接的顶点
    }
    class Graph{
         //图类
        Vertex[] vertices;//顶点数组
        int verNum = 0;//顶点数量
        int edgeNum = 0;//边的数量
    }
    class Arc {
         //生成树的边集结点
        String start;
        String end;
    
    }
    class CreateGraph{
        
        static private Graph graph = new Graph();
        static private boolean[] visited;//遍历辅助数组，标记该顶点是否访问过
        public Vertex getVertex(String str){
        
            //根据指定的顶点名称str，返回对应的顶点
            //如果顶点不存在，返回null
            for(int i = 1;i<=graph.verNum;i++){
        
                if(graph.vertices[i].vername.equals(str))
                    return  graph.vertices[i];
            }
            return  null;
        }
        public void initGraph(){
         //创建图
            Scanner in = new Scanner(System.in);
            System.out.println("输入顶点的数量");
            graph.verNum = in.nextInt();
            graph.vertices = new Vertex[graph.verNum+1];//动态建立顶点数组，vertices[0]不用
            visited = new boolean[graph.verNum+1];//动态建立遍历辅助数组
            System.out.println("输入弧的数量");
            graph.edgeNum = in.nextInt();
            System.out.println("请输入各个顶点的名称:");
            for (int i=1;i<=graph.verNum;i++){
         //读取各个顶点的名称
                //构建顶点数组
                Vertex vertex = new Vertex();
                vertex.vername = in.next();
                vertex.nextNode = null;
                graph.vertices[i] = vertex;
            }
            System.out.println("请依次输入无向图的各条弧的两个顶点：");
            for (int i=1;i<=graph.edgeNum;i++) {
        
                String v1 = in.next(); //读取的两个顶点的名称
                String v2 = in.next();
                Vertex vertex1 = getVertex(v1);//根据两个顶点的名称在顶点数组里找到对应的顶点
                Vertex vertex2 = getVertex(v2);
                if (vertex1 == null) {
         //检查是否输入错误
                    System.out.println(v1 + "不是图中的一个顶点，请重新输入");
                    i--;continue;
                } else if (vertex2 == null) {
        
                    System.out.println(v2 + "不是图中的一个顶点，请重新输入");
                    i--;continue;
                } else {
        
                    //输入正确的情况下，
                    //新建顶点，并插入到邻接表中
                    Vertex newVertex1 = new Vertex();
                    newVertex1.vername = v2;
                    newVertex1.nextNode = vertex1.nextNode;
                    vertex1.nextNode = newVertex1;
                    Vertex newVertex2 = new Vertex();
                    newVertex2.vername =v1;
                    newVertex2.nextNode = vertex2.nextNode;
                    vertex2.nextNode = newVertex2;
                }
            }
        }
        public void outputGraph(){
         //输出图的邻接链表
            System.out.println("输入的无向图图的邻接链表为：");
            for(int i=1;i<=graph.verNum;i++){
        
                Vertex vertex=graph.vertices[i];
                System.out.print(vertex.vername);
    
                Vertex current=vertex.nextNode;
                while(current!=null){
        
                    System.out.print("-->"+current.vername);
                    current=current.nextNode;
                }
                System.out.println();
            }
        }
        ArrayList<Arc> Dset = new ArrayList<>();//深度搜索生成树的边集
        public  int find(Vertex node){
        //在顶点数组里找到对应的顶点，并返回该顶点的位置
            for (int i =1;i<=graph.vertices.length;i++)
                if (graph.vertices[i].vername.equals(node.vername)==true)
                    return i;
            return -1;
        }
        public void DFSTraverse(){
         //深度搜索辅助函数
            System.out.println("请输入从哪个顶点开始进行深度优先搜索（输入顶点名称）");
            Vertex first = new Vertex();
            Scanner in  = new Scanner(System.in);
            first.vername = in.next();
            int index = find(first);//返回该顶点在数组中的位置
            for (int i=1;i<=graph.verNum;i++)
                visited[i]=false;
    
            System.out.println("深度优先搜索遍历的顺序为：");
            for (int i=index;i<=graph.verNum;i++){
        
                if (!visited[i]) DFS(i);
            }
            for(int i=1;i<index;i++){
        
                if (!visited[i]) DFS(i);
            }
            System.out.println();
    
        }
        public  void DFS(int v){
        //深度搜索
            visited[v]=true;
            System.out.print(graph.vertices[v].vername+"  ");//输出当前顶点的名称
            Vertex CurrentNode_NextNode = graph.vertices[v].nextNode;//获取当前顶点邻接的下一个顶点
            while (CurrentNode_NextNode != null){
        
                int index = find(CurrentNode_NextNode);
                if (!visited[index]) {
        
                    Arc asc = new Arc();
                    asc.start = graph.vertices[v].vername;
                    asc.end =CurrentNode_NextNode.vername;
                    Dset.add(asc);
                    DFS(index);
                }
                else
                    CurrentNode_NextNode = CurrentNode_NextNode.nextNode;
            }
        }
        ArrayList<Arc> Bset = new ArrayList<>();//广度搜索生成树的边集
        public void BFSTraverse(){
        //广度搜索辅助函数
            System.out.println("请输入从哪个顶点开始进行广度优先搜索（输入顶点名称）");
            Vertex first = new Vertex();
            Scanner in  = new Scanner(System.in);
            first.vername = in.next();
            int index = find(first);//返回该顶点在数组中的位置
            for (int i=0;i<=graph.verNum;i++)//重新重置visited 数组
                visited[i] = false;
    
            System.out.println("广度优先搜索遍历的顺序为：");
            for (int i=index;i<=graph.verNum;i++){
        
                if (!visited[i]) BFS(i);
            }
            for(int i=1;i<index;i++){
        
                if (!visited[i]) BFS(i);
            }
            System.out.println();
        }
        public void BFS(int v){
        //广度搜索
            visited[v]=true;
            System.out.print(graph.vertices[v].vername+"  ");//输出当前顶点的名称
            Queue<Integer> queue = new LinkedList<>();//辅助队列，放置访问过的结点的位置
            queue.offer(v);//将v放入队列中
            while (!queue.isEmpty()){
        
                v = queue.poll(); //出队
                Vertex CurrentNode_NextNode = graph.vertices[v].nextNode;//当前顶点的下一个邻接点
                while (CurrentNode_NextNode!=null){
         //如果不为空
                    if (visited[find(CurrentNode_NextNode)]==false){
         //当该邻接点没有访问过时
                        System.out.print(CurrentNode_NextNode.vername+"  "); //打印该顶点的信息
                        visited[find(CurrentNode_NextNode)]=true; //标记该结点已访问
                        queue.offer(find(CurrentNode_NextNode));//放入队列中
                        Arc  arc = new Arc();//新建边集
                        arc.start = graph.vertices[v].vername;//边集的起点
                        arc.end = CurrentNode_NextNode.vername;//边集的终点
                        Bset.add(arc);//放入集合中
                    }
                    CurrentNode_NextNode = CurrentNode_NextNode.nextNode;//访问下一个结点
                }
            }
    
        }
        public void show(){
         //打印生成树边集
            System.out.println("深度搜索生成树边集：");
            Iterator  Diterator= Dset.iterator();
            while (Diterator.hasNext()){
        
                Arc arc = (Arc) Diterator.next();
                System.out.print("("+arc.start+","+arc.end+")   ");
            }
            System.out.println();
            System.out.println("广度搜索生成树边集：");
            Iterator  Biterator= Bset.iterator();
            while (Biterator.hasNext()){
        
                Arc arc = (Arc) Biterator.next();
                System.out.print("("+arc.start+","+arc.end+")   ");
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70]: /images/20220404/e6392b142f674c4f85e73dc77f920c82.png