图的概念
图（Graph）是由顶点的有穷非空集合和定点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
在图中数据元素称之为顶点（Vertex），图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
若顶点vi到vj之间的边有方向，则称这条边为有向边，也称为弧（Arc），用有序偶<vi，vj>来表示，其中vi称为弧尾，vj称为弧头。如果图中任意两个顶点之间的边都是有向的，则称该图为有向图。例如：G1 = <V1,E1>：
其中V1={A, B, C, D, E}，E1={<A,B>, <A,E>,<B,C>, <C,D>,<D,B>,<D,A>, <E,C>}。
若顶点vi到vj之间的边没有方向，则称这条边为无向边，用无序偶对（vi，vj）来表示，如果图中任意两个顶点之间的边都是无向的，则称该图为无向图。例如：G2=(V2,E2)
其中，V2={A, B, C, D, E, F}，E2={(A, B), (A, E),(B, E), (C, D), (D, F),(B, F), (C, F)}
注意无向边用小括号“()”表示，而有向边用尖括号“<>”表示。在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。以下不是简单图：
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有：
n-1 + n-2 + … + 3 + 2 + 1=n(n-1)/2条边
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条边。
有很少条边的图称为稀疏图，反之称为稠密网。
当图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权，这些权可以表示从一个顶点到另一个顶点的距离或耗费。带权的图通常称为网（Network）。
假设有两个图G=(V,{E})和G1=(V1,{E1})，如果V1属于等于V且E1属于等于E，则称G1为G的子图：
和顶点v关联的边的数目定义为顶点的度：
对有向图来说，由于弧有方向性，则有入度和出度之分。顶点的出度：以顶点v为弧尾的弧的数目；顶点的入度：以顶点v为弧头的弧的数目。
顶点的度(TD)=出度(OD)+入度(ID)
则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。
若图G中任意两个顶点之间都有路径相通，则称此图为连通图：
若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量：
对于有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。
一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。比如下图中的图1是一个普通图，但显然不是生成树，当去掉两条构成环的边后，比如图2或图3，就满足n个顶点和n-1条边且连通的定义了，它们都是一颗生成树。从这里也可以知道，如果一个图有n个顶点和小于n-1条边，则是非连通图；如果它多于n-1条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2和图3,随便加任意两个顶点的边都将构成环。注意：有n-1条边并不一定时生成树，比如图4。
如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。所谓入度为0其实相当于树中的根结点，其余顶点入度为1就是说树的非根结点的双亲只有一个。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。如下图中图1是一棵有向图，去掉一些弧后，它可以分解为两棵有向图，如图2和图3，这两棵就是图1有向图的生成森林。
图的存储结构
邻接矩阵
基本思想：用一个一维数组存储顶点的信息，用一个二维数组（邻接矩阵）来存储顶点这间的关系。
邻接矩阵:表示顶点间相互关系的矩阵。定义：设G=(V,E)是有n（n>=1)个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵：
无向图的邻接矩阵为对称矩阵：
有向图的邻接矩阵为非对称矩阵：
网的邻接矩阵可定义为：
#include <iostream>
using namespace std;
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
#define MAXVEX 100 //最大顶点数 应由用户定义
#define INFINITY 65535 //用65535来代表无穷
typedef struct{
VertexType vexs[MAXVEX]; //顶点表
EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵 可看作边表
int numVertexes,numEdges; //图中当前的顶点数和边数
}MGraph;
//建立无向网的邻接矩阵表示
void CreateMGraph(MGraph *G){
int i,j,k,w;
cout<<"请输入顶点数和边数："<<endl;
cin>>G->numVertexes>>G->numEdges;
for(i=0;i<G->numVertexes;i++) //输入顶点信息 建立顶点表
cin>>G->vexs[i];
for(i=0;i<G->numVertexes;i++)
for(j=0;j<G->numVertexes;j++)
G->arc[i][j]=INFINITY; //邻接矩阵初始化
for(k=0;k<G->numEdges;k++){
cout<<"输入边(vi,vj)上的下标i，下标j和权w："<<endl;
cin>>i>>j>>w;
G->arc[i][j]=w;
G->arc[j][i]=G->arc[i][j]; //因为是无向图 矩阵对称
}
}
int main(){
MGraph *G=(MGraph*)malloc(sizeof(MGraph));
CreateMGraph(G);
system("pause");
}
邻接矩阵是不错的一种图存结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存储空间的极大浪费。
邻接表
无向图的邻接表存储表示：
有向图的邻接表：
可见，在有向图的邻接表中不易找到指向该顶点的弧。
特点：
1.无向图中顶点Vi的度为第i个单链表中的结点数；
2.有向图中顶点Vi的出度为第i个单链表中的结点个数；顶点Vi的入度为整个单链表中邻接点域值是i的结点个数；
有向图的逆邻接表：
在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。
对于带权值得网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可：
我们可以定义两个表，一个顶点表，一个边表：
#include <iostream>
using namespace std;
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
#define MAXVEX 100
typedef struct EdgeNode{ //边表结点
int adjvex; //邻接点域 存储该顶点对应的下标
EdgeType weight; //用于存储权值 对于非网图可以不需要
struct EdgeNode *next; //链域 指向下一个邻接点
}EdgeNode;
typedef struct VertexNode{ //顶点表结点
VertexType data; //顶点域
EdgeNode *firstedge; //边表头指针
}VertexNode,AdjList[MAXVEX];
typedef struct{
AdjList adjList;
int numVertexes,numEdges; //图中当前顶点数和边数
}GraphAdjList;
//建立图的邻接表结构
void CreateALGraph(GraphAdjList *G){
int i,j,k;
EdgeNode *e;
cout<<"输入顶点数和边数："<<endl;
cin>>G->numVertexes>>G->numEdges; //输入顶点数和边数
for(i=0;i<G->numVertexes;i++){ //读入顶点信息 建立顶点表
cin>>G->adjList[i].data;
G->adjList[i].firstedge=NULL; //将边表置为空表
}
for(k=0;k<G->numEdges;k++){ //成立边表
cout<<"输入边(vi,vj)上的顶点序号："<<endl;
cin>>i>>j;
e=(EdgeNode*)malloc(sizeof(EdgeNode)); //向内存申请空间 生成边表结点
e->adjvex=j; //邻接点序号为j
e->next=G->adjList[i].firstedge; //将e指针指向当前顶点指向的结点 头插法
G->adjList[i].firstedge=e; //将当前顶点的指针指向e
e=(EdgeNode*)malloc(sizeof(EdgeNode)); //向内存申请空间 生成边表结点
e->adjvex=i; //邻接点序号为i
e->next=G->adjList[j].firstedge; //将e指针指向当前顶点指向的结点 头插法
G->adjList[j].firstedge=e; //将当前顶点的指针指向e
}
}
int main(){
GraphAdjList *G=(GraphAdjList*)malloc(sizeof(GraphAdjList));
CreateALGraph(G);
system("pause");
}
十字链表
对于有向图来说，邻接表是有缺陷的。邻接表能知道初度，如果要想知道入度，必须遍历整个图才能知道，反之，逆邻接表解决了入度却解决不了初度的情况。
如果把邻接表和逆邻接表结合起来，我们就会得到一种有向图存储方法：十字链表。
我们重新定义顶点表结构：
其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表的第一个结点。
重新定义的边表结构：
其中taivex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标。headlink是指入边表指针域，指向终点相同的下一条边，也就是逆邻接表的连接方式。taillink是指出边表指针域，指向起点相同的下一条边，也就是邻接表的连接方式。如果是网，还可以再增加一个weight域来存储权值。
如下图所示，顶点依然是存入一个一维数组{v0,v1,v2,v3}，实线箭头指针的图示与邻接表相同。以顶点v0为例，firstout指向的是出边表中的第一个结点v3，所以v0边表结点的headvex=3，而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所以headlink和taillink都是空的。
虚线箭头其实是逆邻接表的表示，对于v0来说，它有两个顶点v1和v2的入边。因此v0的firstin指向顶点v1的边表结点中和headvex为0的结点，如图中(1)。接着由入边结点的headlink指向下一个入边顶点v2，如图中的(2)。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如图中的(3)。顶点v2和v3也是同样有一个入边顶点，如图中(4)和(5)。
有向图的十字链表存储表示：
#define MAX_VERTEX_NUM 20
typedef struct ArcBox{ //边表
int tailvex,headvex; //该弧的尾和头顶点的位置
struct ArcBox *headlink,*taillink; //分别为弧头相同和弧尾相同的弧的链域
InfoType *info; //该弧相关信息的指针
}ArcBox;
typedef struct VexNode{ //顶点表
VertexType data;
ArcBox *firstin,*firstout; //分别指向该顶点第一条入弧和出弧
}VexNode;
typedef struct{
VexNode xlist[MAX_VERTEX_NUM]; //表头向量
int vexnum,arcnum; //有向图的当前顶点数和弧数
}OLGraph;
十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度和邻接表相同的，因此在有向图的应用中，十字链表是非常好的数据结构模型。
邻接多重表
十字链表是有向图的优化存储结构，对于无向图的邻接表，我们使用一种叫做邻接多重表来优化。
如果我们重点关注顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记机，删除某一条边等操作，那就意味着需要找到这两条边表结点进行操作，因为在邻接点中，一条边由两个结点组成，这是比较麻烦的。如下图，若要删除左图中的(v0,v2)这条边，需要对邻接表结构中右边表的阴影两个结点进行删除操作，显然这是比较繁琐的。
重新定义的边表结点结构：
其中ivex和jvex是与某条边依附的两个顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。这就是邻接多重表的结构。如图所示：
无向图的邻接多重表存储表示：
#define MAX_VERTEX_NUM 20
typedef emnu{unvisited,visited} VisitIf;
typedef struct EBox{ //边表
VisitIf mark; //访问标记
int ivex,jvex; //该边依附的两个顶点的位置
struct EBox *ilink,*jlink; //分别指向依附这两个顶点的下一条边
InfoType *info; //改变信息指针
}EBox;
typedef struct VexBox{ //顶点表
VertexType data;
EBox *firstedg; //指向第一条依附该顶点的边
};
typedef struct{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum; //无向图的当前顶点数和边数
}AMLGraph;
邻接多重表与邻接表的差别仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只用一个结点。这样对边的操作就方便多了。若要删除左边的(v0,v2)这条边，只需要将右图的(6)和(9)的链接指向改变为(^)即可。
边集数组
边集数组是由两个一维数组构成，一个是存储顶点信息；另一个是存储边的信息，这个边数组中每个数据元素由一条边的起点下标、终点下标和权值组成。显然边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高，因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。
定义的边数组结构体如：
其中begin是存储起点下标，end是存储终点下标，weight是存储权值。
图的遍历
深度优先搜索
对于连通图来说，从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到，简称DFS。深度优先搜索其实是一种前序遍历。
对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则选图中一个未曾被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。
DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，….如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问； 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
使用邻接矩阵方式：
#include <iostream>
using namespace std;
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
#define MAXVEX 100 //最大顶点数 应由用户定义
#define INFINITY 65535 //用65535来代表无穷
typedef struct{
VertexType vexs[MAXVEX]; //顶点表
EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵 可看作边表
int numVertexes,numEdges; //图中当前的顶点数和边数
}MGraph;
typedef int Boolean; //Boolean是布尔类型 其值是TRUE或FALSE
Boolean visited[MAXVEX]; //访问标志的数组
//建立无向网的邻接矩阵表示
void CreateMGraph(MGraph *G){
int i,j,k,w;
cout<<"请输入顶点数和边数："<<endl;
cin>>G->numVertexes>>G->numEdges;
for(i=0;i<G->numVertexes;i++) //输入顶点信息 建立顶点表
cin>>G->vexs[i];
for(i=0;i<G->numVertexes;i++)
for(j=0;j<G->numVertexes;j++)
G->arc[i][j]=INFINITY; //邻接矩阵初始化
for(k=0;k<G->numEdges;k++){
cout<<"输入边(vi,vj)上的下标i，下标j和权w："<<endl;
cin>>i>>j>>w;
G->arc[i][j]=w;
G->arc[j][i]=G->arc[i][j]; //因为是无向图 矩阵对称
}
}
//邻接矩阵的深度优先递归算法
void DFS(MGraph *G,int i){
int j;
visited[i]=true;
cout<<G->vexs[i]<<endl; //打印顶点 也可以其他操作
for(int j=0;j<G->numVertexes;j++)
if(G->arc[i][j]==1 && !visited[j])
DFS(G,j); //对未访问的邻接点顶点递归调用
}
//邻接矩阵的深度遍历操作
void DFSTraverse(MGraph *G){
int i;
for(i=0;i<G->numVertexes;i++)
visited[i]=false; //初始所有顶点状态都是未访问过状态
for(i=0;i<G->numVertexes;i++)
if(!visited[i]) //对未访问的顶点调用DFS
DFS(G,i);
}
int main(){
MGraph *G=(MGraph*)malloc(sizeof(MGraph));
CreateMGraph(G);
DFSTraverse(G);
system("pause");
}
程序运行结果：
如果图结构是邻接表结构，其DFSTraverse函数的代码几乎相同，只是在递归函数中因为将数组换成了链表而有所不同：
#include <iostream>
using namespace std;
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
#define MAXVEX 100
typedef struct EdgeNode{ //边表结点
int adjvex; //邻接点域 存储该顶点对应的下标
EdgeType weight; //用于存储权值 对于非网图可以不需要
struct EdgeNode *next; //链域 指向下一个邻接点
}EdgeNode;
typedef struct VertexNode{ //顶点表结点
VertexType data; //顶点域
EdgeNode *firstedge; //边表头指针
}VertexNode,AdjList[MAXVEX];
typedef struct{
AdjList adjList;
int numVertexes,numEdges; //图中当前顶点数和边数
}GraphAdjList;
typedef int Boolean; //Boolean是布尔类型 其值是TRUE或FALSE
Boolean visited[MAXVEX]; //访问标志的数组
//建立图的邻接表结构
void CreateALGraph(GraphAdjList *G){
int i,j,k;
EdgeNode *e;
cout<<"输入顶点数和边数："<<endl;
cin>>G->numVertexes>>G->numEdges; //输入顶点数和边数
for(i=0;i<G->numVertexes;i++){ //读入顶点信息 建立顶点表
cin>>G->adjList[i].data;
G->adjList[i].firstedge=NULL; //将边表置为空表
}
for(k=0;k<G->numEdges;k++){ //成立边表
cout<<"输入边(vi,vj)上的顶点序号："<<endl;
cin>>i>>j;
e=(EdgeNode*)malloc(sizeof(EdgeNode)); //向内存申请空间 生成边表结点
e->adjvex=j; //邻接点序号为j
e->next=G->adjList[i].firstedge; //将e指针指向当前顶点指向的结点 头插法
G->adjList[i].firstedge=e; //将当前顶点的指针指向e
e=(EdgeNode*)malloc(sizeof(EdgeNode)); //向内存申请空间 生成边表结点
e->adjvex=i; //邻接点序号为i
e->next=G->adjList[j].firstedge; //将e指针指向当前顶点指向的结点 头插法
G->adjList[j].firstedge=e; //将当前顶点的指针指向e
}
}
//邻接表的深度优先递归算法
void DFS(GraphAdjList *G,int i){
EdgeNode *p;
visited[i]=true;
cout<<G->adjList[i].data<<endl; //打印顶点 也可以其他操作
p=G->adjList[i].firstedge;
while(p){
if(!visited[p->adjvex])
DFS(G,p->adjvex); //对未访问的邻接点顶点递归调用
p=p->next;
}
}
//邻接表的深度遍历操作
void DFSTraverse(GraphAdjList *G){
int i;
for(i=0;i<G->numVertexes;i++)
visited[i]=false; //初始所有顶点状态都是未访问过状态
for(i=0;i<G->numVertexes;i++)
if(!visited[i]) //对未访问的顶点调用DFS
DFS(G,i);
}
int main(){
GraphAdjList *G=(GraphAdjList*)malloc(sizeof(GraphAdjList));
CreateALGraph(G);
DFSTraverse(G);
system("pause");
}
程序运行结果：
对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率大大提高。
广度优先搜索
广度优先遍历，又称为广度优先搜索，简称BFS。如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。如下图中，顶点A放置在最上面的第一层，让与它有边的顶点B、F为第二层，再让与B和F有边的顶点C、I、G、E为第三层，再将这四个顶点有边的D、H放在第四层：
邻接矩阵的广度遍历算法：
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
#define MAXVEX 100 //最大顶点数 应由用户定义
#define INFINITY 65535 //用65535来代表无穷
typedef struct{
VertexType vexs[MAXVEX]; //顶点表
EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵 可看作边表
int numVertexes,numEdges; //图中当前的顶点数和边数
}MGraph;
typedef int Boolean; //Boolean是布尔类型 其值是TRUE或FALSE
Boolean visited[MAXVEX]; //访问标志的数组
void BFSTraverse(MGraph *G){
int i,j;
Queue Q;
for(i=0;i<G->numVertexes;i++)
visited[i]=false;
InitQueue(&Q); //初始化辅助用的队列
for(i=0;i<G->numVertexes;i++){ //对每个顶点作循环
if(!visited[i]){ //若是未访问过就处理
visited[i]=true;
cout<<G->vexs[i]<<endl; //打印顶点
EnQueue(&Q,i); //将此顶点如队列
while(!QueueEmpty(Q)){ //若当前队列不为空
DeQueue(&Q,&i); //将队中元素出队列 赋值给i
//判断其他顶点是否与当前顶点存在边并且未访问过
if(G->arc[i][j]==1 && !visited[j]){
visited[j]=true; //将找到的此顶点标记为已访问
cout<<G->vexs[j]<<endl; //打印顶点
EnQueue(&Q,j); //将找到的此顶点入队列
}
}
}
}
}
邻接表的广度遍历算法：
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
#define MAXVEX 100
typedef struct EdgeNode{ //边表结点
int adjvex; //邻接点域 存储该顶点对应的下标
EdgeType weight; //用于存储权值 对于非网图可以不需要
struct EdgeNode *next; //链域 指向下一个邻接点
}EdgeNode;
typedef struct VertexNode{ //顶点表结点
VertexType data; //顶点域
EdgeNode *firstedge; //边表头指针
}VertexNode,AdjList[MAXVEX];
typedef struct{
AdjList adjList;
int numVertexes,numEdges; //图中当前顶点数和边数
}GraphAdjList;
typedef int Boolean; //Boolean是布尔类型 其值是TRUE或FALSE
Boolean visited[MAXVEX]; //访问标志的数组
void BFSTraverse(GraphAdjList *G){
int i;
EdgeNode *p;
Queue Q;
for(i=0;i<G->numVertexes;i++)
visited[i]=false;
InitQueue(&Q); //初始化辅助用的队列
for(i=0;i<G->numVertexes;i++){ //对每个顶点作循环
if(!visited[i]){ //若是未访问过就处理
visited[i]=true;
cout<<G->adjList[i].data<<endl; //打印顶点
EnQueue(&Q,i); //将此顶点如队列
while(!QueueEmpty(Q)){ //若当前队列不为空
DeQueue(&Q,&i); //将队中元素出队列 赋值给i
p=G->adjList[i].firstedge; //找到当前顶点指向边表的头指针
while(p){
if(!visited[p->adjvex]){ //若此顶点未被访问
visited[p->adjvex]=true;
cout<<G->adjList[p->adjvex].data<<endl;
EnQueue(&Q,p->adjvex); //将此点如队列
}
p=p->next; //指向下一个邻接点
}
}
}
}
}
广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程。
遍历应用举例：
1.求一条从顶点i到顶点s的简单路径；
2.求两个顶点之间的一条路径长度最短的路径；
最小生成树
假设需要为一个镇的九个村庄架设通信网络做设计，村庄的大致如图所示，其中v0~v8是村庄，之间的连线的数字表示村与村之间可通达的直线距离，要求必须用最小的成本来完成此次任务：
提供了三种方案：
我们把构造连通网的最小代价生成树称为最小生成树。
找连通网的最小生成树经典的有两种算法，普里姆算法和克鲁斯卡尔算法。
普里姆算法
首先构造邻接矩阵：
算法的步骤如下：
1.我们首先从一个点出发，如v0点，一开始就把v0点纳入最小优先生成树，然后以v0点为一个整体，找出和整体连接的边的权值最小的那一条边：
很明显，和整体连接的权值最小的那一条边是(v0,v1)，权值为10。但是在计算机上如何实现呢？我们声明一个叫lowcost[9]的数组，因为是从整体是v0，因此把v0的那一行邻接矩阵的值拷进lowcost中，因此lowcost的数组值为：
0 1 2 3 4 5 6 7 8
0 10 65535 65535 65535 11 65535 65535 65535
遍历lowcost，10就是最小值，因此v1被纳入最小生成树中{v0,v1}，同时标记v1=0,因此lowcost的数组值变为：
0 1 2 3 4 5 6 7 8
0 0 65535 65535 65535 11 65535 65535 65535
2.整体已经变为：
然后寻找与整体的连接的边，因为已经把v0的邻边放进lowcost数组中，现在要把v1邻边也放进数组，具体做法也是把v1行的邻接矩阵与lowcost中对应的元素比较，若更小时就把邻接矩阵的值放进lowcost数组中。因此lowcost数组变为：
0 1 2 3 4 5 6 7 8
0 0 18 65535 65535 11 16 65535 12
遍历lowcost数组我可以得到与整体连接的权值最小的边11,于是把v5纳入最小优先生成树中，把{v0,v1,v5}作为一个整体：
3.同样在把v5的邻边放进lowcost数组中，寻找与整体连接权值最小的边：
0 1 2 3 4 5 6 7 8
0 0 18 65535 26 0 16 65535 12
扫描数组，最小值为12，把v8纳入最小生成树中，如此循环模拟，最终求出最小生成树。
Prim算法生成最小生成树的代码实现过程：
void MiniSpanTree_Prim(MGraph G){
int min,i,j,k;
int adjvex[MAXVEX]; //保存相关顶点下标
int lowcost[MAXVEX]; //保存相关顶点间边的权值
lowcost[0]=0; //初始化第一个权值为0 即v0加入生成树
//lowcost的值为0 在这里就是此下标的顶点已经加入生成树
adjvex[0]=0; //初始化第一个顶点下标为0
for(i=1;i<G.numVertexes;i++){ //循环除下标为0外的全部顶点
lowcost[i]=G.arc[0][i]; //将v0顶点与之右边的权值存入数组
adjvex[i]=0; //初始化都为v0的下标
}
for(i=1;i<G.numVertexes;i++){
min=INFINITY; //初始化最小值为无穷
//通常设置不可能的大数字如32767 65535等
j=1;k=0;
while(j<G.numVertexes){ //循环全部顶点
if(lowcost[j]!=0&&lowcost[j]<min){
//如果权值不为0且权值小于min
min=lowcost[j]; //则让当前权值称为最小值
k=j; //将当前最小值的下标存入k
}
j++；
}
printf("(%d,%d)",adjvex[k],k); //打印当前顶点边中权值最小边
lowcost[k]=0; //将当前顶点的权值设置为0 表示此顶点已经完成任务
for(j=1;j<G.numVertexes;j++){
if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){
//若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
lowcost[j]=G.arc[k][j]; //将较小权值存入lowcost
adjvex[j]=k; //将下标为k的顶点存入adjvex
}
}
}
}
由算法中的循环嵌套可得知此算法的时间复杂度为O(n2)。
克鲁斯卡尔算法
普里姆算法是以某顶点未起点，逐步找个顶点上最小权值的边来构建最小生成树的。而克鲁斯卡尔算法直接就以边为目标去构建，因为权值是在边上，直接去找最小权值的边来构建生成树也是很自然的想法，但是构建时要考虑是否会形成环路。此时我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码：
typedef struct{
int begin;
int end;
int weight;
}Edge;
我们还需要将邻接矩阵通过程序转换为右图的边集数组，并且对它们按权值从小到大排序，如下图：
Kruskal算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G){
int i,n,m;
Edge edges[MAXEDGE]; //定义边集数组
int parent[MAXVEX]; //定义一数组用来判断边与边是否形成环路
//此处省略将邻接矩阵G转化为边集数组edges并按权由小到大排序的代码
for(i=0;i<G.numVertexes;i++)
parent[i]=0; //初始化数组值为0
for(i=0;i<G.numEdges;i++){ //循环每一条边
n=Find(parent,edges[i].begin);
m=Find(parent,edges[i].end);
if(n != m){ //假如n和m不等 说明此边没有与现有生成树形成环路
parent[n]=m; //将此边的结尾顶点放入下标为起点的parent中
//表示此顶点已经在生成树集合中
printf("(%d,%d) %d",edges[i].begin,edges[i].end,edges[i].weight);
}
}
}
int Find(int *parent,int f){ //查找连线顶点的尾部下标
while(parent[f]>0)
f=parent[f];
return f;
}
以下为程序运行过程，其中粗线表示被选中的边：
