欢迎移步博主CSDN:CSDN博客

无向图的两种遍历算法的实现

简介

图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为

$$ G = (V,E) $$

如果图的任意两个顶点之间的边都是无向边,则称该图为无向图,否则称该图为有向图

图的两种遍历算法思想

  • 深度优先遍历算法思想
    (1)访问顶点v;

(2)从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历;
(3)重复上述两步,直至图中所有和v有路径相通的顶点都被访问到

  • 广度优先遍历算法思想
    (1)访问顶点v;

(2)依次访问v的各个未被访问的邻接点v1,v2,v3......
(3)分别从v1,v2,v3......出发依次访问它们未被访问的邻接点,并使先被访问顶点的邻接点先于后被访问顶点的邻接点被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

采用邻接矩阵存储

图的邻接矩阵存储也称为数组表示法,其方法是用一个以为数组存储图中顶点的信息,用一个二维数组存储图中边的信息,存储顶点之间临界关系的二维数组称为邻接矩阵。


以下面这个无向图为例进行实现
31.jpg

  • 该无向图的DFS访问顺序:V0->V1->V4->V5->V2->V3
  • 该无向图的BFS访问顺序:V0->V1->V2->V3->V4->V5

为了省时间(其实是自己懒 ),此处省略邻接矩阵的构造过程,采用手动写入边集和点集构建该无向图。

        //手动构造图的点集和边集
        //点集
        int[] vector = {
                0,1,2,3,4,5
        };
        //边集
        int[][] arc ={
                {0,1,1,1,1,0},
                {1,0,0,0,1,0},
                {1,0,0,0,1,0},
                {1,0,0,0,0,0},
                {1,1,1,0,0,1},
                {0,0,0,0,1,1}
        };
        //记录是否访问
        int[] visited = {
                0,0,0,0,0,0
        };

深度优先遍历(递归实现)

     //图的深搜DFS,递归
    public static void DFS(int[] vector, int[] visited, int[][] arc,int i){
        //访问结点并标记
        System.out.println(vector[i]);
        visited[i]=1;
        for (int j = 0;j<vector.length; ++j){
            if (visited[j]==0 && arc[i][j]==1)
                DFS(vector,visited,arc,j);
        }
    }

深度优先遍历 (非递归实现)

//图的深搜DFS ,非递归
    public static void DFS(int[] vector, int[] visited, int[][] arc){
        //访问第一个顶点并入栈
        System.out.println(vector[0]);
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        visited[0] = 1;
        while(!stack.isEmpty()){
            //获取栈顶元素
            int x = stack.peek();
            //标志位
            boolean flag = false;
            for (int i = 0; i<vector.length;++i){
                if (visited[i]==0 && arc[x][i]==1){
                    System.out.println(vector[i]);
                    //入栈
                    stack.push(i);
                    //更改访问位,标志位
                    visited[i] = 1;
                    flag = true;
                    break;
                }
            }
            //出栈
            if (!flag)
                stack.pop();
        }
    }

广度优先遍历

//图的广搜BFS,非递归
    public static void BFS(int[] vector, int[] visited, int[][] arc){
        Queue<Integer> queue = new LinkedList<Integer>();
        //第一个顶点入队
        queue.offer(0);
        while (!queue.isEmpty()){
            //出队
            int x = queue.poll();
            //访问结点并标记
            System.out.println(vector[x]);
            visited[x] = 1;
            //寻找连通的结点并入队
            for (int i = 0; i<vector.length;++i){
                if (visited[i]==0 && arc[x][i]==1){
                    queue.offer(i);
                    visited[i] = 1;
                }
            }
        }
    }

采用邻接表存储

图的邻接表存储是一种顺序存储与链接存储相结合的存储方法,类似于数的孩子链表表示法。对于图的每个顶点v,将所有邻接于v的顶点链成一个单链表,称为顶点v的边表(对于有向图则称为出边表)。

顶点类:

