课程：《数据结构与面向对象程序设计》
班级： 2023
姓名：肖衍豪
学号：20202310
实验教师：王志强
实验日期：2021年12月16日
必修/选修： 必修

1.实验内容

(1) 初始化：根据屏幕提示（例如：输入1为无向图，输入2为有向图）初始化无向图和有向图（可用邻接矩阵，也可用邻接表），图需要自己定义（顶点个数、边个数，建议先在草稿纸上画出图，然后再输入顶点和边数）（2分）
(2) 图的遍历：完成有向图和无向图的遍历（深度和广度优先遍历）（4分）
(3) 完成有向图的拓扑排序，并输出拓扑排序序列或者输出该图存在环（3分）
(4) 完成无向图的最小生成树（Prim算法或Kruscal算法均可），并输出（3分）
(5) 完成有向图的单源最短路径求解（迪杰斯特拉算法）（3分）

PS：本题12分。目前没有明确指明图的顶点和连通边，如果雷同或抄袭，本次实验0分。
实验报告中要根据所编写的代码解释图的相关算法

2. 实验过程及结果

(1) 初始化：根据屏幕提示（例如：输入1为无向图，输入2为有向图）初始化无向图和有向图（可用邻接矩阵，也可用邻接表），图需要自己定义（顶点个数、边个数，建议先在草稿纸上画出图，然后再输入顶点和边数）（2分）

代码实现：

public class MatrixUDG
{
    private char[] mVexs;       // 顶点集合
    private int[][] mMatrix;    // 邻接矩阵
}
    public MatrixUDG(char[] vexs, char[][] edges)
    {

        // 初始化"顶点数"和"边数"
        int vlen = vexs.length;
        int elen = edges.length;

        // 初始化"顶点"
        mVexs = new char[vlen];
        for (int i = 0; i <5; i++)
            mVexs[i] = vexs[i];

        // 初始化"边"
        mMatrix = new int[vlen][vlen];
        for (int i = 0; i < 8; i++)
        {
            // 读取边的起始顶点和结束顶点
            int p1 = getPosition(edges[i][0]);
            int p2 = getPosition(edges[i][1]);

            mMatrix[p1][p2] = 1;
            mMatrix[p2][p1] = 1;
        }
    }//邻接矩阵实现无向图

    public ListDG() {

        // 输入"顶点数"和"边数"
        System.out.printf("input vertex number: ");
        int vlen = readInt();
        System.out.printf("input edge number: ");
        int elen = readInt();
        if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
            System.out.printf("input error: invalid parameters!\n");
            return ;
        }

        // 初始化"顶点"
        mVexs = new VNode[vlen];
        for (int i = 0; i < mVexs.length; i++) {
            System.out.printf("vertex(%d): ", i);
            mVexs[i] = new VNode();
            mVexs[i].data = readChar();
            mVexs[i].firstEdge = null;
        }

        // 初始化"边"
        //mMatrix = new int[vlen][vlen];
        for (int i = 0; i < 3; i++) {
            // 读取边的起始顶点和结束顶点
            System.out.printf("edge(%d):", i);
            char c1 = readChar();
            char c2 = readChar();
            int p1 = getPosition(c1);
            int p2 = getPosition(c2);
            // 初始化node1
            ENode node1 = new ENode();
            node1.ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == null)
                mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
        }
    }//邻接表实现有向图

(2) 图的遍历：完成有向图和无向图的遍历（深度和广度优先遍历）（4分）

代码实现：

// 图的接口
public interface Graph
{

