[关闭]
@ysner 2021-11-14T21:09:07.000000Z 字数 6687 阅读 825

燕山楠的homework 4

数据结构


T1

当边数固定时,使顶点数最少的方案是构建完全图。设题中完全图有个点,则有,解得
又因为该图为非连通图,故至少需添个度数为的顶点以符合题意。
综上,该图至少有个顶点。

T2

本题可以用数学归纳法来证明。
时,由于为一个邻接矩阵,故只可能为。当时,表示图中没有从顶点到顶点的路径,即路径数目为;当时,表示图中有条从顶点到顶点的路径,即路径数目为,此时结论成立。
假设当时结论成立,则的值为从顶点到顶点的路径长度为的数目。
时,由,故有表示图中的顶点数)。进一步推理可得,这其中表示从顶点到顶点再直接到顶点的路径长度为的数目。因此,考虑到所有的顶点后,即表示从顶点到顶点的路径长度为的总数目,故结论成立。

T3

本题代码为T3代码。核心代码为Dijstra函数。
第1行输入n(图中节点数),m(图中边数)。
第2至m+1行输入u(边起点),v(边终点),w(边权)。
注意:第一个输出结果对应本问题的答案。

  1. import java.util.*;
  2. class hw5_3
  3. {
  4. static class Dij
  5. {
  6. final int N=100;
  7. class Node
  8. {
  9. int i,dis;
  10. public Node(int ii,int diss){i=ii;dis=diss;}
  11. }
  12. Edge[] h=new Edge[N];
  13. class Edge
  14. {
  15. int to,w;
  16. Edge nxt;
  17. }
  18. public void add(int u,int v,int w)
  19. //建边函数
  20. {
  21. Edge e=new Edge();
  22. e.to=v;e.nxt=h[u];e.w=w;h[u]=e;
  23. }
  24. int[] dis=new int[N];
  25. boolean[] vis=new boolean[N];
  26. int[] pre=new int[N];//保存最短路径前驱结点,方便最后输出最短路径
  27. PriorityQueue<Node> Q=new PriorityQueue<>((a,b)->a.dis-b.dis);
  28. //优先队列:将点按目前到顶点0的距离从小到大排序
  29. int n,m;
  30. public void Build()
  31. //初始化+读入图的相关信息并建边
  32. {
  33. Arrays.fill(dis,Integer.MAX_VALUE);
  34. Arrays.fill(vis,false);
  35. Scanner in=new Scanner(System.in);
  36. n=in.nextInt();m=in.nextInt();
  37. while(m-->0)
  38. {
  39. int u=in.nextInt(),v=in.nextInt(),w=in.nextInt();
  40. add(u,v,w);
  41. }
  42. }
  43. public void Dijstra()
  44. //实现改进后的迪杰斯特拉算法
  45. {
  46. int u;
  47. dis[0]=0;Q.offer(new Node(0,0));
  48. while(!Q.isEmpty())
  49. {
  50. u=Q.poll().i;
  51. if(vis[u]) continue;
  52. vis[u]=true;
  53. for(Edge i=h[u];i!=null;i=i.nxt)
  54. {
  55. int v=i.to;
  56. if(dis[u]+i.w<dis[v])
  57. {
  58. dis[v]=dis[u]+i.w;
  59. pre[v]=u;
  60. if(!vis[v]) Q.offer(new Node(v,dis[v]));
  61. }
  62. }
  63. }
  64. }
  65. public void print()
  66. //输出顶点0到其它顶点的最短路径及其长度
  67. {
  68. for(int i=1;i<n;i++)
  69. {
  70. System.out.print(i+":len="+dis[i]+" 0");
  71. int u=i;
  72. Stack<Integer> S=new Stack<>();
  73. while(u>0)
  74. {
  75. S.push(u);
  76. u=pre[u];
  77. }
  78. while(!S.isEmpty())
  79. {
  80. System.out.print("->"+S.pop());
  81. }
  82. System.out.println();
  83. }
  84. }
  85. }
  86. public static void main(String[] args)
  87. {
  88. Dij G=new Dij();//新建一个类对象记得new啊!!!
  89. G.Build();
  90. G.Dijstra();
  91. G.print();
  92. }
  93. }

T4