/**
 * @Author zbl
 * @Date: 2019/11/18/ 17:59
 * @Description
 */

//顶点结点
public class VertexNode{
    public int vertex;
    public ArcNode firstEdge;
}

边表类:

/**
 * @Author zbl
 * @Date: 2019/11/18/ 17:12
 * @Description
 */

//边结点
public class ArcNode {
    //邻接点域
    public int adjvex;
    public ArcNode next;
    public ArcNode(){}
    public ArcNode(int adjvex,ArcNode arcNode) {this.adjvex=adjvex;this.next=arcNode;}
}

以下面这个无向图为例进行实现
39.jpg

  • 该无向图的DFS访问顺序:V0->V1->V4->V2->V3
  • 该无向图的BFS访问顺序:V0->V1->V2->V3->V4

为了省时间(其实是自己懒 ),此处省略邻接表的构造过程,采用手动写入边集和点集构建该无向图。

        //手动构造图的点集和边集
        //手动构造点集和边集
        VertexNode[] vertex = new VertexNode[5];
        for (int i = 0;i<vertex.length;++i){
            vertex[i] = new VertexNode();
            vertex[i].vertex=i;
        }


        ArcNode V03 = new ArcNode(3,null);
        ArcNode V02 = new ArcNode(2,V03);
        ArcNode V01 = new ArcNode(1,V02);
        ArcNode V12 = new ArcNode(4,null);
        ArcNode V11 = new ArcNode(0,V12);
        ArcNode V22 = new ArcNode(3,null);
        ArcNode V21 = new ArcNode(0,V22);
        ArcNode V32 = new ArcNode(2,null);
        ArcNode V31 = new ArcNode(0,V32);
        ArcNode V41 = new ArcNode(1,null);

        vertex[0].firstEdge=V01;
        vertex[1].firstEdge=V11;
        vertex[2].firstEdge=V21;
        vertex[3].firstEdge=V31;
        vertex[4].firstEdge=V41;

        for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

深度优先遍历(递归实现)

     /**
    * @Description: 图的深搜DFS,邻接矩阵存储,递归
    * @Param: [vertex, visited, i]
    * @return: void
    * @Author: zbl
    * @Date: 2019/11/18
    */
    public static void DFS(VertexNode[] vertex,int[] visited,int i){
        System.out.println(vertex[i].vertex);
        visited[i]=1;
        ArcNode tmp = vertex[i].firstEdge;
        while(tmp != null){
            int j = tmp.adjvex;
            if(visited[j]==0)
                DFS(vertex,visited,j);
            tmp = tmp.next;
        }
    }

深度优先遍历 (非递归实现)

/**
     * @Description: 图的深搜DFS,邻接矩阵存储,非递归
     * @Param: [vertex, visited]
     * @return: void
     * @Author: zbl
     * @Date: 2019/11/18
     */
    public static void DFS(VertexNode[] vertex,int[] visited){
        Stack<Integer> stack = new Stack<Integer>();
        //访问第一个顶点并入栈
        System.out.println(vertex[0].vertex);
        stack.push(0);
        visited[0]=1;
        //栈不为空
        while(!stack.isEmpty()){
            boolean flag = false;
            //获取栈顶但不弹栈
            int i = stack.peek();
            ArcNode tmp = vertex[i].firstEdge;
            //遍历边表
            while(tmp!=null){
                if (visited[tmp.adjvex]==0){
                    //访问并入栈
                    System.out.println(vertex[tmp.adjvex].vertex);
                    stack.push(tmp.adjvex);
                    //更改访问位,标志位
                    visited[tmp.adjvex]=1;
                    flag = true;
                    break;
                }
                tmp = tmp.next;
            }
            //弹栈
            if(!flag)
                stack.pop();
        }
    }

