1.prime算法思想:(只与顶点有关)
prime算法求最小生成树时，和边数无关，只和顶点的数量有关，时间复杂度是O(n^2),所以呢，适合于求稠密网的最小生成树;
将一个图的顶点分为两部分,一部分是最小生成树的集合，这里就记为(A集合),另一部分是未处理的顶点集合.
首先，选择一个节点，将这个节点加入A集合，然后，对集合A中的顶点遍历,找出A中顶点关联的边权值最小的点加入A集合。
不断重复第二步，直到B集合中所有的顶点加入A集合结束.
得到的A集合就是最小生成树的顶点集合.
具体的实现过程:
定义一个结构体来保存最小生成树的顶点结合.
typedef struct{
char data;
int lowcost;
}closedge[MAXLEN]; //MAXLEN 宏定义最大的顶点数
closedge myedge;
将第一个点放入最小生成树的集合中,然后把myedge[i].data置为第一个顶点的值,将myedge[i].lowcost置为0,代表这个点已经在最小生成树中;
从第二个点开始,初始化myedge.lowcost[i]的值为和第一个点相连的边的权值。
4.找最小权值的边.
5.更新最小生成树集合.
看代码来解释，还是具体的实例解释这个算法，理解起来比较容易;
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
#define INFINE 32678
typedef struct Stack
{
int data;
struct Stack *next;
}LinkStack;
typedef struct Queue
{
int data;
struct Queue *next;
}LNode;
typedef struct
{
LNode *front;
LNode *rear;
}LinkQueue;
typedef struct ArcNode
{
int adjvex;
int weight;
struct ArcNode *next;
}ArcNode;
typedef struct VertexNode
{
char vexdata;
ArcNode *head;
}VertexNode;
typedef struct
{
VertexNode vertex[MAXVEX];
int vexnum; //顶点数
int arcnum; //边数
}AdjList;
typedef struct{
char data;
int Plowcost;
}closedge[MAXVEX];
/********************************栈的操作******************************************/
LinkStack *Init_LinkStack(LinkStack *T)
{
T=(LinkStack *)malloc(sizeof(LinkStack));
T->next=NULL;
return T;
}
int IsEmpty_LinkStack(LinkStack *T)
{
if(T->next!=NULL){
return 0;
}
return 1;
}
LinkStack* Push_LinkStack(LinkStack *T,int t)
{
LinkStack *s=(LinkStack *)malloc(sizeof(LinkStack));
if(s==NULL){
return NULL;
}
s->data=t;
s->next=T->next;
T->next=s;
}
LinkStack *Pop_LinkStack(LinkStack *T,int *t)
{
LinkStack *p=T->next;
if(T->next==NULL){
return NULL;
}
*t=p->data;
T->next=p->next;
free(p);
}
/*************************队列的操作****************************/
LinkQueue *Init_LinkQueue()
{
LinkQueue *q=(LinkQueue *)malloc(sizeof(LinkQueue));
LNode *p=(LNode *)malloc(sizeof(LNode));
p->next=NULL;
q->front=q->rear=p;
return q;
}
int IsEmpty_LinkQueue(LinkQueue *q)
{
if(q->front == q->rear){
return 1;
}
return 0;
}
void EnterQueue(LinkQueue *q,int t)
{
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data=t;
s->next=NULL;
q->rear->next=s;
q->rear=s;
}
int OutQueue(LinkQueue *q,int *t)
{
LNode *p;
if(IsEmpty_LinkQueue(q)){
printf("the Queue is Empty!\n");
return 0;
}else{
p=q->front->next;
*t=p->data;
q->front->next=p->next;
free(p);
if(q->front->next==NULL){
q->rear=q->front;
}
return 1;
}
}
VertexNode *Insert(VertexNode *h,ArcNode *p) //此函数的意义是把每个链表根据adjvex的按从小到大的顺序排列;
{
ArcNode *pre,*cur,*q;
cur=h->head;
if(cur == NULL){
p->next=cur;
cur->next=p;
}else{
pre =h->head;
q=h->head->next;
while(q){
if(p->adjvex < q->adjvex ){
p->next=q;
pre->next=p;
break;
}
pre = q;
q=q->next;
}
if(q == NULL){ //当新的节点比当前链表中的所有的adjvex都大时，直接插在链表的最后面.
p->next==NULL;
pre->next = p;
}
}
return h;
}
AdjList *Created_Graph(AdjList *G)
{
int i,j,k,n1,n2,weight;
ArcNode *s;
char vex1,vex2;
G=(AdjList *)malloc(sizeof(AdjList));
printf("请输入顶点的个数和边数:");
scanf("%d%d",&G->vexnum,&G->arcnum);
printf("请输入顶点:\n");
for(i=1;i<=G->vexnum;i++)
{
printf("No.%d号顶点的值:",i);
scanf(" %c",&G->vertex[i].vexdata);
G->vertex[i].head=(ArcNode *)malloc(sizeof(ArcNode)); //为每个头节点开辟空间;有头节点的链表;
G->vertex[i].head->next=NULL; //头节点指向为空;
}
printf("请输入由两个顶点构成的边:\n");
for(k=1;k<=G->arcnum;k++){
printf("请输入第%d条边:",k);
scanf(" %c%c",&vex1,&vex2);
for(i=1;i<=G->vexnum;i++){
if(G->vertex[i].vexdata == vex1){
n1=i;
}
if(G->vertex[i].vexdata == vex2){
n2=i;
}
}
printf("请输入权值:");
scanf("%d",&weight);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex = n2;
s->weight=weight;
Insert(&G->vertex[n1],s);
/*如果是有向图，则下面的语句去掉就行*/
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex = n1;
Insert(&G->vertex[n2],s);
}
return G;
}
int visited[MAXVEX]={0};
void dfs(AdjList *G,int i)
{
ArcNode *p;
printf("%c ",G->vertex[i].vexdata);
visited[i]=1;
p=G->vertex[i].head->next;
while(p){
if(visited[p->adjvex]==0){
dfs(G,p->adjvex);
}
p=p->next;
}
}
void trans_dfs(AdjList *G)
{
int v;
for(v=1;v<=G->vexnum;v++){
visited[v]=0;
}
for(v=1;v<=G->vexnum;v++){
if(visited[v]==0){
dfs(G,v); //当图只有一个连通分量时，此句只会执行一次;
}
}
}
void undfs(AdjList *G,int vo)
{
LinkStack *T;
ArcNode *p;
T=Init_LinkStack(T);
int visited[MAXVEX]={0},i, t;
Push_LinkStack(T,vo);
while(!IsEmpty_LinkStack(T)){
Pop_LinkStack(T,&t);
if(visited[t]==0){
printf("%c ",G->vertex[t].vexdata);
visited[t]=1;
}
p=G->vertex[t].head->next;
while(p){
if(visited[p->adjvex] == 0){
printf("%c ",G->vertex[p->adjvex].vexdata);
visited[p->adjvex]=1;
Push_LinkStack(T,p->adjvex);
p=G->vertex[p->adjvex].head->next;
}else{
p=p->next;
}
}
}
void bfs(AdjList *G,int v)
{
int i,t;
ArcNode *p;
LinkQueue *S=Init_LinkQueue();
for(i=1;i<=G->vexnum;i++)
{
visited[i]=0;
}
visited[v]=1;
printf("%c ",G->vertex[v].vexdata);
EnterQueue(S,v);
while(!IsEmpty_LinkQueue(S)){
OutQueue(S,&t);
p=G->vertex[t].head->next;
while(p){
if(visited[p->adjvex]==0){
printf("%c ",G->vertex[p->adjvex].vexdata);
visited[p->adjvex]=1;
EnterQueue(S,p->adjvex);
}
p=p->next;
}
}
}
void print(AdjList *G)
{
ArcNode *p;
int i;
for(i=1;i<=G->vexnum;i++){
printf(" %c:",G->vertex[i].vexdata);
p=G->vertex[i].head->next;
while(p)
{
printf("%d ",p->adjvex);
p=p->next;
}
printf("\n");
}
}
int minNum(AdjList *G,closedge myedge){
int i,j,min,minIndex;
for(i=1;i<=G->vexnum;i++){
if(myedge[i].Plowcost!=0){
min=myedge[i].Plowcost; //首先找出第一个不是最小生成树顶点集合当做最小值;
j=i;
break;
}
}
minIndex=j; //这句的作用就是当找出的第一个正好是最小的权值时，直接返回;
for(i=j;i<=G->vexnum;i++){ //遍历最小生成树集合，找当前未被加入此集合的最小权值的顶点
if(min > myedge[i].Plowcost && myedge[i].Plowcost!=0){
min=myedge[i].Plowcost;
minIndex=i;
}
}
return minIndex;
}
void Prime(AdjList *G,int start)
{
int i,k,j;
closedge myedge;
ArcNode *p=G->vertex[start].head->next;
myedge[start].data=G->vertex[start].vexdata;
myedge[start].Plowcost=0;
for(i=1;i<=G->vexnum;i++){
if(i!=start){
myedge[i].data=G->vertex[start].vexdata; //初始化最小生成树的顶点
myedge[i].Plowcost=INFINE; //把它的最小权值设置到相对无穷； 这两个量后面会时时更新
}
}
for(;p!=NULL;p=p->next){
myedge[p->adjvex].Plowcost=p->weight; //这一步是更新和第一个点相关联的顶点的信息;
}
for(i=2;i<=G->vexnum;i++){
k=minNum(G,myedge);
printf("%d\n",k);
printf("%c %c %d\n",G->vertex[k].vexdata,myedge[k].data,myedge[k].Plowcost);
myedge[k].Plowcost=0;
/*我感觉这里属于比较难理解的地方，所以，我详细说，这里的意思就是，当每次往最小生成树集合中加一个顶点时
，我们就去更新和它相关联的点的信息*/
for(p=G->vertex[k].head->next;p!=NULL;p=p->next){
if(myedge[p->adjvex].Plowcost > p->weight){
printf(":1\n");
myedge[p->adjvex].Plowcost= p->weight;
myedge[p->adjvex].data = G->vertex[k].vexdata;
}
}
}
}
void
int main(int argc,char *argv[])
{
AdjList *G;
G=Created_Graph(G);
print(G);
printf("**************dfs递归遍历*****************************\n");
dfs(G,1);
printf("\n");
printf("*************dfs递归遍历多个连通分量********************\n");
trans_dfs(G);
printf("\n");
printf("*******************dfs非递归遍历*************************\n");
undfs(G,1);
printf("\n");
printf("*********************bfs遍历****************************\n");
bfs(G,1);
printf("\n");
printf("*********************Prime算法***************************\n");
Prime(G,1);
return 0;
}对于代码中Prime算法，我做了很多注释,其它 的代码都在上一篇http://www.ystruct.com/archives/506.html中有提到，所以，在这里就不做详细解释了，直接复制就可以运行.