数据结构 --有向图

2021/7/9 23:39:39

本文主要是介绍数据结构 --有向图,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、概述

有向图是一副具有方向性的图,是由一组顶点和一组有方向的边组成的,每条方向的边都连着一对有序的顶点

二、邻接矩阵实现(todo)

2.1 API设计

2.2 实现

2.3 测试

三、邻接表实现

3.1 API设计

类名Digraph
构造方法Digraph(int V):创建一个包含V个顶点但不包含边的有向图
成员方法1.public int V():获取图中顶点的数量
2.public int E():获取图中边的数量
3.public void addEdge(int v,int w):向有向图中添加一条边 v->w
4.public Queue adj(int v):获取由v指出的边所连接的所有顶点
5.private Digraph reverse():该图的反向图
成员变量1.private final int V: 记录顶点数量
2.private int E: 记录边数量
3.private Queue[] adj: 邻接表

3.2 实现

/**
 * 有向图
 * @date 2021/7/9 16:54
 */
public class Digraph {
    // 记录顶点数量
    private final int V;
    // 记录边数量
    private int E;
    // 邻接表
    private Queue<Integer>[] adj;

    public Digraph(int V) {
        //初始化顶点数量
        this.V = V;
        //初始化边的数量
        this.E = 0;
        //初始化邻接表
        this.adj = new Queue[V];
        //初始化邻接表中的空队列
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Queue<Integer>();
        }
    }

    // 获取顶点数目
    public int V() {
        return V;
    }

    // 获取边的数目
    public int E() {
        return E;
    }

    // 向有向图中添加一条边v->w
    public void addEdge(int v, int w) {
        // 只需要让顶点w出现在顶点v的邻接表中,因为边是有方向的,最终,顶点v的邻接表中存储的相邻顶点的含义是: v->其他顶点
        adj[v].enqueue(w);
        E++;
    }

    // 获取由v指出的边所连接的所有顶点
    public Queue<Integer> adj(int v) {
        return adj[v];
    }

    // 该图的反向图
    private Digraph reverse() {
        // 创建有向图对象
        Digraph r = new Digraph(V);

        // 遍历原图的每一个节点
        for (int v = 0; v < V; v++) {
            // 获取由该顶点v指出的所有边
            for (Integer w : adj[v]) { // 原图中表示的是由顶点v->w的边
                r.addEdge(w,v); // w->v
            }
        }

        return r;
    }
}

3.3 测试

    // 测试有向图数据结构
    public static void test01() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
        Digraph digraph = new Digraph(10);
        digraph.addEdge(1,2);
        digraph.addEdge(1,3);
        digraph.addEdge(4,1);
        System.out.print("由顶点1指出的边所连接的所有顶点:");
        for (Integer w : digraph.adj(1)) {
            System.out.print(w+"顶点 ");
        }
        System.out.println();

        // 反向该图
        Class<Digraph> digraphClass = Digraph.class;
        Method method = digraphClass.getDeclaredMethod("reverse", null);
        method.setAccessible(true);
        digraph = (Digraph)method.invoke(digraph);
        System.out.println("----------------------反向该图后---------------------");
        System.out.print("由顶点1指出的边所连接的所有顶点:");
        for (Integer w : digraph.adj(1)) {
            System.out.print(w+"顶点 ");
        }
    }

四、检测有向图中的环

4.1 API设计

类名DirectedCycle
构造方法DirectedCycle(Digraph G):创建一个检测环对象,检测图G中是否有环
成员方法1.private void dfs(Digraph G,int v):基于深度优先搜索,检测图G中是否有环
2.public boolean hasCycle():判断图中是否有环
成员变量1.private boolean[] marked: 索引代表顶点,值表示当前顶点是否已经被搜索
2.private boolean hasCycle: 记录图中是否有环
3.private boolean[] onStack:索引代表顶点,使用栈的思想,记录当前顶点有没有已经处于正在搜索的有向路径上

4.2 实现

/**
 * 检测有向图中的环
 *
 * @date 2021/7/9 20:41
 */
public class DirectedCycle {
    //索引代表顶点,值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录图中是否有环
    private boolean hasCycle;
    //索引代表顶点,使用栈的思想,记录当前顶点有没有已经处于正在搜索的有向路径上
    private boolean[] onStack;

    //创建一个检测环对象,检测图G中是否有环
    public DirectedCycle(Digraph G) {
        //创建一个和图的顶点数一样大小的marked数组
        marked = new boolean[G.V()];
        //创建一个和图的顶点数一样大小的onStack数组
        onStack = new boolean[G.V()];
        //默认没有环
        this.hasCycle = false;
        //遍历搜索图中的每一个顶点
        for (int v = 0; v < G.V(); v++) {
            //如果当前顶点没有搜索过,则搜索
            if (!marked[v]) {
                dfs(G, v);
            }
        }
    }

