graph——图生成器

摘要：图生成器，根据给定的二维数据，生成对应的有向图、无向图。在学习图数据结构和相关算法的过程中，能够快速生成Graph对象用于测试，需要配合特定的图数据结构使用。

图生成器

给定一个二维数组，二维数组的每一行有如下三种情况

• 该行的长度为1，则代表图中的1个顶点
• 该行的长度为2，则代表图中的两个顶点及顶点之间的一条无权值边
• 该行的长度为2，则代表图中的两个顶点及顶点之间的一条带权值边

生成图的原始数据

package com.shg.graph;

/**
 * @author: shg
 * @create: 2022-05-18 1:00 上午
 */
public class Data {
    public static final Object[][] BFS_01 = {
            {"A", "B"}, {"A", "F"},
            {"B", "C"}, {"B", "I"}, {"B", "G"},
            {"C", "I"}, {"C", "D"},
            {"D", "I"}, {"D", "G"}, {"D", "E"}, {"D", "H"},
            {"E", "H"}, {"E", "F"},
            {"F", "G"},
            {"G", "H"},
    };

    public static final Object[][] BFS_02 = {
            {0, 1}, {0, 4},
            {1, 2},
            {2, 0}, {2, 4}, {2, 5},
            {3, 1},
            {4, 6}, {4, 7},
            {5, 3}, {5, 7},
            {6, 2}, {6, 7}
    };

    public static final Object[][] BFS_03 = {
            {0, 2}, {0, 3},
            {1, 2}, {1, 3}, {1, 6},
            {2, 4},
            {3, 7},
            {4, 6},
            {5, 6},
            {6, 7}
    };

    public static final Object[][] BFS_04 = {
            {1, 2}, {1, 3}, {1, 5},
            {2, 0},
            {3, 5},
            {5, 6}, {5, 7},
            {6, 2},
            {7, 6}
    };

    public static final Object[][] DFS_01 = {
            {0, 1},
            {1, 3}, {1, 5}, {1, 6}, {1, 2},
            {2, 4},
            {3, 7}
    };

    public static final Object[][] DFS_02 = {
            {"a", "b"}, {"a", "e"},
            {"b", "e"},
            {"c", "b"},
            {"d", "a"},
            {"e", "c"}, {"e", "f"},
            {"f", "c"}
    };

    public static final Object[][] TOPO = {
            {0, 2},
            {1, 0},
            {2, 5}, {2, 6},
            {3, 1}, {3, 5}, {3, 7},
            {5, 7},
            {6, 4},
            {7, 6}
    };

    public static final Object[][] NO_WEIGHT2 = {
            {0, 3},
            {1, 3}, {1, 6},
            {2, 1},
            {3, 5},
            {6, 2}, {6, 5},
            {4, 7}
    };

    public static final Object[][] NO_WEIGHT3 = {
            {0, 1}, {0, 2},
            {1, 2}, {1, 5},
            {2, 4}, {2, 5},
            {5, 6}, {7, 6},
            {3}
    };

    public static final Object[][] MST_01 = {
            {0, 2, 2}, {0, 4, 7},
            {1, 2, 3}, {1, 5, 1}, {1, 6, 7},
            {2, 4, 4}, {2, 5, 3}, {2, 6, 6},
            {3, 7, 9},
            {4, 6, 8},
            {5, 6, 4}, {5, 7, 5}
    };

    public static final Object[][] MST_02 = {
            {"A", "B", 17}, {"A", "F", 1}, {"A", "E", 16},
            {"B", "C", 6}, {"B", "D", 5}, {"B", "F", 11},
            {"C", "D", 10},
            {"D", "E", 4}, {"D", "F", 14},
            {"E", "F", 33}
    };

    public static final Object[][] WEIGHT3 = {
            {"广州", "佛山", 100}, {"广州", "珠海", 200}, {"广州", "肇庆", 200},
            {"佛山", "珠海", 50}, {"佛山", "深圳", 150},
            {"肇庆", "珠海", 100}, {"肇庆", "南宁", 150},
            {"珠海", "南宁", 350}, {"珠海", "深圳", 100},
            {"南宁", "香港", 500}, {"南宁", "深圳", 400},
            {"深圳", "香港", 150}
    };