    public int V();
    public int E();
    public void addEdge( int v , int w );
    boolean hasEdge( int v , int w );
    void show();
    public Iterable<Integer> adj(int v);
}
// 图的深度优先遍历
    void dfs( int v )
    {

        visited[v] = true;
        //维护联通分量
        id[v] = ccount;
        //遍历邻边的所有元素
        for( int i: G.adj(v) ){
            if( !visited[i] ){
                dfs(i);
            }
        }
    }
    private int[][] edges = {
            { 0, 1, 0, 0, 0, 1, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0, 1, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 0, 1 },
            { 0, 0, 1, 0, 1, 0, 1, 1, 1 }, { 0, 0, 0, 1, 0, 1, 0, 1, 0 }, { 1, 0, 0, 0, 1, 0, 1, 0, 0 },
            { 0, 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 0, 0, 1, 1, 0, 1, 0, 0 }, { 0, 1, 1, 1, 0, 0, 0, 0, 0 }
    };
    // 图的广度遍历操作
    void BFSTraverse() {
        flag = new boolean[number];
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < number; i++) {
            if (flag[i] == false) {
                flag[i] = true;
                System.out.print(vertexs[i] + " ");
                queue.add(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    for (int k = 0; k < number; k++) {
                        if (edges[j][k] == 1 && flag[k] == false) {
                            flag[k] = true;
                            System.out.print(vertexs[k] + " ");
                            queue.add(k);
                        }
                    }
                }
            }
        }
    }

(3) 完成有向图的拓扑排序，并输出拓扑排序序列或者输出该图存在环（3分）
代码实现：

import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/*
 * 用来实现拓扑排序的有向无环图
 */
public class DirectedGraph {

    private class Vertex{
        private String vertexLabel;// 顶点标识
        private List<Edge> adjEdges;
        private int inDegree;// 该顶点的入度

        public Vertex(String verTtexLabel) {
            this.vertexLabel = verTtexLabel;
            inDegree = 0;
            adjEdges = new LinkedList<Edge>();
        }
    }

    private class Edge {
        private Vertex endVertex;

        // private double weight;
        public Edge(Vertex endVertex) {
            this.endVertex = endVertex;
        }
    }

    private Map<String, Vertex> directedGraph;

    public DirectedGraph(String graphContent) {
        directedGraph = new LinkedHashMap<String, DirectedGraph.Vertex>();
        buildGraph(graphContent);
    }

    private void buildGraph(String graphContent) {
        String[] lines = graphContent.split("\n");
        Vertex startNode, endNode;
        String startNodeLabel, endNodeLabel;
        Edge e;
        for (int i = 0; i < lines.length; i++) {
            String[] nodesInfo = lines[i].split(",");
            startNodeLabel = nodesInfo[1];
            endNodeLabel = nodesInfo[2];
            startNode = directedGraph.get(startNodeLabel);
            if(startNode == null){
                startNode = new Vertex(startNodeLabel);
                directedGraph.put(startNodeLabel, startNode);
            }
            endNode = directedGraph.get(endNodeLabel);
            if(endNode == null){
                endNode = new Vertex(endNodeLabel);
                directedGraph.put(endNodeLabel, endNode);
            }

            e = new Edge(endNode);//每读入一行代表一条边
            startNode.adjEdges.add(e);//每读入一行数据,起始顶点添加一条边
            endNode.inDegree++;//每读入一行数据,终止顶点入度加1
        }
    }

    public void topoSort() throws Exception{
        int count = 0;

        Queue<Vertex> queue = new LinkedList<>();// 拓扑排序中用到的栈,也可用队列.
        //扫描所有的顶点,将入度为0的顶点入队列
        Collection<Vertex> vertexs = directedGraph.values();
        for (Vertex vertex : vertexs)
            if(vertex.inDegree == 0)
                queue.offer(vertex);

        while(!queue.isEmpty()){
            Vertex v = queue.poll();
            System.out.print(v.vertexLabel + " ");
            count++;
            for (Edge e : v.adjEdges)
                if(--e.endVertex.inDegree == 0)
                    queue.offer(e.endVertex);
        }
        if(count != directedGraph.size())
            throw new Exception("Graph has circle");
    }
}

 

(4) 完成无向图的最小生成树（Prim算法或Kruscal算法均可），并输出（3分）
代码实现：

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

 

/**

 * 普里姆（Prim）算法

 */

public class Prim {

 

