2002312 2021-2022-1 实验九 《图》实验报告

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

1.实验内容

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

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

2.实验过程及结果

(1）初始化

 1 public class Graph {
 2     Vertex[] VertexArray;
 3     Edge[] EdgeArray;
 4     int edgenum,vertexnum;
 5     int adjmatrix[][];
 6     public void CreateGraph(int num)
 7     {
 8         Scanner scan = new Scanner(System.in);
 9         System.out.println("请输入顶点数与边数");
10         vertexnum=scan.nextInt();
11         edgenum=scan.nextInt();
12         adjmatrix=new int[vertexnum][vertexnum];
13         VertexArray=new Vertex[vertexnum];
14         EdgeArray=new Edge[edgenum];
15         System.out.println("请输入顶点：");
16         for(int i=0;i<vertexnum;i++){
17             VertexArray[i]=new Vertex(scan.next());
18         }
19         for(int i=0;i<edgenum;i++){
20             String a,b;
21             Vertex from,to;
22             int c;
23             System.out.println("请输入边的两顶点与权值：");
24             from=SearchVertex(scan.next());
25             to=SearchVertex(scan.next());
26             c= scan.nextInt();
27             EdgeArray[i]=new Edge(from,to,c);
28             adjmatrix[SearchIndex(from.name)][SearchIndex(to.name)]=c;
29             from.outdegree++;
30             to.indegree++;
31             if(num==2){
32                 adjmatrix[SearchIndex(to.name)][SearchIndex(from.name)]=c;
33                 from.outdegree--;
34                 to.indegree--;
35             }
36         }
37     }
38 
39     public int SearchIndex(String name){
40         for(int i=0;i<VertexArray.length;i++)
41         {
42             if(VertexArray[i].name.equals(name))
43                 return i;
44         }
45         return -1;
46     }
47 
48     public Vertex SearchVertex(String name)
49     {
50         for(int i=0;i<VertexArray.length;i++){
51             if(VertexArray[i].name.equals(name))
52                 return VertexArray[i];
53         }
54         return null;
55     }

(2) 图的遍历：

 1 public String BreadthFirstTraversal(String first){
 2         Vertex temp;
 3         String result="";
 4         Queue<Vertex> queue=new LinkedList();
 5         queue.offer(SearchVertex(first));
 6         SearchVertex(first).Mark();
 7         while(!queue.isEmpty()){
 8             temp=queue.poll();
 9             result+=temp.name;
10             for(int i=0;i<vertexnum;i++){
11                 if(adjmatrix[SearchIndex(temp.name)][i]!=0&&!VertexArray[i].isMark) {
12                     queue.offer(VertexArray[i]);
13                     VertexArray[i].Mark();
14                 }
15             }
16         }
17         for(int i=0;i<vertexnum;i++){ VertexArray[i].wipe(); }
18         return result;
19     }
20     public String DepthTraversal(String first){
21         String result=first;
22         SearchVertex(first).Mark();
23         for(int i=0;i<vertexnum;i++){
24             if(adjmatrix[SearchIndex(first)][i]!=0&&!VertexArray[i].isMark) {
25                 result += DepthTraversal(VertexArray[i].name);
26             }
27         }
28         return result;
29     }
30     public String DepthFirstTraversal(String first){
31         String a=DepthTraversal(first);
32         for(int i=0;i<vertexnum;i++){ VertexArray[i].wipe(); }
33         return a;
34     }

 (3) 有向图的拓扑排序

 1 public String topology(){
 2         String a="";
 3         Stack<Vertex> stack=new Stack<Vertex>();
 4         int indegreearray[]=new int[vertexnum];
 5         boolean ismark[]=new boolean[vertexnum];
 6         for(int i=0;i< VertexArray.length;i++) {
 7             indegreearray[i] = VertexArray[i].indegree;
 8             ismark[i]=false;
 9             if(indegreearray[i]==0){stack.push(VertexArray[i]);ismark[i]=true;}
10         }
11         while(!stack.isEmpty()) {
12             Vertex temp = stack.pop();
13             a += temp.name + " ";
14             for (int i = 0; i < vertexnum; i++) {
15                 if (adjmatrix[SearchIndex(temp.name)][i]!=0) {
16                     indegreearray[i]--;
17                     for (int j = 0; j < vertexnum; j++) {
18                         if (indegreearray[j] == 0 && !ismark[j]) { stack.push(VertexArray[j]);ismark[j] = true; }
19                     }
20                 }
21             }
22         }
23         for(int i=0;i<vertexnum;i++)
24             if(!ismark[i])return "该图存在环";
25         return a;
26     }

(4) 完成无向图的最小生成树

 1 public Graph spanningTree(){
 2         Graph spanning =new Graph();
 3         Scanner scan=new Scanner(System.in);
 4         Edge []an=new Edge[vertexnum-1];
 5         int anweight[]=new int[vertexnum-1];
 6         String a="";
 7         spanning.VertexArray=this.VertexArray;
 8         spanning.EdgeArray=new Edge[vertexnum-1];
 9         spanning.edgenum=vertexnum-1;
10         spanning.vertexnum=vertexnum;
11         System.out.print("请输入起点：");
12         Vertex as= SearchVertex(scan.next());
13         boolean appear=false;
14         for(int i=0;i<vertexnum-1;i++){
15             an[i]=new Edge();
16             an[i].from=as;
17             if(VertexArray[i]==as)appear=true;
18             if(appear)an[i].to=VertexArray[i+1];
19             else an[i].to=VertexArray[i];
20             for(int j=0;j<edgenum;j++){
21                 if(EdgeArray[j].from==an[i].from&&EdgeArray[j].to==an[i].to) {an[i].weight=EdgeArray[j].weight;break;}
22                 if(EdgeArray[j].from==an[i].to&&EdgeArray[j].to==an[i].from){an[i].weight=EdgeArray[j].weight;break;}
23             }
24         }
25         for(int r=0,min=0,max=0;r<vertexnum-1;r++){
26             for(int j=0;j<vertexnum-1;j++){
27                 if(an[j].weight<an[min].weight&&an[j].weight>0&&anweight[j]>=0){min=j;}
28                 if(an[j].weight>an[max].weight&&an[j].weight>0&&anweight[j]>=0){max=j;}
29             }
30             anweight[min]=-1;
31             spanning.EdgeArray[r]=an[min];
32             a+=an[min].from.name+" "+an[min].to.name+" "+an[min].weight+"\n";
33             for(int t=0;t<vertexnum-1;t++){
34                 for(int j=0;j<edgenum;j++){
35                     if(EdgeArray[j].from==an[min].to&&EdgeArray[j].to==an[t].to&&anweight[t]>=0) {
36                         anweight[t]=EdgeArray[j].weight;
37                         break;}
38                     if(EdgeArray[j].from==an[t].to&&EdgeArray[j].to==an[min].to&&anweight[t]>=0){
39                         anweight[t]=EdgeArray[j].weight;
40                         break;}
41                 }
42                 if(anweight[t]<an[t].weight&&anweight[t]>0){an[t].from=an[min].to;an[t].weight=anweight[t];}
43                 if(an[t].weight==-1){an[t].from=an[min].to;an[t].weight=anweight[t];}
44             }
45             min=max;
46         }
47         System.out.println(a);
48         return spanning;
49     }

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

 1 public void Dijkstra(){
 2         Scanner scan=new Scanner(System.in);
 3         String a="",b="";
 4         System.out.print("请输入起点");
 5         b=scan.next();
 6         Vertex begin=SearchVertex(b);
 7         Path ShortestEdge[]=new Path[vertexnum];
 8         Path shortest[]=new Path[vertexnum-1];
 9         for(int i=0,j=0;i<vertexnum;i++){
10             if(VertexArray[i]!=begin) {
11                 ShortestEdge[j]=new Path(begin,VertexArray[i],1000000000);j++;
12             }
13         }
14         for(int i = 0,k=0; i<vertexnum-1;i++){
15             Path min=new Path();
16             Path con=new Path(3);
17             for(int j=0;j<vertexnum;j++){
18                 int tempweight=adjmatrix[SearchIndex(begin.name)][j];
19                 if(SearchIndex(begin.name)!=j) {
20                     if (ShortestEdge[k].weight!= con.weight) {
21                         Path temp1 =new Path(ShortestEdge[k]), temp2 ;
22                         if(i>0) temp2 =new Path(shortest[i-1]);
23                         else temp2=ShortestEdge[k];
24                         if (tempweight != 0 &&temp2.Add(begin, ShortestEdge[k].end, tempweight).weight < temp1.weight){
25                             ShortestEdge[k]=temp2;
26                         }
27                         else {
28                             ShortestEdge[k] = temp1;
29                         }
30                         if (ShortestEdge[k].weight < min.weight) min = ShortestEdge[k];
31                     }
32                     k++;
33                 }
34             }
35             ShortestEdge[vertexnum-1]=new Path(min);
36             shortest[i]=new Path(min);
37             a+=b+" "+shortest[i].end.name+" "+shortest[i].weight+"\n";
38             begin=min.end;
39             min.weight=con.weight;
40             k=0;
41         }
42         System.out.println(a);
43     }

3.实验过程中遇到的问题和解决过程

- 问题1：在输入无向图时老是报错，进行调试也没能解决
- 问题1解决方案：仔细查找，发现是自己的输入方式出现了问题，调整后，显示成功。

 ## 其他（感悟、思考等）

　　感觉这次图的实验好难啊，好多算法自己还不是很清楚，感觉还得多花时间去搞懂。

## 参考资料

-  [《Java程序设计与数据结构教程（第二版）》](https://book.douban.com/subject/26851579/)

-  [《Java程序设计与数据结构教程（第二版）》学习指导](http://www.cnblogs.com/rocedu/p/5182332.html)
-  ...