本题代码为T4代码。核心代码为Search和DFS函数。
第1行输入n(图中节点数),m(图中边数)。
第2至m+1行输入u(边的一个端点),v(边的另一个端点)。

  1. import java.util.*;
  2. class hw5_4
  3. {
  4. static class Dij
  5. {
  6. final int N=100;
  7. class Edge
  8. {
  9. int to;
  10. Edge nxt;
  11. }
  12. public void add(int u,int v)
  13. //建边函数
  14. {
  15. Edge e=new Edge();
  16. e.to=v;e.nxt=h[u];h[u]=e;
  17. }
  18. Edge[] h=new Edge[N];
  19. boolean[] vis=new boolean[N];//标记对应点是否被访问过
  20. int n,m,ans=0;
  21. public void Build()
  22. //初始化+依据输入的边信息建无向边
  23. {
  24. Arrays.fill(vis,false);
  25. Scanner in=new Scanner(System.in);
  26. n=in.nextInt();m=in.nextInt();
  27. while(m-->0)
  28. {
  29. int u=in.nextInt(),v=in.nextInt();
  30. add(u,v);add(v,u);//无向边=两个不同方向的有向边
  31. }
  32. }
  33. public void Search()
  34. //进入每一个连通分量并统计答案
  35. {
  36. for(int i=0;i<n;i++)
  37. if(vis[i]==false)//该顶点没被标记,说明这个顶点在一个新的连通分量里
  38. {
  39. DFS(i);
  40. ans++;
  41. }
  42. System.out.println(ans);
  43. }
  44. public void DFS(int u)
  45. //把一个连通分量内的所有顶点均遍历一遍并标记
  46. {
  47. vis[u]=true;
  48. for(Edge i=h[u];i!=null;i=i.nxt)
  49. {
  50. int v=i.to;
  51. if(vis[v]==true) continue;
  52. DFS(v);
  53. }
  54. }
  55. }
  56. public static void main(String[] args)
  57. {
  58. Dij G=new Dij();
  59. G.Build();
  60. G.Search();
  61. }
  62. }

T5

本题代码为T5代码。核心代码为Check函数。
第1行输入n(图中节点数),S(起点,即顶点i),T(终点,即顶点j)。
接下来输入一个n*n的矩阵E,E[i][j]表示顶点i和顶点j之间边的长度(约定:若顶点i与顶点j不相邻,则E[i][j]=-1(否则输入一个矩阵要打好多2147483647呜呜);E[i][i]=0)。
若顶点i到顶点j有路径,则输出true,否则输出false。

  1. import java.util.*;
  2. class hw5_5
  3. {
  4. static class Graph
  5. {
  6. final int N=100;
  7. int e[][]=new int[N][N];
  8. boolean vis[]=new boolean[N];//vis保存顶点是否已入队,已入队为true,未入队为false
  9. int n,S,T;
  10. Queue<Integer> Q=new LinkedList<>();
  11. public void Build()
  12. //初始化+读入邻接矩阵
  13. {
  14. Arrays.fill(vis,false);
  15. Scanner in=new Scanner(System.in);
  16. n=in.nextInt();S=in.nextInt();T=in.nextInt();
  17. for(int i=0;i<n;i++)
  18. for(int j=0;j<n;j++)
  19. e[i][j]=in.nextInt();
  20. }
  21. public boolean Check()
  22. //以S为起点进行BFS遍历,将遍历到的新结点入队。
  23. //如果遍历完后T入过队,就说明顶点i到顶点j的路径存在。
  24. {
  25. Q.offer(S);vis[S]=true;//入队了就记录下来,以防重复入队
  26. while(!Q.isEmpty())
  27. {
  28. int u=Q.poll();
  29. if(u==T) return true;//发现T入了队就直接返回,节省时间
  30. for(int i=0;i<n;i++)
  31. if(e[u][i]>0&&!vis[i])
  32. {
  33. Q.offer(i);
  34. vis[i]=true;
  35. }
  36. }
  37. return false;
  38. }
  39. }
  40. public static void main(String[] args)
  41. {
  42. Graph G=new Graph();
  43. G.Build();
  44. System.out.println(G.Check());
  45. }
  46. }

T6

本题代码为T6代码。核心代码为Check函数。
第1行输入n(图中节点数),m(图中边数)。
第2到m+1行中每行输入u(有向边起点),v(有向边终点)。
第m+2行输入S(起点,即顶点i),T(终点,即顶点j),X(不可访问点,即顶点k)
若有符合题目要求的路径,则输出true,否则输出false。

  1. import java.util.*;
  2. class hw5_6
  3. {
  4. static class Graph
  5. {
  6. final int N=100;
  7. class Edge
  8. {
  9. int to;
  10. Edge nxt;
  11. }
  12. Edge[] h=new Edge[N];
  13. public void add(int u,int v)
  14. //建边函数
  15. {
  16. Edge e=new Edge();
  17. e.to=v;e.nxt=h[u];h[u]=e;
  18. }
  19. int n,m,S,T,X;
  20. boolean[] vis=new boolean[N];//vis表示顶点是否已入过队
  21. public void Build()
  22. //初始化vis数组+读入建边信息
  23. {
  24. Arrays.fill(vis,false);
  25. Scanner in=new Scanner(System.in);
  26. n=in.nextInt();m=in.nextInt();
  27. while(m-->0)
  28. {
  29. int u=in.nextInt(),v=in.nextInt();
  30. add(u,v);
  31. }
  32. S=in.nextInt();T=in.nextInt();X=in.nextInt();
  33. vis[X]=true;
  34. //通过此操作,顶点k无法入队且无法以顶点k为起点搜索,相当于顶点k是不可访问的,符合题意。
  35. }
  36. Queue<Integer> Q=new LinkedList<>();
  37. public boolean Check()
  38. //以S为起点进行BFS遍历,将遍历到的新结点入队。
  39. //如果遍历完后T入过队,就说明顶点i到顶点j的路径存在。
  40. {
  41. Q.offer(S);vis[S]=true;
  42. while(!Q.isEmpty())
  43. {
  44. int u=Q.poll();
  45. for(Edge i=h[u];i!=null;i=i.nxt)
  46. {
  47. int v=i.to;
  48. if(!vis[v])
  49. {
  50. if(v==T) return true;//发现T入了队就直接返回,节省时间(放这位置比上一题更快)
  51. Q.offer(v);
  52. vis[v]=true;
  53. }
  54. }
  55. }
  56. return false;
  57. }
  58. }
  59. public static void main(String[] args)
  60. {
  61. Graph G=new Graph();
  62. G.Build();
  63. System.out.println(G.Check());
  64. }
  65. }