    public static void main(String[] args) {

        int[][] arr = new int[][]{

                {-1, 4, 0, 0, 0, 0, 0, 8, 0},

                {0, -1, 8, 0, 0, 0, 0, 11, 0},

                {0, 0, -1, 7, 0, 4, 0, 0, 2},

                {0, 0, 0, -1, 9, 14, 0, 0, 0},

                {0, 0, 0, 0, -1, 10, 0, 0, 0},

                {0, 0, 0, 0, 0, -1, 2, 0, 0},

                {0, 0, 0, 0, 0, 0, -1, 1, 6},

                {0, 0, 0, 0, 0, 0, 0, -1, 7},

                {0, 0, 0, 0, 0, 0, 0, 0, -1}

        };

        List<Integer> list = new ArrayList<>();

        //先将0放置在list中

        list.add(0);

        int begin = 0, end = 0, weight;

        int[] parent = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {

            parent[i] = -1;

        }

        while (list.size() < arr.length) {

            weight = Integer.MAX_VALUE;

            for (Integer row : list) {

                for (int i = 0; i < arr.length; i++) {

                    if (!list.contains(i)) {

                        if (i >= row + 1) {

                            if (arr[row][i] > 0 && arr[row][i] < weight) {

                                begin = row;

                                end = i;

                                weight = arr[row][i];

                            }

                        } else if (i <= row - 1) {

                            //我这里只用了上三角矩阵，所以这里需要画蛇添足写这一部分

                            if (arr[i][row] > 0 && arr[i][row] < weight) {

                                begin = row;

                                end = i;

                                weight = arr[i][row];

                            }

                        }

                    }

                }

            }

            list.add(end);

            parent[end] = begin;

        }

        System.out.println(Arrays.toString(parent));

    }

}

(5) 完成有向图的单源最短路径求解（迪杰斯特拉算法）（3分）

代码实现：

public class DijstraAlgorithm {
    //不能设置为Integer.MAX_VALUE，否则两个Integer.MAX_VALUE相加会溢出导致出现负权
    public static int MaxValue = 100000;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入顶点数和边数:");
        //顶点数
        int vertex = input.nextInt();
        //边数
        int edge = input.nextInt();

        int[][] matrix = new int[vertex][vertex];
        //初始化邻接矩阵
        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                matrix[i][j] = MaxValue;
            }
        }
        for (int i = 0; i < edge; i++) {
            System.out.println("请输入第" + (i + 1) + "条边与其权值:");
            int source = input.nextInt();
            int target = input.nextInt();
            int weight = input.nextInt();
            matrix[source][target] = weight;
        }

        //单源最短路径，源点
        int source = input.nextInt();
        //调用dijstra算法计算最短路径
        dijstra(matrix, source);
    }

    public static void dijstra(int[][] matrix, int source) {
        //最短路径长度
        int[] shortest = new int[matrix.length];
        //判断该点的最短路径是否求出
        int[] visited = new int[matrix.length];
        //存储输出路径
        String[] path = new String[matrix.length];

        //初始化输出路径
        for (int i = 0; i < matrix.length; i++) {
            path[i] = new String(source + "->" + i);
        }

        //初始化源节点
        shortest[source] = 0;
        visited[source] = 1;

        for (int i = 1; i < matrix.length; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;

            for (int j = 0; j < matrix.length; j++) {
                //已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
                if (visited[j] == 0 && matrix[source][j] < min) {
                    min = matrix[source][j];
                    index = j;
                }
            }

            //更新最短路径
            shortest[index] = min;
            visited[index] = 1;

            //更新从index跳到其它节点的较短路径
            for (int m = 0; m < matrix.length; m++) {
                if (visited[m] == 0 && matrix[source][index] + matrix[index][m] < matrix[source][m]) {
                    matrix[source][m] = matrix[source][index] + matrix[index][m];
                    path[m] = path[index] + "->" + m;
                }
            }

        }

        //打印最短路径
        for (int i = 0; i < matrix.length; i++) {
            if (i != source) {
                if (shortest[i] == MaxValue) {
                    System.out.println(source + "到" + i + "不可达");
                } else {
                    System.out.println(source + "到" + i + "的最短路径为：" + path[i] + "，最短距离是：" + shortest[i]);
                }
            }
        }
    }