数据结构的一些问题~1、连通图含义?2、n个顶点的无向图、有向图,最少、最多边数?3、n个顶点的非连通图,最多边数?4、n个顶点有向图,顶点的度最小?最大?5、有向图顶点入度、出度关系?6、邻

Answer 1

1、连通图
图内任意两个顶点均有可达路径,其中有向图的话,所有边都看作无向.满足这一性质的图为连通图
2、由于没说一定连通,所以有向图与无向图最少边数均为0
最多的话,有向图为n*(n-1),无向图为n*(n-1)/2
3、无向图,理论最多边数为(n^2-n)/4,其中点的数目平均分布在两个连通分量
假定一边为x,则边数为x*(x-1)/2,另一边就是(n-x)(n-x-1)/2,两项和取最大值.
4、由于没说一定连通,所以最小度为0
最大度,为n-1入度与n-1出度
5、所有顶点的入度之和等于所有顶点的出度之和
6、假定点数为n,边数为e.
邻接矩阵存储空间为n^2
邻接表存储空间为n+e（有向图）,n+e*2（无向图,因为无向图一条边是拆成两条有向边来存）
7、矩阵适合稠密图,即边比较多的图~