广度优先遍历

    /**
    * @Description: 图的广搜BFS,邻接矩阵存储,非递归
    * @Param: [vertex, visited]
    * @return: void
    * @Author: zbl
    * @Date: 2019/11/18
    */
    public static void BFS(VertexNode[] vertex,int[] visited){
        for (int i = 0; i<vertex.length; ++i){
            ArcNode tmp = vertex[i].firstEdge;
            //若未访问,则访问并标记
            if (visited[i]==0){
                System.out.println(vertex[i].vertex);
                visited[i]=1;
            }

            while(tmp!=null){
                //若未访问,则访问并标记
                if (visited[tmp.adjvex]==0){
                    System.out.println(vertex[tmp.adjvex].vertex);
                    visited[tmp.adjvex]=1;
                }
                tmp = tmp.next;
            }
        }
    }

完整函数代码

顶点类和边表类在上面已经给出,在此就不重复放出来了。

import javafx.scene.shape.Arc;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
 * author zbl
 *
 * datetime 2019.11.18
 *
 */
public class Main {

    //图的深搜DFS ,非递归
    public static void DFS(int[] vector, int[] visited, int[][] arc){
        //访问第一个顶点并入栈
        System.out.println(vector[0]);
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        visited[0] = 1;
        while(!stack.isEmpty()){
            //获取栈顶元素
            int x = stack.peek();
            //标志位
            boolean flag = false;
            for (int i = 0; i<vector.length;++i){
                if (visited[i]==0 && arc[x][i]==1){
                    System.out.println(vector[i]);
                    //入栈
                    stack.push(i);
                    //更改访问位,标志位
                    visited[i] = 1;
                    flag = true;
                    break;
                }
            }
            //出栈
            if (!flag)
                stack.pop();
        }
    }

    //图的深搜DFS,递归
    public static void DFS(int[] vector, int[] visited, int[][] arc,int i){
        //访问结点并标记
        System.out.println(vector[i]);
        visited[i]=1;
        for (int j = 0;j<vector.length; ++j){
            if (visited[j]==0 && arc[i][j]==1)
                DFS(vector,visited,arc,j);
        }
    }

    //图的广搜BFS,非递归
    public static void BFS(int[] vector, int[] visited, int[][] arc){
        Queue<Integer> queue = new LinkedList<Integer>();
        //第一个顶点入队
        queue.offer(0);
        while (!queue.isEmpty()){
            //出队
            int x = queue.poll();
            //访问结点并标记
            System.out.println(vector[x]);
            visited[x] = 1;
            //寻找连通的结点并入队
            for (int i = 0; i<vector.length;++i){
                if (visited[i]==0 && arc[x][i]==1){
                    queue.offer(i);
                    visited[i] = 1;
                }

            }
        }
    }

    /**
     * @Description: 图的深搜DFS,邻接矩阵存储,非递归
     * @Param: [vertex, visited]
     * @return: void
     * @Author: zbl
     * @Date: 2019/11/18
     */
    public static void DFS(VertexNode[] vertex,int[] visited){
        Stack<Integer> stack = new Stack<Integer>();
        //访问第一个顶点并入栈
        System.out.println(vertex[0].vertex);
        stack.push(0);
        visited[0]=1;
        //栈不为空
        while(!stack.isEmpty()){
            boolean flag = false;
            //获取栈顶但不弹栈
            int i = stack.peek();
            ArcNode tmp = vertex[i].firstEdge;
            //遍历边表
            while(tmp!=null){
                if (visited[tmp.adjvex]==0){
                    //访问并入栈
                    System.out.println(vertex[tmp.adjvex].vertex);
                    stack.push(tmp.adjvex);
                    //更改访问位,标志位
                    visited[tmp.adjvex]=1;
                    flag = true;
                    break;
                }
                tmp = tmp.next;
            }
            //弹栈
            if(!flag)
                stack.pop();
        }
    }

    /**
    * @Description: 图的深搜DFS,邻接矩阵存储,递归
    * @Param: [vertex, visited, i]
    * @return: void
    * @Author: zbl
    * @Date: 2019/11/18
    */
    public static void DFS(VertexNode[] vertex,int[] visited,int i){
        System.out.println(vertex[i].vertex);
        visited[i]=1;
        ArcNode tmp = vertex[i].firstEdge;
        while(tmp != null){
            int j = tmp.adjvex;
            if(visited[j]==0)
                DFS(vertex,visited,j);
            tmp = tmp.next;
        }
    }
    