    //基于深度优先搜索,检测图G中是否有环
    private void dfs(Digraph G, int v) {
        //把当前顶点标记为已搜索
        marked[v] = true;
        //让当前顶点进栈
        onStack[v] = true;
        //遍历v顶点的邻接表,得到每一个顶点w
        for (Integer w : G.adj(v)) {
            //如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点
            if (!marked[w]) {
                dfs(G, w);
            }
            //如果顶点w已经被搜索过,则查看顶点w是否在栈中,如果在,则证明图中有环,修改hasCycle标 记,结束循环
            if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }
        //当前顶点已经搜索完毕,让当前顶点出栈
        onStack[v]=false;
    }

    //判断w顶点与s顶点是否相通
    public boolean hasCycle() {
        return hasCycle;
    }
}

4.5 测试

public class DirectedCycleTest {
    public static void main(String[] args) {
        Digraph digraph = new Digraph(10);
        digraph.addEdge(1,2);
        digraph.addEdge(2,3);
        digraph.addEdge(3,1);

        DirectedCycle directedCycle = new DirectedCycle(digraph);
        System.out.println("是否有环:" + directedCycle.hasCycle());
    }
}

五、基于深度优先的顶点排序

5.1 API设计

类名DepthFirstOrder
构造方法DepthFirstOrder(Digraph G):创建一个顶点排序对象,生成顶点线性序列;
成员方法1.private void dfs(Digraph G,int v):基于深度优先搜索,生成顶点线性序列
2.public Stack reversePost():获取顶点线性序列
成员变量1.private boolean[] marked: 索引代表顶点,值表示当前顶点是否已经被搜索
2.private Stack reversePost: 使用栈,存储顶点序列

5.2 实现

/**
 * 基于深度优先的顶点排序
 *
 * @date 2021/7/9 21:15
 */
public class DepthFirstOrder {
    // 索引代表顶点,值代表当前顶点是否已经被搜索
    private boolean[] marked;
    // 使用栈,存储顶点序列
    private Stack<Integer> reversePost;

    // 创建一个检测环对象,检测图G中是否有环
    public DepthFirstOrder(Digraph G) {
        // 初始化mrked数组
        marked = new boolean[G.V()];

        // 初始化reversePost栈
        reversePost = new Stack<Integer>();

        // 遍历图中的每一个顶点,让每一个顶点作为入口,完成一次深度优先搜索
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v);
            }
        }
    }

    // 基于深度优先搜索,检测图G中是否有环
    private void dfs(Digraph G, int v) {
        // 标记当前v已经被搜索
        marked[v] = true;

        // 通过循环深度搜索顶点v
        for (Integer w : G.adj(v)) {
            //如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点
            if (!marked[w]) {
                dfs(G, w);
            }
        }

        // 让顶点v进栈
        reversePost.push(v);
    }

    // 获取顶点线性序列
    public Stack<Integer> reversePost() {
        return reversePost;
    }
}

5.3 测试

public class DepthFirstOrderTest {
    public static void main(String[] args) {
        Digraph digraph = new Digraph(10);
        digraph.addEdge(1,2);
        digraph.addEdge(1,3);

        DepthFirstOrder depthFirstOrder = new DepthFirstOrder(digraph);
        Stack<Integer> reversePost = depthFirstOrder.reversePost();
        System.out.println("顶点排序序列:");
        for (Integer integer : reversePost) {
            System.out.print(integer + " ");
        }
    }
}

六、拓扑排序

6.1 API设计

类名TopoLogical
构造方法TopoLogical(Digraph G):构造拓扑排序对象
成员方法1.public boolean isCycle():判断图G是否有环
2.public Stack order():获取拓扑排序的所有顶点
成员变量1.private Stack order: 顶点的拓扑排序

6.2 实现

/**
 * 拓扑排序
 * @date 2021/7/9 22:34
 */
public class TopoLogical {
    // 顶点的拓扑排序
    private Stack<Integer> order;

    // 构造拓扑排序对象
    public TopoLogical(Digraph G) {
        //创建检测环对象,检测图G中是否有环
        DirectedCycle dCycle = new DirectedCycle(G);
        if (!dCycle.hasCycle()) {
            //如果没有环,创建顶点排序对象,进行顶点排序
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
            order = depthFirstOrder.reversePost();
        }
    }

    // 判断图G是否有环
    public boolean isCycle() {
        return order == null;
    }

    // 获取拓扑排序的所有顶点
    public Stack<Integer> order() {
        return order;
    }
}

6.3 测试

public class TopoLogicalTest {
    public static void main(String[] args) {
        Digraph digraph = new Digraph(10);
        digraph.addEdge(1,2);
        digraph.addEdge(1,3);

        TopoLogical topoLogical = new TopoLogical(digraph);
        Stack<Integer> order = topoLogical.order();

        System.out.print("拓扑排序:");
        for (Integer w : order) {
            System.out.print(w+" ");
        }
    }
}


这篇关于数据结构 --有向图的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程