数据结构复习之图的入门（深度优先搜索和广度优先搜索递归实现）

数据结构之图的入门

一、图的定义及分类

定义：图是有一组顶点和一组能够将两个顶点相连的边组成的

特殊的图：

• 自环：即一个顶点有一条连接自己的边
• 平行边：连接同一对顶点的边
  图的分类：
• 按照连接两个顶点的边的不同，图可以分为两种
  • 无向图：边仅仅连接两个顶点，没有方向
  • 有向图：边不仅连接两个顶点，并且具有方向

1.1 无向图

图的相关术语：

• 相邻顶点：当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点
• 度：某个顶点的度就是依附于该顶点的边数
• 子图：是一幅图中所有边的子集（包含这些依附的顶点）组成的图
• 路径：由边顺序连接的一组顶点组成
• 环：是一条至少含有一条边且终点和起点相同的路径
• 连通图：如果图中的任意两个顶点之间都存在路径可以到达，那么这个图就称为连通图
• 连通子图：一个非连通图由若*分组成，每个连通的部分都可以称为该图的连通子图

图的存储结构：

要表示一幅图，需要表示清楚图中的所有顶点和所有连接顶点的边

常见的图的存储结构有两种：邻接矩阵和邻接表

• 邻接矩阵：
  • 使用二维数组表示
  • 将顶点看为索引
  • 将边看为两个索引对应的元素的值为1右边，0无边
  • 表示图的空间复杂度为n^2
• 邻接表：
  • 使用一位数组和链表组成
  • 每个索引处存储一个队列，该队列中存储的是与该顶点相连的其他顶点
  • 空间复杂度小于n^2，后面会使用邻接表的形式表示图

1.2 手搓图

package GraphTest;


import LinearTest.QueueTest;

public class Graph {
    //顶点数目
    private final int V;
    //边的数目
    private int E;
    //邻接表
    private QueueTest<Integer>[] adj;
    public Graph(int V){
        //初始化顶点数量
        this.V = V;
        this.E = 0;
        this.adj = new QueueTest[V];
        for(int i = 0;i<adj.length;i++){
            adj[i] = new QueueTest<Integer>();
        }
    }
    //获取顶点数目
    public int V(){
        return V;
    }
    //获取边的数目
    public int E(){
        return E;
    }
    //向图中添加一条边，传入两个点，在两点间建立一条边
    public void addEdge(int v,int w){
        //把w添加到v的链表中，这样就有一条从v->w的边
        adj[v].enqueue(w);
        //把v添加到w的链表中，这样就有一条从w->v的边
        adj[w].enqueue(v);
        //边的数目++
        E++;
    }
    //获取和顶点v相邻的所有顶点
    public QueueTest<Integer> adj(int v){
        return adj[v];
    }
}

1.3 图的搜索

深度优先搜索DFS：

对一个连通图进行遍历的算法。思想：从顶点V0开始，沿着一条路径走，如果走到最后发现不能到达目标解，则返回上一个顶点，换一条路径继续走

不清楚，上代码debug跟几遍就OK

package GraphTest;

public class DepthFirstSearch {
    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录有多少个顶点与s顶点相通
    private int count;
    //构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点对应的所有相邻顶点
    public DepthFirstSearch(Graph G,int s){
        //创建一个对应所有顶点的是否搜索标记数组
        marked = new boolean[G.V()];
        //搜索G图所有与s相连的顶点
        dfs(G,s);
    }
    //深度优先遍历算法，传入要搜索的图和顶点
    private void dfs(Graph G,int s){
        //把当前顶点设置为已搜索，因为是无向图，防止重复搜索
        marked[s] = true;
        //开始查找s对应的邻接表中有边的结点
        for (Integer w : G.adj(s)) {
            //如果w结点未被搜索过，则递归调用该结点搜索
            if (!marked[w]){
                dfs(G,w);
            }
        }
        count++;
    }
    //判断w顶点与s顶点是否相通
    public boolean marked(int w){
        return marked[w];
    }
    //获取与顶点s相通的所有顶点的总数
    public int count(){
        return count;
    }

