. 连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
. 强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
. 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
. 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
. 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
图片说明
一.Kruskal算法
此算法是从边进行考虑，通过将边上的权值进行排序，每次选取最小的边加入到最小生成树中。
1.将所有边按权值大小进行排序放入数组中。
2.把图中的各个顶点看成n个独立的树组成的森林。
3.按排好的权值依次选择最小的边，所选的两个顶点q，p应该是属于两个不同的树。则两点间的边成为最小生成树的一条边，将这两棵树合并为同一棵树(这里需要涉及到并查集的算法)。
4.重复第3步，直到所有顶点都在同一棵树上或有n-1条边为止。
图片说明
二.prim算法
此算法是从点进行考虑的，通过选择一个初始点，找到这个初始点权值最小的边的点，并加入到最小生成树中，重复这个过程直到所有点被覆盖。
1.选取一个点为起始点，选取与它直接连通的最小权值的点，加入到最小生成树中。
2.按照1，每次将所选出的点再次作为起始点进行同样的操作，直到最小生成树有n-1条边或者n个顶点为止。
图片说明
三.练习
HDU1301（Jungle Roads）
1.prim代码

#include <iostream>              

using namespace std;

int num,m,b;            //num为村庄数   m为与n村庄有联系的村庄数量  b为n村庄到a村庄的代价
char n,a;               //n为村庄名称，a为与n村庄有联系的村庄名称
int road[27][27],visit[100],low[100];                  
road用来存储邻接矩阵,visit用来记录此村庄是否在最小树中，low是代表此村庄所能直接到达的村庄所需要的路程

int prim()
{
    int i,j,next;
    int min_road,cost = 0;               //min_road代表最短路的权值   cost表示最终最小生成树的总权值

    for(i = 1; i <= num; i++)          //这个for语句是让A村庄所能直接到达村庄的路程存入low集合中
    {
        visit[i] = 0;
        low[i] = road[1][i];
    }

    visit[1] = 1;

    for(i = 2; i <= num; i++)
    {

        min_road = 9999;

        for(j = 1; j <= num; j++)
        {
            if(!visit[j] && min_road > low[j])     //判断这条路是否标记过且此时最短路路程是否大于到这条路的路程
            {
                min_road = low[j];  //若满足则将到达此路所需要的路程赋给min_road
                next = j;      //将此路作为下一次的开始路
            }
        }

        visit[next] = 1;     //将这个村庄标记
        cost += min_road;     //将判断的第一条最短路加给cost

        //这个for语句是为将所能到达的村庄的代价进行更新
        for(j = 1;j <= num; j++)
        {
            if(!visit[j] && low[j] > road[next][j])
            {
                low[j] = road[next][j];
            }
        }
    }
    return cost;
}
int main()
{
    while(~scanf("%d",&num) && num)
    {
        getchar();

        for(int x = 1; x <= num; x++)
        {
            for(int y = 1; y <= num; y++)
            {
                if(x == y)
                    road[x][y] = 0;
                else
                    road[x][y] = 9999;
            }
        }

        for(int x = 1; x < num; x++)
        {
            char q;

            scanf("%c %d",&n,&m);

            q = n - 'A' + 1;                                 //将输入的字母转化为1~26的数字

            for(int y = 1; y <= m; y++)
            {
                getchar();                                     //下面要输入%c所以这里吸收一下回车

                char p;

                scanf("%c %d",&a,&b);

                p = a - 'A' + 1;                            //将输入的字母转化为1~26的数字
                road[q][p] = road[p][q] = b;                  //将数值放入并更新邻接矩阵
            }

            getchar();                                    //同理，吸收一下回车
        }

        printf("%d\n",prim());
    }
}

2.Kruskal代码

#include <iostream>                ////最小生成树（Kruskal算法）1301（Jungle Roads）
#include <algorithm>

using namespace std;

struct Road
{
    int x,y,cost;
};

int num,m,b,l = 0;                                            //num为村庄数   m为与n村庄有联系的村庄数量
char n,a;                                               //n为头村庄名称，a为与n村庄有联系的村庄名称
int min_cost = 0,father[27];                 //min_cost记录最小代价,father数组记录村庄之间联系
Road Distance[200];

class Shengxu
{
public:

    bool operator()(Road x,Road y)           //重载
    {
        if(x.cost < y.cost)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

int Merge(int a)                  //并查集
{
    if(father[a] == a)
    {
        return a;
    }
    return father[a] = Merge(father[a]);
}
void Kruskal()
{
    for(int i = 1; i <= l; i++)
    {
        int q = Merge(Distance[i].x);
        int p = Merge(Distance[i].y);

        if(q != p)                  //判断在不在同一树上
        {
            father[p] = q;
            min_cost += Distance[i].cost;
        }
    }
}
int main()
{
    while(~scanf("%d",&num) && num)
    {

        min_cost = 0,l = 0;
        for(int i = 1; i <= num; i++)          //初始化
        {
            father[i] = i;
        }

        getchar();

        for(int i = 1; i < num; i++)
        {
            int q;

            scanf("%c %d",&n,&m);

            q = n - 'A' + 1;                                 //将输入的字母转化为1~26的数字

            for(int j = 1; j <= m; j++)
            {
                getchar();                                     //下面要输入%c所以这里吸收一下回车

                int p;

                scanf("%c %d",&a,&b);

                p = a - 'A' + 1;                            //将输入的字母转化为1~26的数字
                ++l;
                Distance[l].x = q;
                Distance[l].y = p;
                Distance[l].cost = b;
            }

            getchar();                                    //同理，吸收一下回车
        }

        sort(Distance + 1,Distance +1 + l,Shengxu());    //调用sort函数对Distance[1]到Distance[1+l]进行升序排序
        Kruskal();

        printf("%d\n",min_cost);
    }
}