RT:
在数据结构中,N个顶点的连通图至少要有（N-1）条边（也就是树）才能保证图为连通图.

对于简单图而言至多有n*(n-1)/2条边,此时即是完全图.

强连通图最多n(n-1)条边,最少n-1条边.
强连通图：任意两个顶点都相互连通的图。


e.g.: 15年腾讯软测的一道选择题

	

我们都是时间旅行者 
为了寻找生命中的光 
终其一生 
行走在漫长的旅途上 
安迪·安德鲁斯
相邻关系：两个顶点之间存在一条边，则表示两个顶点具有相邻关系路径：相邻顶点序偶所构成的序列路径长度：路径上边的数目回路：若一条路径中第一个顶点和最后一个顶点相同，则为回路连通：从顶点Vi到顶点Vj有路径，则称Vi和Vj连通连通图和连通分量是针对无向图的强连通图和强连通分量是针对有向图的
由概念感觉两者像是形式不同但意思一样，但不一样的说法.
任意两个不同顶点之间都存在方向相反的两条弧.
看概念：
如果图中任意两个顶点之间都连通，则称该图为连通图。
连通：
从顶点Vi到顶点Vj有路径，则称Vi和Vj连通
路径：相邻顶点序偶所构成的序列
其实最大的疑惑是路径是相邻顶点
其实可看出，连通是两个顶点连通就可以，也就是说，连通图是说两个顶点连通，不一定非要是相邻的两个顶点。
一个无向图G= (V,E)是连通的，那么边的数目大于等于顶点的数目减一
有向完全图和强连通图的区别？
有向完全图一定是强连通的，但强连通不一定是有向完全图。
看概念：
强连通图(Strongly Connected Graph)是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
有向完全图：具有n(n-1)条边的有向图称为有向完全图
有n个顶点的强连通图最多有n(n-1)条边，最少有n条边
证明：
(1)最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n(n-1)/2条边，而由于强连通图是有向图，故每条边有两个方向，n(n-1)/2×2=n(n-1)，故有n个顶点的强连通图最多有n(n-1)条边。
(2)最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。
下面举例说明：如图1所示，设ABCD四个点构成强连通图，则：
(1)边数最多有4×3=12条
(2)边数最少有4条即：一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次
图：由结点的有穷集合V和边的集合E组成。
图的结点称为顶点，边是顶点的有序偶对。
简单路径：序列中顶点不重复出现的路径称为简单路径
网：边上带权的图称为带权图，也称为网
无法在扩充顶点的连通子图称为极大连通子图
一个图中的极大连通子图：从一个顶点开始作为子图，逐个添加和这个子图有边相连的顶点，直到所有相连顶点都被纳入其中，所生成的子图就是一个极大连通子图。
图有多种存储方式，但一般用到的是邻接矩阵(顺序存储)和邻接表(链式存储)。邻接表：由单链表的表头形成的顶点表和单链表其余结点形成的边表两部分组成邻接多重表中，所有的依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接链表的差别仅仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。
每一个独立而丰富的灵魂，
都有处可栖。
工具人点在看

	

