具有n个顶点且每一对不同的顶点之间都有一条边的无向图被称为()。
A、无向完全图
B、无向连通图
C、无向强连通图
D、无向树图
A、无向完全图
B、无向连通图
C、无向强连通图
D、无向树图
A.n+l
B.n
C.
D.n-1
●试题六
阅读以下说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数;a为带权邻接矩阵,用于存储有向网中每一对顶点间弧上的权值;c为二维数组,存储有向网中每一对顶点间的最短路径长度;kay为二维数组,存储最短路径,kay[i][j]=k表示顶点i 到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有:
Input():输入有向网的顶点数、各条弧及权值,建立带权领接矩阵a。若顶点i到顶点j有弧,则a[i][j]取弧上的权值,否则a[i][j]的值取NoEdge。
AllPairs();用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。
OutShortestPath(int i,int j):计算顶点i到顶点j的最短路径。
outputPath(int i,int j):输出顶点i到顶点j的最短路径上的顶点。
Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1,C2,…,Cn,其中C0是已知的带权邻接矩阵,a,Ck(i,j)(0≤i,j<n)表示从顶点i到顶点j的中间顶点序号不大于k 的最短路径长度。如果i到j的路径没有中间顶点,则对于0≤k<n,有Ck(i,j)=C0(i,j)=a[i][j]。递推地产生C1,C2,…,Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探,直到为全部路径都找遍了所有可能成为最短路径上的中间顶点,所有的最短路径也就全部求出,算法就此结束。
【C++代码】
#include<iostream.h>
#define NoEdge 10000 //当两个顶点之间没有边相连时,在邻接矩阵中用NoEdge表示
void Make2DArray(int * * &x,int rows,int cols);
class AdjacencyWDigraph{
private
int n;//有向网中的顶点数目
int**a;//存储顶点间弧上的权值
int**c;//存储计算出的最短路径长度
int**kay;//存储求出的最短路径
pubic:
int Vertices()const {return n;}
void AllPairs();
void Input();//输入有向网的顶点数、各条弧及权值,建立邻接矩阵a
void OutShortestPath(int i,int j);//计算顶点i到j的最短路径(试卷中未列出)
~AdjacencyWDigraph();//析构函数(试卷中未列出)
private:
void outputPath(int i,int j);
};
void AdjacencyWDigraph::AllPairs()
{int i,j,k,t1,t2,t3;
for(i=1;i<=n;k++)
for(j=1;j<=n;++j)
{c[i][j]= (1) ;kay[i][j]=0;}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++){
if(i==k) continue;
t1=c[i][k];
for(j=1;j<=n;j++){
if(j==k||j==i)continue;
t2=c[k][j];t3=c[i][j];
if(t1!=NoEdge && t2!=NoEdge &&(t3==NoEdge||t1+t2<t3))
{c[i][j]= (2) ;kay[i][j]= (3) ;}
}//for
}//for
}
void AdjacencyWDigraph:: outputPath(int i,int j)
{//输出顶点i到j的最短路径上的顶点
if(i==j)return;
if(kay[i][j]==0)cout<<j<<′′;
else { outputPath(i, (4) ); outputPath((5) );}
}
void Adjacency WDigraph::Input()
{int i,j,u,v,w,E;
cout<<″输入网中顶点个数:″;cin>>n;
cout<<″输入网中弧的个数:″;cin>>E;
Make2DArray(a,n+1,n+1);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)a[i][j]=NoEdge;
for(i=1;i<=n;i++)a[i][i]=0;
Make2DArray(c,n+1,n+1);
Make2DArray(kay,n+1,n+1);
for(i=1;i<=E;i++){
cout<<″输入弧的信息(起点终点权值):″;cin>>u>>v>>w;a[u][v]=w;
}
}
void Make2DArray(int**&x,int rows,int cols)
{int i,j;
x=new int*[rows+1];
for(i=0;i<rows+1;i++)x[i]=new int [cols+1];
for(i=1;i<=rows;i++)
for(j=1;j<=cols;j++=x[i][j]=0;
}
一个具有n(n>0)个顶点的连通无向图至少有(33)条边。
A.n+1
B.n
C.n/2
D.n-1
一个具有N个顶点的无向图最多有(47)条边。
A.N×(N-1)/2
B.N×(N-1)
C.N×(N+1)/2
D.N2
A.N
B.E
C.2E
D.N+E
(60)
A.N
B.E
C.2E
D.N+E
具有n个顶点e条边的无向图的邻接表,其边表结点总数为(50)。
A.n
B.e
C.2e
D.n+e
A.分治 B.贪心 C.动态规划 D.回溯 A.若网较稠密,则Prim算法更好 B.两个算法得到的最小生成树是一样的 C.Prim算法比Kruscal算法效率更高 D.Kruscal算法比Prim算法效率更高
● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构 (矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧),则该矩阵的元素数目为 (60) ,其中非零元素数目为 (61) 。