数据结构图的算法的毕业论文
图
图形结构是一种比树形结构更复杂的非线性结构。树形结构中的结点之间具有明显的层次关系，且每一层上的结点只能和上一层中的一个结点相关，但可能和下一层的多个结点相关。在图形结构中，任意两个结点之间都可能相关，即结点与结点之间的邻接关系可以是任意的。因此，图形结构可用来描述更加复杂的对象。
1 图的基本概念和存储结构
1.1 图的定义
图（Graph ）是由非空的顶点集合V 与描述顶点之间关系——边（或者弧）的集合E 组成，其形式化定义为：
G=(V , E)
如果图G 中的每一条边都是没有方向的，则称G 为无向图。无向图中边是图中顶点的无序偶对。无序偶对通常用圆括号“( )”表示。例如，顶点偶对(v i ,v j )表示顶点v i 和顶点v j 相连的边，并且(v i ,v j )与(v j ,v i )表示同一条边。
如果图G 中的每一条边都是有方向的，则称G 为有向图。有向图中的边是图中顶点的有序偶对，有序偶对通常用尖括号“< >”表示。例如，顶点偶对
图是一种复杂的数据结构，表现在不仅各顶点的度可以不同，而且顶点之间的逻辑关系也错综复杂。从图的定义可知：一个图的信息包括两个部分：图中顶点的信息以及描述顶点之间的关系——边或弧的信息。因此无论采取什么方法来建立图的存储结构，都要完整、准确地反映这两部分的信息。为适于用C 语言描述，从本节起顶点序号由0开始，即图的顶点集的一般形式为：V={v 0,v 1,…,v n-1}。
下面介绍几种常用的图的存储结构。
1.2 邻接矩阵
所谓邻接矩阵存储结构，就是用一维数组存储图中顶点的信息，并用矩阵来表示图中各顶点之间的邻接关系。假定图G=(V , E)有n 个顶点，即V={v 0,v 1,…,v n-1}，则表示G 中各顶点相邻关系需用一个n ×n 的矩阵，且矩阵元素为：
A[i][j]= 若G 是带权图（网），则邻接矩阵可定义为： A[i][j]= 其中，w ij 表示(v i ,v j )或
图7-6 无向图及邻接矩阵表示
有向图的邻接矩阵表示如图7-7所示。
图7-7 有向图及邻接矩阵表示
带权图的邻接矩阵表示如图7-8所示。
1 若(v i ,v j )或
0 若(v i ,v j )或
0或∞ 若(v i ,v j )或
图7-8 带权图及邻接矩阵表示
从图的邻接矩阵可以看出以下特点：
（1）无向图（包括带权图）的邻接矩阵一定是一个按对角线对称的对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。
（2）对于无向图，邻接矩阵的第i行或第i列的非零元素（或非∞元素）个数正好是第i个顶点的度D(v i)。
（3）对有向图，邻接矩阵的第i行非零元素（或非∞元素）的个数正好是第i个顶点的出度OD(v i)，第i列非零元素（或非∞元素）的个数正好是第i个顶点的入度ID(v i)。
（4）用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中具体有多少条边，则必须按行、按列对每一个元素进行查找后方能确定，因此花费的时间代价较大，这也是用邻接矩阵存储图的局限性。
在采用邻接矩阵方式表示图时，除了用一个二维数组存储用于表示顶点相邻关系的邻接矩阵之外，还需要用一个一维数组存储顶点信息。这样，一个图在顺序存储结构下的类型定义为；
typedef struct
{
char vertex[MaxNum]; /*顶点为字符型且顶点表的长度小于MaxNum*/
int edges[MaxNum][MaxNum]; /*边为整型且edges为邻接矩阵*/
} MGraph; /*MGraph为采用邻接矩阵存储的图类型*/
建立一个无向图的邻接矩阵程序如下：
#include
#include
#define MAXSIZE 30
typedef struct
{
char vertex[MAXSIZE]; //顶点为字符型且顶点表的长度小于MAXSIZE
int edges[MAXSIZE][MAXSIZE]; //边为整型且edges为邻接矩阵
}MGraph; //MGraph为采用邻接矩阵存储的图类型
void CreatMGraph(MGraph *g,int e,int n)
{ //建立无向图的邻接矩阵g->egdes，n为顶点个数，e为边数
int i,j,k;
printf("Input data of vertexs(0~n-1):\n");
for(i=0;i g->vertex[i]=i; //读入顶点信息 for(i=0;i for(j=0;j g->edges[i][j]=0; //初始化邻接矩阵 for(k=1;k<=e;k++) //输入e条边*/ { printf("Input edge of(i,j): "); scanf("%d,%d",&i,&j); g->edges[i][j]=1; g->edges[j][i]=1; } } void main() { int i,j,n,e; MGraph *g; //建立指向采用邻接矩阵存储图类型指针 g=(MGraph *)malloc(sizeof(MGraph)); //生成采用邻接矩阵存储图类型的存储空间 printf("Input size of MGraph: "); //输入邻接矩阵的大小 scanf("%d",&n); printf("Input number of edge: "); //输入邻接矩阵的边数 scanf("%d",&e); CreatMGraph(g,e,n); //生成存储图的邻接矩阵 printf("Output MGraph:\n"); //输出存储图的邻接矩阵 for(i=0;i { for(j=0;j printf("%4d",g->edges[i][j]); printf("\n"); } } 【说明】 无向图的邻接矩阵表示如图15-1所示。 图15-1 无向图及邻接矩阵表示 对图15-1所示的无向图，程序执行如下： 输入： Input size of MGraph: 4↙ Input number of edge: 4↙ Input data of vertexs(0~n-1): Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙ 输出： Output MGraph: 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 Press any key to continue 0 1 0 1 A= 1 0 1 1 0 1 0 0 1 1 0 0 V 0 V 3 V 1 V 2 1.3 邻接表 邻接表是图的一种顺序存储与链式存储相结合的存储方法。邻接表表示法类似于树的孩子表示法。也即，对于图G 中的每个顶点v i ，将所有邻接于v i 的顶点v j 链成一个单链表，这个单链表就称为顶点v i 的邻接表；然后，将所有顶点的邻接表表头指针放入到一个一维数组中，就构成了图的邻接表。用邻接表表示的图有两种结构，如图7-9所示。 图7-9 邻接表表示的结点结构 一种是用一维数组表示的顶点表的结点（即数组元素）结构，它由顶点域（vertex ）和指向该顶点第一条邻接边的指针域（firstedge ）（也即，这个指针指向该顶点的邻接表）所构成。另一种是邻接表结点（边结点），它由邻接点域(adjvex)和指向下一条邻接边的指针域（next ）所构成。对带权图（网）的邻接表结点则需增加一个存储边上权值信息的这样一个域。因此，带权图的邻接表结点结构如图7-10所示。 图7-10 带权图（网）的邻接表结点结构 图7-11给出了图7-6所示的无向图所对应的邻接表表示。 图7-11 无向图的邻接表表示 邻接表表示下的类型定义为： typedef struct node /*邻接表结点*/ { int adjvex; /*邻接点域*/ struct node *next; /*指向下一个邻接边结点的指针域*/ }EdgeNode; /*邻接表结点类型*/ typedef struct vnode /*顶点表结点*/ { int vertex; /*顶点域*/ EdgeNode *firstedge; /*指向邻接表第一个邻接边结点的指针域*/ }VertexNode /*顶点表结点类型*/ 建立一个无向图的邻接表存储算法如下： void CreatAdjlist （VetexNode g[],int e,int n ） {/*建立无向图的邻接表，n 为顶点数，e 为边数，g[]存储n 个顶点表结点*/ EdgeNode *p; int i,j,k; printf (“Input date of vetex(0~n -1);\n”); for(i=0;i { g[i].vertex=i; /*读入顶点i 信息*/ g[i].firstedge=NULL; /*初始化指向顶点i 的邻接表表头指针*/ } for(k=1;k<=e;k++) /*输入e 条边*/ { printf("Input edge of(i,j): "); scanf("%d,%d",i,j); p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjex=j; /*在顶点v i的邻接表中添加邻接点为j的结点*/ p->next=g[i].firstedge; /*插入是在邻接表表头进行的*/ g[i].firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; /*在顶点v j的邻接表中添加邻接点为i的结点*/ p->next=g[j].firstedge; /*插入是在邻接表表头进行的*/ g[i].firstedge=p; } } 2 图的遍历 图的遍历是指从图中的任一顶点出发，按照事先确定的某种搜索方法依次对图中所有顶点进行访问且仅访问一次的过程。图的遍历要比树的遍历复杂得多，其复杂性主要表现在以下4个方面： （1）在图结构中，没有象树根结点那样“自然”的首结点，即图中的任何一个顶点都可以作为第一个被访问的结点。 （2）在非连通图中，从一个顶点出发只能访问它所在的连通分量上的所有顶点；因此，还需考虑如何选取下一个未被访问的顶点来继续访问图中其余的连通分量。 （3）在图结构中如果有回路存在，则一个顶点被访问后有可能沿回路又回到该顶点。 （4）在图结构中一个顶点可以和其它多个顶点相邻，当该顶点访问过后则存在如何从众多相邻顶点中选取下一个要访问的顶点问题。 图的遍历是图的一种基本操作，它是求解图的连通性问题、拓扑排序以及求关键路径等算法的基础。图的遍历通常采用深度优先搜索（Depth First Search,DFS）和广度优先搜索（Breadth First Search,BFS）两种方式，这两种方式对无向图和有向图的遍历都适用。 2.1 深度优先搜索 深度优先搜索对图的遍历类似于树的先根遍历，是树的先根遍历的一种推广；也即，搜索顶点的次序是沿着一条路径尽量向纵深发展。深度优先搜索的基本思想是：假设初始状态是图中所有顶点都未曾访问过，则深度优先搜索可以从图中某个顶点v出发即先访问v，然后依次从v的未曾访问过的邻接点出发，继续深度优先搜索图，直至图中所有和v有路径相通的顶点都被访问过；若此时图中尚有顶点未被访问过，则另选一个未曾访问过的顶点作为起始点，重复上述深度优先搜索的过程，直到图中的所有顶点都被访问过为止。 我们以图7-18的无向图为例进行图的深度优先搜索。假定从顶点v0出发，在访问了顶点v0后选择邻接点v1作为下一个访问的顶点；由于v1未曾访问过，则访问v1并继续由v1开始搜索下一个邻接点v3作为访问顶点；v3同样没有访问过，则访问v3并继续搜索下一个邻接点v6；v6也未访问过，则访问v6再继续搜索下一个邻接点v4；v4未曾访问过，则访问v4并继续搜索下一个邻接点v1，此时由于v1已被访问过则回退至v4继续搜索v4的下一个邻接点；由于v4已无未被访问过的邻接点，则继续回退到v6再搜索v6的未被访问邻接点；…这种回退一直持续到v0，此时可搜索到v0的未被访问邻接点v2，即访问v2并继续搜索下一个邻接点v5；由于v5未被访问，则访问v5并继续搜索v5的邻接点；因v5已无未被访问过的邻接点故回退至v2，继续搜索v2的未被访问邻接点，但v2 已无未被访问过的邻接点，则回退至v0，而v0也无未被访问的邻接点。由于v0为搜索图时的出发结点，故到此搜索结束。由此得到深度优先搜索遍历图的结点序列为： v0→v1→v3→v6→v4→v2→v5 图7-18 无向图深度优先搜索示意 显然，深度优先搜索遍历图的过程是一个递归过程，我们可以用递归算法来实现。在算法中为了避免在访问过某顶点后又沿着某条回路回到该顶点这种重复访问的情况出现，就必须在图的遍历过程中对每一个访问过的顶点进行标识，这样才可以避免一个顶点被重复访问的情况出现。所以，我们在遍历算法中对n个顶点的图设置了一个长度为n的访问标志数组visited[n]，每个数组元素被初始化0，一旦某个顶点i被访问则相应的visited[i]就置为1来做为访问过的标志。 对以邻接表为存储结构的图（可为非连通图）进行深度优先搜索的程序如下： #include #include #define MAXSIZE 30 typedef struct node //邻接表结点 { int adjvex; //邻接点域 struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 { int vertex; //顶点域 EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n) {//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点EdgeNode *p; int i,j,k; printf("Input date of vetex(0~n-1);\n"); for(i=0;i { g[i].vertex=i; //读入顶点i信息 g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 } for(k=1;k<=e;k++) //输入e条边 { printf("Input edge of(i,j): "); scanf("%d,%d",&i,&j); p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } } int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量void DFS(VertexNode g[],int i) { EdgeNode *p; printf("%4d",g[i].vertex); //输出顶点i信息，即访问顶点i visited[i]=1; //置顶点i为访问过标志 p=g[i].firstedge; //根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点while(p!=NULL) //当邻接边结点不为空时 { if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 DFS(g,p->adjvex); //对这个边结点进行深度优先搜索 p=p->next; //查找顶点i的下一个邻接边结点} } void DFSTraverse(VertexNode g[],int n) {//深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数int i; for(i=0;i visited[i]=0; //访问标志置0 for(i=0;i DFS(g,i); //从未访问过的顶点i开始遍历 } void main() { int e,n; V ertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf("Input number of node:\n"); //输入图中结点个数 scanf("%d",&n); printf("Input number of edge:\n"); //输入图中边的个数 scanf("%d",&e); printf("Make adjlist:\n"); CreatAdjlist(g,e,n); //建立无向图的邻接表 printf("DFSTraverse:\n"); DFSTraverse(g,n); //深度优先遍历以邻接表存储的无向图 printf("\n"); } 【说明】 对图15-1所示的无向图，程序执行如下： 输入：Input number of node: 4↙ Input number of edge: 4↙ Make adjlist: Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙ 输出：DFSTraverse: 0 3 1 2 Press any key to continue 2.2 广度优先搜索 广度优先搜索遍历图类似于树的按层次遍历。广度优先搜索的基本思想是：从图中某顶点v出发，访问顶点v后再依次访问与v相邻接的未曾访问过的其余邻接边结点v1，v2，…，v k；接下来再按上述方法访问与v1邻接的未曾访问过的各邻接边结点、与v2邻接的未曾访问过的各邻接边结点、…、与v k邻接的未曾访问过的各邻接边结点；…这样逐层下去直至图中的全部顶点都被访问过。广度优先搜索遍历图的特点是尽可能先进行横向搜索，即先访问的顶点其邻接边结点也先访问，后访问的顶点其邻接边结点也后访问。 例如，对图7-19所示的无向图进行广度优先搜索遍历，首先访问v0，然后访问v0未被访问的邻接边结点v1和v3（注意，先是v1然后才是v3），接下来访问v1未被访问的邻接边结点v4，再访问v3未被访问邻接边结点v2（v3的邻接边结点v4已被访问过）。此时，图中所有顶点都被访问过即完成了图的遍历，所得到的顶点访问序列为： v0→v1→v3→v4→v2 为了实现图的广度优先搜索，必须引入队列结构来保存已访问过的顶点序列；即从指定的顶点开始，每访问一个顶点就同时使该顶点进入队尾；然后由队头取出一个顶点并访问该顶点的所有未被访问过的邻接边结点并且使该邻接边结点进入队尾，…如此进行下去直到队空时为止，则图中所有由开始顶点所能到达的全部顶点均已访问过。 对以邻接表为存储结构的图进行广度优先搜索的程序如下： #include #include #define MAXSIZE 30 typedef struct node1 //邻接表结点 { int adjvex; //邻接点域 struct node1 *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 { int vertex; //顶点域 EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n) {//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点EdgeNode *p; int i,j,k; printf("Input date of vetex(0~n-1);\n"); for(i=0;i { g[i].vertex=i; //读入顶点i信息 g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针} for(k=1;k<=e;k++) //输入e条边 { printf("Input edge of(i,j): "); scanf("%d,%d",&i,&j); p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } } typedef struct node { int data; struct node *next; }QNode; //链队列结点的类型 typedef struct { QNode *front,*rear; //将头、尾指针纳入到一个结构体的链队列 }LQueue; void Init_LQueue(LQueue **q) //创建一个带头结点的空队列 { QNode *p; *q=(LQueue *)malloc(sizeof(LQueue));//申请带头、尾指针的结点 p=(QNode*)malloc(sizeof(QNode)); //申请链队列的头结点 p->next=NULL; //头结点的next指针置为空 (*q)->front=p; //队头指针指向头结点 (*q)->rear=p; //队尾指针指向头结点 } int Empty_LQueue(LQueue *q) //判队空 { if(q->front==q->rear) //队为空 return 1; else return 0; } void In_LQueue(LQueue *q,int x) //入队 { QNode *p; p=(QNode *)malloc(sizeof(QNode)); //申请新链队列结点 p->data=x; p->next=NULL; //新结点作为队尾结点时其next域为空 q->rear->next=p; //将新结点*p链到原队尾结点之后 q->rear=p; //使队尾指针指向新的队尾结点*p } void Out_LQueue(LQueue *q,int *x) //出队 { QNode *p; if(Empty_LQueue(q)) printf("Queue is empty!\n"); //队空，出队失败 else { p=q->front->next; //指针p指向链队列第一个数据结点（即队头结点） q->front->next=p->next; //头结点的next指针指向链队列第二个数据结点（即删除第一个数据结点）*x=p->data; //将删除的队头结点数据经由x返回 free(p); if(q->front->next==NULL) //出队后队为空，则置为空队列 q->rear=q->front; } } int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量void BFS(VertexNode g[],LQueue *Q,int i) {//广度优先搜索遍历邻接表存储的图，g为顶点表，Q为队指针，i为第i个顶点int j,*x=&j; EdgeNode *p; printf("%4d",g[i].vertex); //输出顶点i信息，即访问顶点i visited[i]=1; //置顶点i为访问过标志 In_LQueue(Q,i); //顶点i入队Q while(!Empty_LQueue(Q)) //当队Q非空时 { Out_LQueue(Q,x); //队头顶点出队并送j（暂记为顶点j） p=g[j].firstedge;//根据顶点j的表头指针查找其邻接表的第一个邻接边结点while(p!=NULL) { if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 { printf("%4d",g[p->adjvex].vertex);//输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送入队Q } p=p->next; //在顶点j 的邻接表中查找j的下一个邻接边结点} } } void main() { int e,n; V ertexNode g[MAXSIZE]; //定义顶点表结点类型数组g LQueue *q; printf("Input number of node:\n"); //输入图中结点个数 scanf("%d",&n); printf("Input number of edge:\n"); //输入图中边的个数 scanf("%d",&e); printf("Make adjlist:\n"); CreatAdjlist(g,e,n); //建立无向图的邻接表 Init_LQueue(&q); //队列q初始化 printf("BFSTraverse:\n"); BFS(g,q,0); //广度优先遍历以邻接表存储的无向图 printf("\n"); } 【说明】 对图15-1所示的无向图，程序执行如下： 输入：Input number of node: 4↙ Input number of edge: 4↙ Make adjlist: Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙ 输出：BFSTraverse: 0 3 1 2 Press any key to continue 2.3图的连通性问题 判断一个图的连通性是图的应用问题，我们可以利用图的遍历算法来求解这一问题。 1. 无向图的连通性 在对无向图进行遍历时，对连通图仅需从图中任一顶点出发进行深度优先搜索或广度优先搜索，就可访问到图中的所有顶点；对于非连通图，则需要由不连通的多个顶点开始进行搜索，且每一次从一个新的顶点出发进行搜索过程中得到的顶点访问序列，就是包含该出发顶点的这个连通分量中的顶点集。 因此，要想判断一个无向图是否为连通图，或者有几个连通分量，则可增加一个计数变量count并设其初值为0，在深度优先搜索算法DFSTraverse函数里的第二个for循环中，每调用一次DFS就给count增1；这样当算法执行结束时的count值即为连通分量的个数。 无向图连通分量的计算程序如下 #include #include #define MAXSIZE 30 typedef struct node1 //邻接表结点 { int adjvex; //邻接点域 struct node1 *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 { int vertex; //顶点域 EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n) {//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点EdgeNode *p; int i,j,k; printf("Input date of vetex(0~n-1);\n"); for(i=0;i { g[i].vertex=i; //读入顶点i信息 g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针} for(k=1;k<=e;k++) //输入e条边 { printf("Input edge of(i,j): "); scanf("%d,%d",&i,&j); p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } } int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量void DFS(VertexNode g[],int i) //图的深度优先遍历 { EdgeNode *p; printf("%4d",g[i].vertex); //输出顶点i信息，即访问顶点i visited[i]=1; //置顶点i为访问过标志 p=g[i].firstedge; //根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=NULL) //当邻接边结点不为空时 { if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 DFS(g,p->adjvex); //对这个边结点进行深度优先搜索p=p->next; //查找顶点i的下一个邻接边结点} } int count=0; //连通分量计数count初值为0 void ConnectEdge(VertexNode g[],int n) //求图的连通分量 {//深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数int i; for(i=0;i visited[i]=0; //访问标志置0 for(i=0;i { DFS(g,i); //从未访问过的顶点i开始遍历 count++; //访问过一个连通分量则count加1 } } void main() { int e,n; V ertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf("Input number of node:\n"); //输入图中结点个数 scanf("%d",&n); printf("Input number of edge:\n"); //输入图中边的个数 scanf("%d",&e); printf("Make adjlist:\n"); CreatAdjlist(g,e,n); //建立无向图的邻接表 printf("DFSTraverse:\n"); ConnectEdge(g,n); //求图的连通分量 printf("\nNumber of connect is %d\n",count); //输出连通分量 } 【说明】 图15-2无向图示意 对图15-2所示的无向图，程序执行如下： 输入：Input number of node: 8↙ Input number of edge: 7↙ Make adjlist: Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,2↙ Input edge of(i,j): 0,4↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 2,3↙ Input edge of(i,j): 5,6↙ Input edge of(i,j): 5,7↙ 输出：DFSTraverse: 0 4 2 3 1 5 7 6 Number of connect is 2 Press any key to continue 3 生成树与最小生成树 3.1 生成树和生成森林 对于连通的无向图和强连通的有向图G=(V, E)，如果从图中任一顶点出发遍历图时，必然会将图中边的集合E(G)分别为两个子集T(G)和B(G)；其中，T(G)为遍历中所经过的边的集合，而B(G)为遍历中未经过的边的集合。显然，T(G)和图G中所有顶点一起构成了连通图G的一个极小连通子图；也即，G'=(V, T)是G的一个子图。按照生成树的定义，图G'为图G的一棵生成树。 连通图的生成树不是唯一的。从不同顶点出发进行图的遍历，或者虽然从图的同一个顶点出发但图的存储结构不同都可能得到不同的生成树。当一个连通图具有n个顶点时，该连通图的生成树就包含图中的全部n个顶点但却仅有连接这n个顶点的n-1条边。生成树不具有回路，在生成树G'=(V, T)中任意添加一条属于B(G)的边则必定产生回路。 我们将由深度优先搜索遍历图所得到的生成树称为深度优先生成树，将由广度优先搜索遍历图所得到的生成树称为广度优先生成树。图7-22(b)和图7-22(c)就是由图7-22(a)所得到的深度优先生成树和广度优先生成树；图中虚线为集合B(G)中的边，而实线为集合T(G)中的边。 图7-22 无向图及其生成树示意 对非连通图，通过对各连通分量的遍历将得到一个生成森林。 深度优先生成树求解可在DFS算法中添加一条语句得到，因为在DFS(g,i)中递归调用DFS(g,p->adjvex)时，i是刚访问过顶点v i的序号，而p->adjvex是v i未被访问过且正准备访问的邻接边结点序号。所以，只要在DFS算法中的if语句里，在递归调用DFS(g,p->adjvex)语句之前将边“(i,p->adjvex)”输出即可。同样也可在BFS算法中插入输出边的语句即可求得广度优先生成树算法。 深度优先生成树程序如下： #include #include #define MAXSIZE 30 typedef struct node //邻接表结点 { int adjvex; //邻接点域 struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 { int vertex; //顶点域 EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n) {//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点EdgeNode *p; int i,j,k; printf("Input date of vetex(0~n-1);\n"); for(i=0;i { g[i].vertex=i; //读入顶点i信息 g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针} for(k=1;k<=e;k++) //输入e条边 { printf("Input edge of(i,j): "); scanf("%d,%d",&i,&j); p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } } int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量void DFSTree(VertexNode g[],int i) //图的深度优先遍历 { EdgeNode *p; visited[i]=1; //置顶点i为访问过标志 p=g[i].firstedge; //根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=NULL) //当邻接边结点不为空时 { if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 { printf("(%d,%d),",i,p->adjvex); //输出生成树中的一条边 DFSTree(g,p->adjvex); //对这个边结点进行深度优先搜索} p=p->next; //查找顶点i的下一个邻接边结点 } } void DFSTraverse(VertexNode g[],int n) //生成深度优先生成树 {//深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数 int i; for(i=0;i visited[i]=0; //访问标志置0*/ for(i=0;i DFSTree(g,i); //从未访问过的顶点i开始遍历 } void main() { int e,n; V ertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf("Input number of node:\n"); //输入图中结点个数 scanf("%d",&n); printf("Input number of edge:\n"); //输入图中边的个数 scanf("%d",&e); printf("Make adjlist:\n"); CreatAdjlist(g,e,n); //建立无向图的邻接表 printf("DFSTraverse:\n"); DFSTraverse(g,n); //生成深度优先生成树 printf("\n"); } 【说明】 对图15-1所示的无向图，程序执行如下： 输入：Input number of node: 4↙ Input number of edge: 4↙ Make adjlist: Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙ 输出：DFSTraverse: (0,3),(3,1),(1,2), Press any key to continue 广度优先生成树程序如下： #include #include #define MAXSIZE 30 typedef struct { int data[MAXSIZE]; /*队中元素存储空间*/ int rear,front; /*队尾和队头指针*/ }SeQueue; void Int_SeQueue(SeQueue **q) { *q=(SeQueue*)malloc(sizeof(SeQueue)); (*q)->front=0; (*q)->rear=0; } int Empty_SeQueue(SeQueue *q) //判队空 { if(q->front==q->rear) return 1; //队空 else return 0; //队不空 } void In_SeQueue(SeQueue *q,int x) //入队 { if((q->rear+1)%MAXSIZE==q->front) printf("Queue is full!\n"); //队满，入队失败 else { q->rear=(q->rear+1)%MAXSIZE; //队尾指针加1 q->data[q->rear]=x; //将元素x入队} } void Out_SeQueue(SeQueue *q,int *x) //出队 { if(q->front==q->rear) printf("Queue is empty"); //队空，出队失败else { q->front=(q->front+1)%MAXSIZE; //队头指针加1 *x=q->data[q->front]; //队头元素出队并由x返回队头元素值} } typedef struct node //邻接表结点 { int adjvex; //邻接点域 struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 { int vertex; //顶点域 EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n) {//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 EdgeNode *p; int i,j,k; printf("Input date of vetex(0~n-1);\n"); for(i=0;i { g[i].vertex=i; //读入顶点i信息 g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针} for(k=1;k<=e;k++) //输入e条边 { printf("Input edge of(i,j): "); scanf("%d,%d",&i,&j); p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } } int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量 void BFSTree(VertexNode g[],int i) //生成广度优先生成树 {//广度优先搜索遍历邻接表存储的图，g为顶点表，Q为队指针，i为第i个顶点int j,*x=&j; SeQueue *q; EdgeNode *p; visited[i]=1; //置顶点i为访问过标志 Int_SeQueue(&q); In_SeQueue(q,i); //顶点i入队q while(!Empty_SeQueue(q)) //当队q非空时 { Out_SeQueue(q,x); //队头顶点出队并送j（暂记为顶点j） p=g[j].firstedge;//根据顶点j的表头指针查找其邻接表的第一个邻接边结点while(p!=NULL) { if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 { printf("(%d,%d),",j,p->adjvex); //输出生成树中的一条边 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_SeQueue(q,p->adjvex); //将该邻接边结点送入队q } p=p->next; //在顶点j 的邻接表中查找j的下一个邻接边结点} } } void main() { int e,n; V ertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf("Input number of node:\n"); //输入图中结点个数 scanf("%d",&n); printf("Input number of edge:\n"); //输入图中边的个数 scanf("%d",&e); printf("Make adjlist:\n"); CreatAdjlist(g,e,n); //建立无向图的邻接表 printf("DFSTraverse:\n"); BFSTree(g,0); //由顶点0开始生成广度优先生成树 printf("\n"); } 【说明】 对图15-1所示的无向图，程序执行如下： 输入：Input number of node: 4↙ Input number of edge: 4↙ Make adjlist: Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙ 输出：DFSTraverse: (0,3),(0,1),(1,2), Press any key to continue 3.2 最小生成树与构造最小生成树的Prim算法 由于生成树的不唯一性，即从不同的顶点出发可能得到不同的生成树，对不同的存储结构从同一顶点出发也可能得到不同的生成树。在连通网中边是带权值的，则连通网的生成树各边也是带权值的，我们把生成树各边权值总和称为生成树的权；那么，对无向连通图构成的连通网，则它的所有生成树中必有一棵边的权值总和为最小的生成树，我们称这棵生成树为最小生成树。 最小生成树有许多重要的应用，如以尽可能低的总造价建立n个城市间的通讯网络。我们可以用连通网来表示n个城市以及n个城市之间可能设置的通讯线路；其中网的顶点表示城市、边表示两城市之间的线路，边的权值表示该线路的造价。要想使总的造价最低，实际上就是寻找该网络的最小生成树。 构造最小生成树必须解决好以下两个问题： （1）尽可能选取权值小的边，但不能构成回路。 （2）选取合适的n-1条边将连通网的n个顶点连接起来。 构造最小生成树的算法主要是利用最小生成树的一种简称为MST的性质：设G=(V，E)是一个连通网络，U是顶点集合V的一个真子集。若(u,v)是G的所有边中一个顶点在U(即u∈U)里，而另一个顶点不在U(即v∈V-U)里且具有最小权值的一条边，则最小生成树必然包含边(u,v)。 普里姆（Prim）算法就是一种依据MST性质构造最小生成树的方法。假设G=(V，E)为一连通网，其中V为网中所有顶点的集合，E为网中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U={u0}（假设构造最小生成树时是从顶点u0出发），集合T的初值为T={}。Prim算法的思想是：在连通网中寻找一个顶点落入U集、另外一个顶点落入V-U集且权值最小的边加入到集合T中，并且将该边的属于V-U集的这个顶点加入到U集中，然后继续上述寻找一顶点在U集而另一顶点在V-U集且权值最小的边；如此不断重复直到U=V时，最小生成树就已经生成，这时集合T中包含了最小生成树中的所有边。 Prim算法能够实现最小生成树构造的理由如下： （1）构造过程中对正在生成的最小生成树来说，处于U集中的顶点都是有边相连的顶点，而V-U集中的顶点都是没有边相连的顶点，故一个顶点在V-U集的边则保证了这个顶点是第一次连接，因此不产生回路；另一个顶点在U集，则保证了生成树构造的连通性，即不会出现不连通的情况。 （2）最小生成树的构造过程要进行到U集等于V集为止，即此时U集中的顶点已包含连通网中的全部顶点，由(1)可知这些顶点都有边相连且又不产生回路，故必为一生成树。 （3）在保证（1）的前提下每次都是选取权值最小的边来构造生成树，故最终生成的树为最小生成树。 Prim算法可用下述过程描述(w uv表示连接顶点u与顶点v的这条边上的权值)： （1）U={u0}，T={ }； （2）while(U≠V) {(u,v)=min{w uv；u∈U，v∈V-U} T=T+{(u,v)} U=U+{v} } （3）结束。 为实现Prim算法，需要设置两个一维数组lowcast和closevertex；其中，数组lowcost 用来保存集合V-U中各顶点与集合U中各顶点所构成的边中具有最小权值的边的权值，并且一旦将lowcost[i]置为0，则表示顶点i已加入到集合U中，即该顶点不再作为寻找下一个最小权值边的顶点（只能在V-U集中寻找），否则将形成回路；也即，数组lowcost 有两个功能：一个是记录边的权值，一个是标识U集中的顶点。数组closevertex用来保存依附于该边在集合U中的顶点，即若closevertex[i]的值为j，则表示边(i,j)中的顶点j 在集合U中；数组closevertex同时也保存构造最小生成树过程中产生的每一条边，如closevertex[i]的值为j，则边(i,j)即为最小生成树的一条边。 我们先设定初始状态U={u0}（u0为出发的顶点），这时置lowcost[0]为0则表示顶点u0已加入到U集中，数组lowcost其它的数组元素值则为顶点u0到其余各顶点边的权值（没有边相连则取一个极大值），同时初始化数组closevertex[i]所有数组元素值为0（即先假定所有顶点包括u0都与u0有一条边）。然后不断选取权值最小的边(u i,u k)（u i∈U，