    public static final Object[][] SP = {
            {"A", "B", 10}, {"A", "D", 30}, {"A", "E", 100},
            {"B", "C", 50},
            {"C", "E", 10},
            {"D", "C", 20}, {"D", "E", 60}
    };

    public static final Object[][] BF_SP = {
            {"A", "B", 10}, {"A", "E", 8},
            {"B", "C", 8}, {"B", "E", -5},
            {"D", "C", 2}, {"D", "F", 6},
            {"E", "D", 7}, {"E", "F", 3}
    };

    public static final Object[][] WEIGHT5 = {
            {0, 14, 1}, {0, 4, 8},
            {1, 2, 9},
            {2, 3, 6}, {2, 5, 9},
            {3, 17, 1}, {3, 10, 4},
            {4, 5, 2}, {4, 8, 2},
            {5, 6, 6}, {5, 8, 1}, {5, 9, 4},
            {6, 9, 8},
            {7, 11, 4},
            {8, 9, 1}, {8, 11, 2}, {8, 12, 7},
            {9, 10, 7}, {9, 13, 4},
            {10, 13, 2},
            {11, 12, 7}, {11, 15, 4},
            {12, 13, 2}, {12, 16, 2},
            {13, 16, 7},
            {15, 16, 7}, {15, 17, 7},
            {16, 17, 2}
    };

    public static final Object[][] NEGATIVE_WEIGHT1 = {
            {"A", "B", -1}, {"A", "C", 4},
            {"B", "C", 3}, {"B", "D", 2}, {"B", "E", 2},
            {"D", "B", 1}, {"D", "C", 5},
            {"E", "D", -3}
    };

    /**
     * 有负权环
     */
    public static final Object[][] NEGATIVE_WEIGHT2 = {
            {0, 1, 1},
            {1, 2, 7},
            {1, 0, -2}
    };
}

图生成器

package com.shg.graph;

/**
 * @author: shg
 * @create: 2022-05-18 1:01 上午
 */
public class ListGraphGenerator<K, V> {

    /**
     * 根据数据生成有向图或无向图
     * @param data 生成图的原始数据
     * @param directed 生成无向图还是有向图
     * @return
     */
    public ListGraph<K, V> generateListGraph(Object[][] data, boolean directed) {
        ListGraph<K, V> graph = new ListGraph<>();

        for (Object[] row : data) {
            if (row.length == 1) {
                graph.addVertex((K) row[0]);
            } else if (row.length == 2) {
                graph.addEdge((K) row[0], (K) row[1]);
                if (!directed) {
                    graph.addEdge((K) row[1], (K) row[0]);
                }
            } else if (row.length == 3) {
                graph.addEdge((K) row[0], (K) row[1], (V) row[2]);
                if (!directed) {
                    graph.addEdge((K) row[1], (K) row[0], (V) row[2]);
                }
            }
        }
        return graph;
    }

    /**
     * 生成有向图
     * @param data
     * @return
     */
    public ListGraph<K, V> generateListDigraph(Object[][] data) {
        return generateListGraph(data, true);
    }

    /**
     * 生成无向图
     * @param data
     * @return
     */
    public ListGraph<K, V> generateListUnDigraph(Object[][] data) {
        return generateListGraph(data, false);
    }

}

图生成器的使用

public void testGenerator() {
    ListGraphGenerator<String, Integer> generator = new ListGraphGenerator<>();
    ListGraph<String, Integer> graph = generator.generateListUnDigraph(Data.BFS_01);
    graph.bfs("A");

    ListGraphGenerator<Integer, Integer> generator1 = new ListGraphGenerator<>();
    ListGraph<Integer, Integer> graph1 = generator1.generateListDigraph(Data.BFS_02);
    graph1.bfs(0);
}