通过前面的学习，对于含有 n 个顶点的连通图来说可能包含有多种生成树，例如图 1 所示：
图 1 连通图的生成树
图 1 中的连通图和它相对应的生成树，可以用于解决实际生活中的问题：假设A、B、C 和 D 为 4 座城市，为了方便生产生活，要为这 4 座城市建立通信。对于 4 个城市来讲，本着节约经费的原则，只需要建立 3 个通信线路即可，就如图 1(b)中的任意一种方式。在具体选择采用(b)中哪一种方式时，需要综合考虑城市之间间隔的距离，建设通信线路的难度等各种因素，将这些因素综合起来用一个数值表示，当作这条线路的权值。
图 2 无向网
假设通过综合分析，城市之间的权值如图 2(a)所示，对于(b)的方案中，选择权值总和为 7 的两种方案最节约经费。这就是本节要讨论的最小生成树的问题，简单得理解就是给定一个带有权值的连通图(连通网)，如何从众多的生成树中筛选出权值总和最小的生成树，即为该图的最小生成树。给定一个连通网，求最小生成树的方法有：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。
普里姆算法
普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在树中的(假设为 A 类)，剩下的是另一类(假设为 B 类)。对于给定的连通网，起始状态全部顶点都归为 B 类。在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。例如，通过普里姆算法查找图 2(a)的最小生成树的步骤为：假如从顶点A出发，顶点 B、C、D 到顶点 A 的权值分别为 2、4、2，所以，对于顶点 A 来说，顶点 B 和顶点 D 到 A 的权值最小，假设先找到的顶点 B：
继续分析顶点 C 和 D，顶点 C 到 B 的权值为 3，到 A 的权值为 4；顶点 D 到 A 的权值为 2，到 B 的权值为无穷大(如果之间没有直接通路，设定权值为无穷大)。所以顶点 D 到 A 的权值最小：
最后，只剩下顶点 C，到 A 的权值为 4，到 B 的权值和到 D 的权值一样大，为 3。所以该连通图有两个最小生成树：
具体实现代码为：
#include #include #define VertexType int#define VRType int#define MAX_VERtEX_NUM 20#define InfoType char   #define INFINITY 65535typedef struct {    VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。    InfoType * info;                        //弧额外含有的信息指针}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];typedef struct {    VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据    AdjMatrix arcs;                         //二维数组，记录顶点之间的关系    int vexnum,arcnum;                      //记录图的顶点数和弧(边)数}MGraph;//根据顶点本身数据，判断出顶点在二维数组中的位置int LocateVex(MGraph G,VertexType v){    int i=0;    //遍历一维数组，找到变量v    for (; i        if (G.vexs[i]==v) {            return i;        }    }    return -1;}//构造无向网void CreateUDN(MGraph* G){    scanf("%d,%d",&(G->vexnum),&(G->arcnum));    for (int i=0; ivexnum; i++) {        scanf("%d",&(G->vexs[i]));    }    for (int i=0; ivexnum; i++) {        for (int j=0; jvexnum; j++) {            G->arcs[i][j].adj=INFINITY;            G->arcs[i][j].info=NULL;        }    }    for (int i=0; iarcnum; i++) {        int v1,v2,w;        scanf("%d,%d,%d",&v1,&v2,&w);        int m=LocateVex(*G, v1);        int n=LocateVex(*G, v2);        if (m==-1 ||n==-1) {            printf("no this vertex\n");            return;        }        G->arcs[n][m].adj=w;        G->arcs[m][n].adj=w;    }}//辅助数组，用于每次筛选出权值最小的边的邻接点typedef struct {    VertexType adjvex;//记录权值最小的边的起始点    VRType lowcost;//记录该边的权值}closedge[MAX_VERtEX_NUM];closedge theclose;//创建一个全局数组，因为每个函数中都会使用到//在辅助数组中找出权值最小的边的数组下标，就可以间接找到此边的终点顶点。int minimun(MGraph G,closedge close){    int min=INFINITY;    int min_i=-1;    for (int i=0; i        //权值为0，说明顶点已经归入最小生成树中；然后每次和min变量进行比较，最后找出最小的。        if (close[i].lowcost>0 && close[i].lowcost < min) {            min=close[i].lowcost;            min_i=i;        }    }    //返回最小权值所在的数组下标    return min_i;}//普里姆算法函数，G为无向网，u为在网中选择的任意顶点作为起始点void miniSpanTreePrim(MGraph G,VertexType u){    //找到该起始点在顶点数组中的位置下标    int k=LocateVex(G, u);    //首先将与该起始点相关的所有边的信息：边的起始点和权值，存入辅助数组中相应的位置，例如(1，2)边，adjvex为0，lowcost为6，存入theclose[1]中，辅助数组的下标表示该边的顶点2    for (int i=0; i        if (i !=k) {            theclose[i].adjvex=k;            theclose[i].lowcost=G.arcs[k][i].adj;        }    }    //由于起始点已经归为最小生成树，所以辅助数组对应位置的权值为0，这样，遍历时就不会被选中    theclose[k].lowcost=0;    //选择下一个点，并更新辅助数组中的信息    for (int i=1; i        //找出权值最小的边所在数组下标        k=minimun(G, theclose);        //输出选择的路径        printf("v%d v%d\n",G.vexs[theclose[k].adjvex],G.vexs[k]);        //归入最小生成树的顶点的辅助数组中的权值设为0        theclose[k].lowcost=0;        //信息辅助数组中存储的信息，由于此时树中新加入了一个顶点，需要判断，由此顶点出发，到达其它各顶点的权值是否比之前记录的权值还要小，如果还小，则更新        for (int j=0; j            if (G.arcs[k][j].adj                theclose[j].adjvex=k;                theclose[j].lowcost=G.arcs[k][j].adj;            }        }    }    printf("\n");}int main(){    MGraph G;    CreateUDN(&G);    miniSpanTreePrim(G, 1);}
图 3 无向网
使用普里姆算法找图 3 所示无向网的最小生成树的测试数据为：
6,10
1
2
3
4
5
6
1,2,6
1,3,1
1,4,5
2,3,5
2,5,3
3,4,5
3,5,6
3,6,4
4,6,2
5,6,6
运行结果为：
v1 v3
v3 v6
v6 v4
v3 v2
v2 v5
普里姆算法的运行效率只与连通网中包含的顶点数相关，而和网所含的边数无关。所以普里姆算法适合于解决边稠密的网，该算法运行的时间复杂度为：O(n2)。
如果连通网中所含边的绸密度不高，则建议使用克鲁斯卡尔算法求最小生成树(下节详细介绍)。

目录

完全图公式

非连通无向图有28条边,至少有多少顶点

一个链式队列的队头和队尾指针分别为f和r，则判断队空的条件为

在用单链表表示的链式队列Q中

完全图公式

n个端点的完全图有n个端点以及n(n − 1) / 2条边，以Kn表示

例题：

非连通无向图有28条边,至少有多少顶点

8个点全联通27 ，加上一个孤立点；

所以28条边的非连通无向图为9个(加入一个孤立点)

一个链式队列的队头和队尾指针分别为f和r，则判断队空的条件为

A．f!=NULL

B．r!=NULL

C．f==NULL

D．f==r

在用单链表表示的链式队列Q中

队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front ==Q->rear 答案：×

不要混淆队列和循环队列