课程：《程序设计与数据结构》
班级： 2023
姓名： 陈欢
学号：20202320
实验教师：王志强
实验日期：2021年12月23日
必修/选修： 必修

##1.实验内容

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

##2.实验过程及结果

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

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

 　　如上图所示：其中邻接矩阵表示的有向图是（由于作图原因，其中顶点0直接与顶点5相连通）：

　　　　无向图的遍历：

　　完整代码如下：

public void Depth(int i){
    //标记第i个节点以遍历
    visited[i]=true;
    //打印当前已经遍历的节点
    visit(i);
    //遍历邻接矩阵中第i个节点的直接连通节点
    for(int j=0;j<nodenum;j++){
        if(Adjacency[i][j]==1&&visited[j]==false){
            Depth(j);
        }
    }
}
//深度优先遍历
public void dfs(){
    //初始化节点访问标记
    for(int i=0;i<visited.length;i++){
        visited[i]=false;
    }
    //从没有被遍历的节点开始深度优先遍历
    for(int i=0;i<nodenum;i++){
        if(visited[i]==false){
            Depth(i);
        }
    }
    System.out.println();
}
//广度遍历
public void bfs(){
    //初始化节点访问标记
    for(int i=0;i<visited.length;i++){
        visited[i]=false;
    }
    Queue<Integer> queue=new LinkedList<Integer>();
    for(int i=0;i<nodenum;i++){
        if(visited[i]==false){
            visited[i]=true;
            //打印当前已经遍历的节点
            visit(i);
            //添加到队列里
            queue.add(i);
            //只要队列不为空
            while(!queue.isEmpty()){
                //出队节点，也就是这一层的节点
                int k=queue.poll();
                //遍历所有未被访问的邻接节点，放入队列
                for(int j=0;j<nodenum;j++){
                    //也就是访问这一层剩下的未被访问的节点
                    if(Adjacency[k][j]==1&&visited[j]==false){
                        visited[j]=true;
                        visit(j);
                        queue.add(j);
                    }
                }
            }
        }
    }
    System.out.println();
}

　　（3）完成有向图的拓扑排序，并输出拓扑排序序列或者输出该图存在环（3分）

　　　　有向图的拓扑排序如实验内容（1）所示。

　　　　完整代码如下：

　　　　public void Topo(int i){    int sum=0;

    public void Topo(int i){
　　itn sum=0;
　　for(int j=0;j<nodenum;j++){
        sum=sum+rear[j][i];//行
    }
    if(sum==0){//第i个节点没有前驱
        visited[i]=true;
        visit(i);
        for(int k=0;k<nodenum;k++){
            rear[i][k]=0;//列
        }
    }

}
public void Topological(){
    for(int i=0;i<visited.length;i++){
        visited[i]=false;
    }
    int sum0=0;
    do {
        int i;
        for (i = 0; i < nodenum; i++) {
            if (visited[i] == false) {
                Topo(i);
            }
        }
        if(i==nodenum&&visited[i-1]==false) {
            System.out.println("该图存在环！");
            sum0=nodenum;
        }else {
            for (int j = 0; j < nodenum; j++) {//判断是否全部遍历
                if (visited[j] == true) {
                    sum0++;
                } else {
                    sum0 = 0;
                    break;
                }
            }
        }
    }while(sum0!=nodenum);
    System.out.println();
}

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

 使用的是Prime 算法，完整代码如下：

public void Prime(){
    for(int i=0;i<nodenum;i++){
        visited[i]=false;
    }
    for(int i=0;i<nodenum;i++){
        if(visited[i]==false){
            Primehelp(i);
        }
    }
    rear=Adjacency;
}//生成最小生成树
public void Primehelp(int i) {//无向图使用
    int key = 0;
    int a = 0, b = 0;
    if (visited[i] == false) {
        for (int j = 0; j < nodenum; j++) {
            if (rear[i][j] > key)
                key = rear[i][j];//第i行的最大值
        }
            for (int j = 0; j < nodenum; j++) {
                if (rear[i][j] < key && rear[i][j] != 0) {
                    key = rear[i][j];//第i行的最小值
                    a = i;
                    b = j;
                }
            }
            for (int num = 0; num < nodenum; num++) {
                if (visited[num] == true) {
                    for (int p = 0; p < nodenum; p++) {
                        if (rear[num][p] < key && rear[num][p] != 0) {
                            key = rear[num][p];
                            a = num;
                            b = p;
                        }
                    }
                }
            }
        }
        if (visited[b] == false) {
            rear[a][b] = 0;
            rear[b][a] = 0;
            visited[i] = true;
            visit(i);
            System.out.print("(" + key + ")");
            Primehelp(b);
        } else {
            rear[a][b] = 0;
            rear[b][a] = 0;
            int sum = 0;
            for (int ni = 0; ni < nodenum; ni++) {
                if (visited[ni] == true) {
                    sum++;
                }
            }
            if (sum != nodenum)
                if (sum == nodenum - 1) {
                    for (int ni = 0; ni < nodenum; ni++) {
                        if (visited[ni] == false)
                            System.out.println(vertices[ni]);
                    }
                } else
                    Primehelp(i);
    }
}
(5) 完成有向图的单源最短路径求解（迪杰斯特拉算法）（3分）
暂未完成

##3.实验中遇到的问题和解决方法
--问题一：进行拓扑排序时总是不能够在最后输出正确的邻接矩阵。
--解决方法：给邻接矩阵做一个“分身”，在进行拓扑排序时，只对“分身”进行操作，而要输出的邻接矩阵并不做改变。
　　　　　　同时该“分身”不能够定义为rear=Adjacency，因为这样定义出的“分身”矩阵和Adjacency矩阵是同一个“存储空间”（应该是这么叫吧）。
--问题二：递归是难以退出。
--解决方法：通过调试，找出能够退出的唯一条件，这个条件需要做到所谓“当且仅当”（maybe）。
##4.实验心得与体会
　　首先是后悔没有早点动手，到了考试周才匆匆忙忙的做。
　　其次是递归的运用，在这次的实验中，递归的重要作用比之前的更加突出，递归非常考验人的逻辑（我觉得）。
　　最后，最后一次实验值得好好……
##5.参考资料
--数据结构和算法动态可视化 (Chinese) - VisuAlgo
--(3条消息) JAVA实现图的深度优先遍历._今天又是充满希望的一天-CSDN博客_java实现深度优先搜索
--《Java程序设计教程（第九版）》
--《Java软件结构与数据结构（第四版）》