T7

本题代码为T7代码。核心代码为Search和DFS函数。
第1行输入n(图中节点数)。
接下来输入一个n*n的矩阵E,E[i][j]表示顶点i和顶点j之间边的长度(约定:若顶点i与顶点j不相邻,则E[i][j]=-1;E[i][i]=0)。
若该有向图的根不存在,则输出-1。

  1. import java.util.*;
  2. class hw5_7
  3. {
  4. static class Graph
  5. {
  6. final int N=100;
  7. int e[][]=new int[N][N];
  8. boolean vis[]=new boolean[N];
  9. int n,tot;
  10. public void Build()
  11. //读入矩阵的函数
  12. {
  13. Scanner in=new Scanner(System.in);
  14. n=in.nextInt();
  15. for(int i=0;i<n;i++)
  16. for(int j=0;j<n;j++)
  17. e[i][j]=in.nextInt();
  18. }
  19. public void DFS(int u)
  20. //进行深度优先遍历的函数
  21. {
  22. vis[u]=true;
  23. tot++;
  24. for(int i=0;i<n;i++)
  25. if(e[u][i]>0&&!vis[i])//根据约定,顶点u到顶点i有边当且仅当e[u][i]>0
  26. DFS(i);
  27. }
  28. public int Search()
  29. //枚举所有结点,分别尝试将其作为遍历起点,看是否能遍历全图。一旦有遍历全图的就可以返回值了。
  30. {
  31. for(int i=0;i<n;i++)
  32. {
  33. Arrays.fill(vis,false);//重置结点的访问状态(已访问/未访问)
  34. tot=0;//统计遍历到的结点个数
  35. DFS(i);
  36. if(tot==n) return i;
  37. }
  38. return -1;//图中没有根则返回-1
  39. }
  40. }
  41. public static void main(String[] args)
  42. {
  43. Graph G=new Graph();
  44. G.Build();
  45. System.out.println(G.Search());
  46. }
  47. }

T8

本题代码为T8代码。核心代码为Dijstra函数。
第1行输入n(图中节点数),s,t。
接下来输入一个n*n的矩阵E,E[i][j]表示顶点i和顶点j之间边的长度(约定:若顶点i与顶点j不相邻,则E[i][j]=-1;E[i][i]=0)。
若从顶点s到顶点t的路径不存在,则输出-1。

  1. import java.util.*;
  2. class hw5_8
  3. {
  4. static class Graph
  5. {
  6. final int N=100;
  7. int e[][]=new int[N][N];
  8. boolean vis[]=new boolean[N];
  9. int n,S,T;
  10. int[] dis=new int[N];
  11. public void Build()
  12. //读入矩阵的函数
  13. {
  14. Scanner in=new Scanner(System.in);
  15. n=in.nextInt();S=in.nextInt();T=in.nextInt();
  16. for(int i=0;i<n;i++)
  17. for(int j=0;j<n;j++)
  18. e[i][j]=in.nextInt();
  19. }
  20. class Node
  21. {
  22. int dis,u;
  23. public Node(int diss,int uu){dis=diss;u=uu;}
  24. }
  25. PriorityQueue<Node> Q=new PriorityQueue<>((a,b)->a.dis-b.dis);
  26. //优先队列:将点按目前到顶点s的距离从小到大排序
  27. public int Dijstra()
  28. //实现改进后的迪杰斯特拉算法,以顶点s为源,返回dis[t]即可。
  29. {
  30. Arrays.fill(dis,Integer.MAX_VALUE);
  31. Arrays.fill(vis,false);
  32. Q.offer(new Node(0,S));
  33. dis[S]=0;
  34. while(!Q.isEmpty())
  35. {
  36. int u=Q.poll().u;
  37. if(vis[u]) continue;
  38. vis[u]=true;
  39. for(int i=0;i<n;i++)
  40. if(dis[u]+e[u][i]<dis[i]&&e[u][i]>0)//e[u][i]>0:首先矩阵里存的0和负数就不是边权,再者迪杰斯特拉算法也不能在有负权的图里跑
  41. {
  42. dis[i]=dis[u]+e[u][i];
  43. if(!vis[i]) Q.offer(new Node(dis[i],i));
  44. }
  45. }
  46. return (dis[T]==2147483647)?-1:dis[T];//dis[T]=inf表示路径不存在,按约定返回-1
  47. }
  48. }
  49. public static void main(String[] args)
  50. {
  51. Graph G=new Graph();
  52. G.Build();
  53. System.out.println(G.Dijstra());
  54. }
  55. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注