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

燕山楠的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. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注