    public static void main(String[] args) {
        Graph G = new Graph(13);
        G.addEdge(0,5);
        G.addEdge(0,1);
        G.addEdge(0,2);
        G.addEdge(0,6);
        G.addEdge(5,3);
        G.addEdge(5,4);
        G.addEdge(3,4);
        G.addEdge(4,6);
        DepthFirstSearch search = new DepthFirstSearch(G,0);
        //测试与某个顶点相通的顶点数量
        int count = search.count();
        System.out.println("与起点0相通的顶点的数量为:"+count);
    }
}

广度优先搜索：

对一个连通图进行遍历的算法。思想：从顶点V0开始，把所有连通顶点都遍历一次，没有找到解，就再从通顶点中找出一个递归以上过程
这里的QueueTest是自己复习时写的队列类，大家可以用jdk自带的Queue类

package GraphTest;

import LinearTest.QueueTest;

/**
 * 广度优先遍历
 * 原理：对一个顶点的所有连通结点进行遍历，之后再深入每一个连通的顶点递归该过程
 */
public class BreadthFirstSearch {
    private boolean[] marked;
    //记录右多少个顶点与s顶点相通
    private int count;
    //用来保存待搜索邻接表的点
    /*回顾树的层次遍历，使用一个辅助队列，弹出一个元素，
    就把该元素的子结点放入队列*/
    private QueueTest<Integer> waitSearch;
    Integer next;
    //构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相通顶点
    public BreadthFirstSearch(Graph G,int v){
        //创建一个数组，标记图中顶点是否已被搜索
        marked = new boolean[G.V()];
        //创建辅助队列
        waitSearch = new QueueTest<Integer>();
        //调用广度优先搜索算法
        waitSearch.enqueue(v);
        bfs(G,v);
    }

    /**
     * bfs算法需要做的事
     * 1、把当前顶点设置为已搜索，放入队列，弹出
     * 2、遍历出当前顶点邻接表中所有相邻的顶点
     * 3、放入辅助队列中
     * 4、弹出元素重复以上过程
     */
    private void bfs(Graph G,int v){
        marked[v] = true;
        boolean flag = false;
        //判断队列是否存在数据
        while (!waitSearch.isEmpty()){
            Integer wait = waitSearch.dequeue();
            for (Integer w : G.adj(wait)) {
                if (!flag && !marked[w]){
                    next = w;
                    flag = true;
                }
                if(!marked[w]){
                    //递归调用广度优先搜索算法，可以将每个连通的顶点放入辅助队列中
                    marked[w] = true;
                    waitSearch.enqueue(w);
                }
            }
            count++;
            bfs(G,next);
        }
    }
    public int count(){
        return count;
    }
    //判断w顶点与s顶点是否相通
    public boolean marked(int w){
        return marked[w];
    }
    public static void main(String[] args) {
        //准备Graph对象
        Graph G = new Graph(13);
        G.addEdge(0,5);
        G.addEdge(0,1);
        G.addEdge(0,2);
        G.addEdge(0,6);
        G.addEdge(5,3);
        G.addEdge(5,4);
        G.addEdge(3,4);
        G.addEdge(4,6);

        G.addEdge(7,8);

        G.addEdge(9,11);
        G.addEdge(9,10);
        G.addEdge(9,12);
        G.addEdge(11,12);
        //准备广度优先搜索对象
        BreadthFirstSearch search = new BreadthFirstSearch(G, 0);
        //测试与某个顶点相通的顶点数量
        int count = search.count();
        System.out.println("与起点0相通的顶点的数量为:"+count);
        //测试某个顶点与起点是否相同
        boolean marked1 = search.marked(5);
        System.out.println("顶点5和顶点0是否相通："+marked1);
        boolean marked2 = search.marked(7);
        System.out.println("顶点7和顶点0是否相通："+marked2);
    }
}