    /**
    * @Description: 图的广搜BFS,邻接矩阵存储,非递归
    * @Param: [vertex, visited]
    * @return: void
    * @Author: zbl
    * @Date: 2019/11/18
    */
    public static void BFS(VertexNode[] vertex,int[] visited){
        for (int i = 0; i<vertex.length; ++i){
            ArcNode tmp = vertex[i].firstEdge;
            //若未访问,则访问并标记
            if (visited[i]==0){
                System.out.println(vertex[i].vertex);
                visited[i]=1;
            }

            while(tmp!=null){
                //若未访问,则访问并标记
                if (visited[tmp.adjvex]==0){
                    System.out.println(vertex[tmp.adjvex].vertex);
                    visited[tmp.adjvex]=1;
                }
                tmp = tmp.next;
            }
        }
    }

    public static void main(String[] args) {
        //手动构造点集和边集
        //点集
        int[] vector = {
                0,1,2,3,4,5
        };
        //边集
        int[][] arc ={
                {0,1,1,1,1,0},
                {1,0,0,0,1,0},
                {1,0,0,0,1,0},
                {1,0,0,0,0,0},
                {1,1,1,0,0,1},
                {0,0,0,0,1,1}
        };
        //记录是否访问
        int[] visited = {
                0,0,0,0,0,0
        };
        System.out.println("===============邻接矩阵Start===============");
        System.out.println("Start DFS:");
        DFS(vector,visited,arc);
        System.out.println("End DFS\n");

        for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

        System.out.println("Start DFS:");
        DFS(vector,visited,arc,0);
        System.out.println("End DFS\n");

        for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

        System.out.println("Start BFS:");
        BFS(vector,visited,arc);
        System.out.println("End BFS");

        System.out.println("===============邻接矩阵End===============\n");

        System.out.println("===============邻接表Start===============");
        //手动构造点集和边集
        VertexNode[] vertex = new VertexNode[5];
        for (int i = 0;i<vertex.length;++i){
            vertex[i] = new VertexNode();
            vertex[i].vertex=i;
        }


        ArcNode V03 = new ArcNode(3,null);
        ArcNode V02 = new ArcNode(2,V03);
        ArcNode V01 = new ArcNode(1,V02);
        ArcNode V12 = new ArcNode(4,null);
        ArcNode V11 = new ArcNode(0,V12);
        ArcNode V22 = new ArcNode(3,null);
        ArcNode V21 = new ArcNode(0,V22);
        ArcNode V32 = new ArcNode(2,null);
        ArcNode V31 = new ArcNode(0,V32);
        ArcNode V41 = new ArcNode(1,null);

        vertex[0].firstEdge=V01;
        vertex[1].firstEdge=V11;
        vertex[2].firstEdge=V21;
        vertex[3].firstEdge=V31;
        vertex[4].firstEdge=V41;

        for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

        System.out.println("Start DFS:");
        DFS(vertex,visited);
        System.out.println("End DFS\n");

        for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

        System.out.println("Start DFS:");
        DFS(vertex,visited,0);
        System.out.println("End DFS\n");

        for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

        System.out.println("Start BFS:");
        BFS(vertex,visited);
        System.out.println("End BFS");
        System.out.println("===============邻接表End===============");
    }
}

注意事项

以上代码只适用于强连通图!!!
以上代码只适用于强连通图!!!
以上代码只适用于强连通图!!!
重要的事说三遍。

参考文献

  • 王红梅,胡明,王涛编著. 数据结构(C++版)(第二版)[M]. 清华大学出版社.
最后修改:2020 年 03 月 14 日 12 : 38 PM
如果觉得我的文章对你有用,请随意赞赏