@ysner
2021-11-14T21:09:07.000000Z
字数 6687
阅读 825
数据结构
当边数固定时,使顶点数最少的方案是构建完全图。设题中完全图有个点,则有,解得。
又因为该图为非连通图,故至少需添个度数为的顶点以符合题意。
综上,该图至少有个顶点。
本题可以用数学归纳法来证明。
当时,由于为一个邻接矩阵,故只可能为或。当时,表示图中没有从顶点到顶点的路径,即路径数目为;当时,表示图中有条从顶点到顶点的路径,即路径数目为,此时结论成立。
假设当时结论成立,则的值为从顶点到顶点的路径长度为的数目。
当时,由,故有(表示图中的顶点数)。进一步推理可得,这其中表示从顶点到顶点再直接到顶点的路径长度为的数目。因此,考虑到所有的顶点后,即表示从顶点到顶点的路径长度为的总数目,故结论成立。
本题代码为T3代码。核心代码为Dijstra函数。
第1行输入n(图中节点数),m(图中边数)。
第2至m+1行输入u(边起点),v(边终点),w(边权)。
注意:第一个输出结果对应本问题的答案。
import java.util.*;
class hw5_3
{
static class Dij
{
final int N=100;
class Node
{
int i,dis;
public Node(int ii,int diss){i=ii;dis=diss;}
}
Edge[] h=new Edge[N];
class Edge
{
int to,w;
Edge nxt;
}
public void add(int u,int v,int w)
//建边函数
{
Edge e=new Edge();
e.to=v;e.nxt=h[u];e.w=w;h[u]=e;
}
int[] dis=new int[N];
boolean[] vis=new boolean[N];
int[] pre=new int[N];//保存最短路径前驱结点,方便最后输出最短路径
PriorityQueue<Node> Q=new PriorityQueue<>((a,b)->a.dis-b.dis);
//优先队列:将点按目前到顶点0的距离从小到大排序
int n,m;
public void Build()
//初始化+读入图的相关信息并建边
{
Arrays.fill(dis,Integer.MAX_VALUE);
Arrays.fill(vis,false);
Scanner in=new Scanner(System.in);
n=in.nextInt();m=in.nextInt();
while(m-->0)
{
int u=in.nextInt(),v=in.nextInt(),w=in.nextInt();
add(u,v,w);
}
}
public void Dijstra()
//实现改进后的迪杰斯特拉算法
{
int u;
dis[0]=0;Q.offer(new Node(0,0));
while(!Q.isEmpty())
{
u=Q.poll().i;
if(vis[u]) continue;
vis[u]=true;
for(Edge i=h[u];i!=null;i=i.nxt)
{
int v=i.to;
if(dis[u]+i.w<dis[v])
{
dis[v]=dis[u]+i.w;
pre[v]=u;
if(!vis[v]) Q.offer(new Node(v,dis[v]));
}
}
}
}
public void print()
//输出顶点0到其它顶点的最短路径及其长度
{
for(int i=1;i<n;i++)
{
System.out.print(i+":len="+dis[i]+" 0");
int u=i;
Stack<Integer> S=new Stack<>();
while(u>0)
{
S.push(u);
u=pre[u];
}
while(!S.isEmpty())
{
System.out.print("->"+S.pop());
}
System.out.println();
}
}
}
public static void main(String[] args)
{
Dij G=new Dij();//新建一个类对象记得new啊!!!
G.Build();
G.Dijstra();
G.print();
}
}
本题代码为T4代码。核心代码为Search和DFS函数。
第1行输入n(图中节点数),m(图中边数)。
第2至m+1行输入u(边的一个端点),v(边的另一个端点)。
import java.util.*;
class hw5_4
{
static class Dij
{
final int N=100;
class Edge
{
int to;
Edge nxt;
}
public void add(int u,int v)
//建边函数
{
Edge e=new Edge();
e.to=v;e.nxt=h[u];h[u]=e;
}
Edge[] h=new Edge[N];
boolean[] vis=new boolean[N];//标记对应点是否被访问过
int n,m,ans=0;
public void Build()
//初始化+依据输入的边信息建无向边
{
Arrays.fill(vis,false);
Scanner in=new Scanner(System.in);
n=in.nextInt();m=in.nextInt();
while(m-->0)
{
int u=in.nextInt(),v=in.nextInt();
add(u,v);add(v,u);//无向边=两个不同方向的有向边
}
}
public void Search()
//进入每一个连通分量并统计答案
{
for(int i=0;i<n;i++)
if(vis[i]==false)//该顶点没被标记,说明这个顶点在一个新的连通分量里
{
DFS(i);
ans++;
}
System.out.println(ans);
}
public void DFS(int u)
//把一个连通分量内的所有顶点均遍历一遍并标记
{
vis[u]=true;
for(Edge i=h[u];i!=null;i=i.nxt)
{
int v=i.to;
if(vis[v]==true) continue;
DFS(v);
}
}
}
public static void main(String[] args)
{
Dij G=new Dij();
G.Build();
G.Search();
}
}
本题代码为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。
import java.util.*;
class hw5_5
{
static class Graph
{
final int N=100;
int e[][]=new int[N][N];
boolean vis[]=new boolean[N];//vis保存顶点是否已入队,已入队为true,未入队为false
int n,S,T;
Queue<Integer> Q=new LinkedList<>();
public void Build()
//初始化+读入邻接矩阵
{
Arrays.fill(vis,false);
Scanner in=new Scanner(System.in);
n=in.nextInt();S=in.nextInt();T=in.nextInt();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
e[i][j]=in.nextInt();
}
public boolean Check()
//以S为起点进行BFS遍历,将遍历到的新结点入队。
//如果遍历完后T入过队,就说明顶点i到顶点j的路径存在。
{
Q.offer(S);vis[S]=true;//入队了就记录下来,以防重复入队
while(!Q.isEmpty())
{
int u=Q.poll();
if(u==T) return true;//发现T入了队就直接返回,节省时间
for(int i=0;i<n;i++)
if(e[u][i]>0&&!vis[i])
{
Q.offer(i);
vis[i]=true;
}
}
return false;
}
}
public static void main(String[] args)
{
Graph G=new Graph();
G.Build();
System.out.println(G.Check());
}
}
本题代码为T6代码。核心代码为Check函数。
第1行输入n(图中节点数),m(图中边数)。
第2到m+1行中每行输入u(有向边起点),v(有向边终点)。
第m+2行输入S(起点,即顶点i),T(终点,即顶点j),X(不可访问点,即顶点k)
若有符合题目要求的路径,则输出true,否则输出false。
import java.util.*;
class hw5_6
{
static class Graph
{
final int N=100;
class Edge
{
int to;
Edge nxt;
}
Edge[] h=new Edge[N];
public void add(int u,int v)
//建边函数
{
Edge e=new Edge();
e.to=v;e.nxt=h[u];h[u]=e;
}
int n,m,S,T,X;
boolean[] vis=new boolean[N];//vis表示顶点是否已入过队
public void Build()
//初始化vis数组+读入建边信息
{
Arrays.fill(vis,false);
Scanner in=new Scanner(System.in);
n=in.nextInt();m=in.nextInt();
while(m-->0)
{
int u=in.nextInt(),v=in.nextInt();
add(u,v);
}
S=in.nextInt();T=in.nextInt();X=in.nextInt();
vis[X]=true;
//通过此操作,顶点k无法入队且无法以顶点k为起点搜索,相当于顶点k是不可访问的,符合题意。
}
Queue<Integer> Q=new LinkedList<>();
public boolean Check()
//以S为起点进行BFS遍历,将遍历到的新结点入队。
//如果遍历完后T入过队,就说明顶点i到顶点j的路径存在。
{
Q.offer(S);vis[S]=true;
while(!Q.isEmpty())
{
int u=Q.poll();
for(Edge i=h[u];i!=null;i=i.nxt)
{
int v=i.to;
if(!vis[v])
{
if(v==T) return true;//发现T入了队就直接返回,节省时间(放这位置比上一题更快)
Q.offer(v);
vis[v]=true;
}
}
}
return false;
}
}
public static void main(String[] args)
{
Graph G=new Graph();
G.Build();
System.out.println(G.Check());
}
}
本题代码为T7代码。核心代码为Search和DFS函数。
第1行输入n(图中节点数)。
接下来输入一个n*n的矩阵E,E[i][j]表示顶点i和顶点j之间边的长度(约定:若顶点i与顶点j不相邻,则E[i][j]=-1;E[i][i]=0)。
若该有向图的根不存在,则输出-1。
import java.util.*;
class hw5_7
{
static class Graph
{
final int N=100;
int e[][]=new int[N][N];
boolean vis[]=new boolean[N];
int n,tot;
public void Build()
//读入矩阵的函数
{
Scanner in=new Scanner(System.in);
n=in.nextInt();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
e[i][j]=in.nextInt();
}
public void DFS(int u)
//进行深度优先遍历的函数
{
vis[u]=true;
tot++;
for(int i=0;i<n;i++)
if(e[u][i]>0&&!vis[i])//根据约定,顶点u到顶点i有边当且仅当e[u][i]>0
DFS(i);
}
public int Search()
//枚举所有结点,分别尝试将其作为遍历起点,看是否能遍历全图。一旦有遍历全图的就可以返回值了。
{
for(int i=0;i<n;i++)
{
Arrays.fill(vis,false);//重置结点的访问状态(已访问/未访问)
tot=0;//统计遍历到的结点个数
DFS(i);
if(tot==n) return i;
}
return -1;//图中没有根则返回-1
}
}
public static void main(String[] args)
{
Graph G=new Graph();
G.Build();
System.out.println(G.Search());
}
}
本题代码为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。
import java.util.*;
class hw5_8
{
static class Graph
{
final int N=100;
int e[][]=new int[N][N];
boolean vis[]=new boolean[N];
int n,S,T;
int[] dis=new int[N];
public void Build()
//读入矩阵的函数
{
Scanner in=new Scanner(System.in);
n=in.nextInt();S=in.nextInt();T=in.nextInt();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
e[i][j]=in.nextInt();
}
class Node
{
int dis,u;
public Node(int diss,int uu){dis=diss;u=uu;}
}
PriorityQueue<Node> Q=new PriorityQueue<>((a,b)->a.dis-b.dis);
//优先队列:将点按目前到顶点s的距离从小到大排序
public int Dijstra()
//实现改进后的迪杰斯特拉算法,以顶点s为源,返回dis[t]即可。
{
Arrays.fill(dis,Integer.MAX_VALUE);
Arrays.fill(vis,false);
Q.offer(new Node(0,S));
dis[S]=0;
while(!Q.isEmpty())
{
int u=Q.poll().u;
if(vis[u]) continue;
vis[u]=true;
for(int i=0;i<n;i++)
if(dis[u]+e[u][i]<dis[i]&&e[u][i]>0)//e[u][i]>0:首先矩阵里存的0和负数就不是边权,再者迪杰斯特拉算法也不能在有负权的图里跑
{
dis[i]=dis[u]+e[u][i];
if(!vis[i]) Q.offer(new Node(dis[i],i));
}
}
return (dis[T]==2147483647)?-1:dis[T];//dis[T]=inf表示路径不存在,按约定返回-1
}
}
public static void main(String[] args)
{
Graph G=new Graph();
G.Build();
System.out.println(G.Dijstra());
}
}