| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 2406 人关注过本帖, 1 人收藏
标题:Prime 算法求最小生成树 (邻接矩阵)
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
  已结贴   问题点数:20  回复次数:4   
Prime 算法求最小生成树 (邻接矩阵)
Name: Prime算法求最小生成树 (邻接矩阵)
    Copyright:
    Author: 巧若拙
    Date: 25/11/14 13:38
    Description:
    实现了 Prime算法求最小生成树 (邻接矩阵)的普通算法和最小堆优化算法。
程序代码:
#include<stdio.h>
#include<stdlib.h>

#define MAX 2000   //最大顶点数量 
#define INFINITY 999999   //无穷大 

typedef struct MinHeap{  
    int num;//存储顶点序号 
    int w;  //存储顶点到最小生成树的距离
} MinHeap; //最小堆结构体  

int map[MAX][MAX] = {0};//邻接矩阵存储图信息 

void CreatGraph(int m, int n);//创建邻接矩阵图 
void CreatGraph_2(int m, int n);//创建邻接矩阵图(随机图) 
void PrintGraph(int n);//输出图
void Prime(int n, int v0);//Prime算法求最小生成树(原始版本) 
void Prime_MinHeap(int n, int v0);//Prime算法求最小生成树(优先队列版本) 
void BuildMinHeap(MinHeap que[], int n);
void MinHeapSiftDown(MinHeap que[], int n, int pos);
void MinHeapSiftUp(MinHeap que[], int n, int pos);
void ChangeKey(MinHeap que[], int pos, int weight);//将第pos个元素的关键字值改为weight 
int SearchKey(MinHeap que[], int pos, int weight);//查找最小堆中关键字值为k的元素下标,未找到则返回-1(非递归) 
int ExtractMin(MinHeap que[]);//删除并返回最小堆中具有最小关键字的元素

int main()
{
    int i, j, m, n, v0 = 0;
    
    printf("请输入顶点数量:"); 
    scanf("%d", &n);
    printf("\n请输入边数量:"); 
    scanf("%d", &m);
    
    CreatGraph_2(m, n);//创建邻接矩阵图 
//    PrintGraph(n);//输出图
    Prime(n, v0);//Prime算法求最小生成树(原始版本) 
    Prime_MinHeap(n, v0);//Prime算法求最小生成树(优先队列版本) 

    return 0;
}

void CreatGraph(int m, int n)//创建邻接矩阵图 
{
    int i, j, a, b, c;
    
    for (i=0; i<n; i++) //初始化顶点数据 
    {
        for (j=0; j<n; j++)
        {
            map[i][j] = (i == j) ? 0 : INFINITY;
        }
    }
    printf("\n请按照a b c格式输入边信息:\n"); 
    for (i=0; i<m; i++)
    {
        scanf("%d%d%d", &a,&b,&c);
        map[a][b] = map[b][a] = c;
    }
} 

void CreatGraph_2(int m, int n)//创建邻接矩阵图(随机图) 
{
    int i, j, a, b, c;
    
    for (i=0; i<n; i++) //初始化顶点数据 
    {
        for (j=0; j<n; j++)
        {
            map[i][j] = (i == j) ? 0 : INFINITY;
        }
    }
   
    for (i=1; i<n; i++)//确保是连通图
    {
        map[i][0] = map[0][i] =  rand() % 100 + 1;
    } 
    m -= n - 1;
    while (m > 0)
    {
        for (i=0; i<n; i++) 
        {
            for (j=i+1; j<n; j++)
            {
                if (rand()%10 == 0) //有10%的概率出现边
                {
                    if (map[j][i] == INFINITY)
                    {
                        map[i][j] = map[j][i] =  rand() % 100 + 1;
                        m--;
                        if (m == 0)
                            return;
                    }
                } 
            }
        }
    }
} 

void PrintGraph(int n)//输出图
{
    int i, j;
    
    for (i=0; i<n; i++)
    {
        printf("G[%d] = %d: ", i, i);
        for (j=0; j<n; j++)
        {
            if (map[i][j] != 0 && map[i][j] != INFINITY)
                printf("<%d, %d> = %d", i, j, map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
} 

void Prime(int n, int v0)//Prime算法求最小生成树(原始版本) 
{
    int book[MAX] = {0}; //标记该顶点是否已经在路径中 
    int dic[MAX] = {0}; //存储顶点到最小生成树的距离 
    int adj[MAX] = {0}; //存储顶点在最小生成树树中的邻接点序号 
    int min, i, j, k;
    
    for (i=0; i<n; i++) //初始化工作 
    {
        dic[i] = map[v0][i];
        adj[i] = v0;
    }
    book[v0] = 1;
    
    for (i=1; i<n; i++) //每趟确定一个新顶点,共n-1趟 
    {
        min = INFINITY;
        k = v0;
        for (j=0; j<n; j++)//找出离最小生成树最近的顶点k 
        {
            if (book[j] == 0 && dic[j] < min)
            {
                min = dic[j];
                k = j;
            }
        }
        
        book[k] = 1;       printf("<%d, %d> = %d   ", adj[k], k, dic[k]);
        for (j=0; j<n; j++)//更新与顶点k的邻接点的dic[]值 
        {
            if (book[j] == 0 && dic[j] > map[k][j])
            {
                dic[j] = map[k][j];
                adj[j] = k;
            }
        }
    }
    
    min = 0;
    for (i=0; i<n; i++) //输出各顶点在最小生成树中的邻接点及边的长度 
    {
//        printf("<%d, %d> = %d\n", adj[i], i, dic[i]);
        min += dic[i];
    }    
    printf("最小生成树总长度(权值)为 %d\n", min); 
}

void Prime_MinHeap(int n, int v0)//Prime算法求最小生成树(优先队列版本) 
{
    int book[MAX] = {0}; //标记该城市是否已经在路径中 
    int dic[MAX] = {0}; //存储顶点到最小生成树的距离 
    int adj[MAX] = {0}; //存储顶点在最小生成树树中的邻接点序号 
    MinHeap que[MAX+1];//最小堆用来存储顶点序号和到最小生成树的距离 
    int min, i, j, k, pos, K;
    
    que[0].num = n; //存储最小堆中的顶点数量 
    for (i=0; i<n; i++) //初始化工作 
    {
        dic[i] = map[v0][i];
        adj[i] = v0;
        que[i+1].num = i;
        que[i+1].w = dic[i];
    }
    book[v0] = 1;
    BuildMinHeap(que, n);//构造一个最小堆 
    ExtractMin(que);//删除顶点v0 

    for (i=1; i<n; i++) //每趟确定一个新顶点,共n-1趟 
    {
        k = ExtractMin(que);//删除并返回最小堆中具有最小关键字的元素    
        book[k] = 1;   printf("<%d, %d> = %d   ", adj[k], k, dic[k]);
        for (j=0; j<n; j++)//更新与顶点k的邻接点的dic[]值,同时更新最小堆 
        {
            if (book[j] == 0 && dic[j] > map[k][j])
            {
                pos = SearchKey(que, j, dic[j]);    
                dic[j] = map[k][j];                  
                adj[j] = k;                  
                ChangeKey(que, pos, dic[j]);//将第pos个元素的关键字值改为weight  
            }
        }
    }
    
    min = 0;
    for (i=0; i<n; i++) //输出各顶点在最小生成树中的邻接点及边的长度 
    {
//        printf("<%d, %d> = %d\n", adj[i], i, dic[i]);
        min += dic[i];
    }    
    printf("最小生成树总长度(权值)为 %d\n", min); 
}

int ExtractMin(MinHeap que[])//删除并返回最小堆中具有最小关键字的元素
{  
    int pos = que[1].num;  
    
    que[1] = que[que[0].num--];
    MinHeapSiftDown(que, que[0].num, 1);  
      
    return pos;  
}  

int SearchKey(MinHeap que[], int pos, int weight)//查找最小堆中关键字值为k的元素下标,未找到则返回-1(非递归) 
{
    int Stack[MAX] = {0};
    int i = 1, top = -1;
    
    while ((i <= que[0].num && que[i].w <= weight) || top >= 0)//类似先序遍历二叉树的方式查找 
    {
        if (i <= que[0].num && que[i].w <= weight)
        {
            if (que[i].w == weight && que[i].num == pos)//权值与顶点序号都必须对应 
                return i;
            Stack[++top] = i;//该结点入栈 
            i *= 2; //搜索左孩子 
        }
        else
        {
            i = Stack[top--] * 2 + 1; //结点退栈并搜索右孩子 
        }
    }
    
    return -1;
}

void ChangeKey(MinHeap que[], int pos, int weight)//将第pos个元素的关键字值改为weight  
{  
    if (weight < que[pos].w) //关键字值变小,向上调整最小堆   
    {  
        que[pos].w = weight;  
        MinHeapSiftUp(que, que[0].num, pos);    
    }  
    else if (weight > que[pos].w)  //关键字值变大,向下调整最小堆   
    {  
        que[pos].w = weight;   
        MinHeapSiftDown(que, que[0].num, pos);      
    }     
} 

void MinHeapSiftDown(MinHeap que[], int n, int pos)  //向下调整结点 
{  
    MinHeap temp = que[pos];  
    int child = pos * 2; //指向左孩子   
      
    while (child <= n)  
    {  
        if (child < n && que[child].w > que[child+1].w) //有右孩子,且右孩子更小些,定位其右孩子   
            child += 1;  
          
        if (que[child].w < temp.w) //通过向上移动孩子结点值的方式,确保双亲小于孩子   
        {  
            que[pos] = que[child];   
            pos = child;  
            child = pos * 2;  
        }  
        else  
            break;  
    }  
    que[pos] = temp; //将temp向下调整到适当位置   
}  

void MinHeapSiftUp(MinHeap que[], int n, int pos)  //向上调整结点 
{  
    MinHeap temp = que[pos];  
    int parent = pos / 2; //指向双亲结点  
      
    if (pos > n) //不满足条件的元素下标   
        return;  
      
    while (parent > 0)  
    {  
        if (que[parent].w > temp.w) //通过向下移动双亲结点值的方式,确保双亲小于孩子   
        {  
            que[pos] = que[parent];   
            pos = parent;  
            parent = pos / 2;     
        }  
        else  
            break;  
    }  
    que[pos] = temp; //将temp向上调整到适当位置   
}  


void BuildMinHeap(MinHeap que[], int n)//构造一个最小堆 
{
    int i;
    
    for (i=n/2; i>0; i--)
    {
        MinHeapSiftDown(que, n, i);
    }
}
搜索更多相关主题的帖子: Copyright  color  
2014-11-26 14:07
wp231957
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:神界
等 级:版主
威 望:391
帖 子:13264
专家分:51144
注 册:2012-10-18
  得分:10 
标记

DO IT YOURSELF !
2014-11-26 15:36
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
  得分:0 
又写了一个用邻接表实现的Prime算法,数据结构不同,算法是一样的,其中自动生成图信息是亮点
程序代码:
/*
    Name: Prime算法求最小生成树 (邻接表)
    Copyright: 
    Author: 巧若拙 
    26/11/14 18:46
    Description: 
    实现了 Prime算法求最小生成树 (邻接表)的普通算法和最小堆优化算法。 
*/
#include<stdio.h>
#include<stdlib.h>

#define MAX 2000   //最大顶点数量 
#define INFINITY 999999   //无穷大 

typedef int VertexType; //顶点类型由用户自定义
typedef int EdgeType; //边上的权值类型由用户自定义

typedef struct EdgeNode{ //边表结点
int adjvex;  //邻接点域,存储该顶点对应的下标
EdgeType weight; //权值,对于非网图可以不需要 
struct EdgeNode *next; //链域,指向下一个邻接点 
} EdgeNode;

typedef struct VertexNode{ //顶点表结点
VertexType data; //顶点域,存储顶点信息
EdgeNode *firstEdge; //边表头指针
} VertexNode;

typedef struct MinHeap{  
    int num;//存储顶点序号 
    int w;  //存储顶点到最小生成树的距离
} MinHeap; //最小堆结构体  

int Locate(VertexNode *GL, int u, int v);//判断u,v是否是邻接点 
void CreateGraph(VertexNode *GL, int n, int m);//创建邻接表图(人工图) 
void CreateGraph_2(VertexNode *GL, int n, int m);//创建邻接表图(随机图) 
void PrintGraph(VertexNode *GL, int n);//输出图
void DestroyGL(VertexNode *GL, int n);//销毁图并释放空间 
void Prime(VertexNode *GL, int n, int v0);//Prime算法求最小生成树(原始版本) 
void Prime_MinHeap(VertexNode *GL, int n, int v0);//Prime算法求最小生成树(优先队列版本) 
void BuildMinHeap(MinHeap que[], int n);
void MinHeapSiftDown(MinHeap que[], int n, int pos);
void MinHeapSiftUp(MinHeap que[], int n, int pos);
void ChangeKey(MinHeap que[], int pos, int weight);//将第pos个元素的关键字值改为weight 
int SearchKey(MinHeap que[], int pos, int weight);//查找最小堆中关键字值为k的元素下标,未找到则返回-1(非递归) 
int ExtractMin(MinHeap que[]);//删除并返回最小堆中具有最小关键字的元素

int main()
{
    int i, j, m, n, v0 = 0;
    VertexNode GL[MAX];
    
    printf("请输入顶点数量:"); 
    scanf("%d", &n);
    printf("\n请输入边数量:"); 
    scanf("%d", &m);
    
    CreateGraph_2(GL, n, m);//创建邻接矩阵图 
    PrintGraph(GL, n);//输出图
    Prime(GL, n, v0);//Prime算法求最小生成树(原始版本) 
    Prime_MinHeap(GL, n, v0);//Prime算法求最小生成树(优先队列版本) 

    return 0;
}

void CreateGraph(VertexNode *GL, int n, int m)//创建一个图
{
    int i, u, v, w;
    EdgeNode *e;
    
    for (i=0; i<n; i++)//初始化图 
    {
        GL[i].data = i;
        GL[i].firstEdge = NULL;
    }
    
    for (i=0; i<m; i++) //读入边信息(注意是无向图) 
    {
        scanf("%d%d%d", &u, &v, &w);
        
        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
        if (!e)
        {
            puts("Error"); 
            exit(1);
        }
        e->next = GL[u].firstEdge;
        GL[u].firstEdge = e;
        e->adjvex = v;
        e->weight = w;
        
        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
        if (!e)
        {
            puts("Error"); 
            exit(1);
        }
        e->next = GL[v].firstEdge;
        GL[v].firstEdge = e;
        e->adjvex = u;
        e->weight = w;
    }
} 

void PrintGraph(VertexNode *GL, int n)//输出图
{
    int i, j;
    EdgeNode *e;
    
    for (i=0; i<n; i++)
    {
        printf("%d: ", i);
        e = GL[i].firstEdge;
        while (e)
        {
            printf("<%d, %d> = %d  ", i, e->adjvex, e->weight);
            e = e->next;
        }
        printf("\n");
    }
    printf("\n");
} 

void CreateGraph_2(VertexNode *GL, int n, int m)//创建邻接表图(随机图) 
{
    int i, j, u, v, w;
    EdgeNode *e;
    
    for (i=0; i<n; i++)//初始化图 
    {
        GL[i].data = i;
        GL[i].firstEdge = NULL;
    }
    
    for (i=1; i<n; i++)//确保是连通图
    {
        w =  rand() % 100 + 1;
        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
        if (!e)
        {
            puts("Error"); 
            exit(1);
        }
        e->next = GL[0].firstEdge;
        GL[0].firstEdge = e;
        e->adjvex = i;
        e->weight = w;
        
        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
        if (!e)
        {
            puts("Error"); 
            exit(1);
        }
        e->next = GL[i].firstEdge;
        GL[i].firstEdge = e;
        e->adjvex = 0;
        e->weight = w;
    } 
    
    m -= n - 1;
    while (m > 0)
    {
        for (i=0; i<n; i++) 
        {
            for (j=i+1; j<n; j++)
            {
                if (rand()%10 == 0) //有10%的概率出现边
                {
                    if (!Locate(GL, i, j))
                    {
                        w =  rand() % 100 + 1;
                        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
                        if (!e)
                        {
                            puts("Error"); 
                            exit(1);
                        }
                        e->next = GL[i].firstEdge;
                        GL[i].firstEdge = e;
                        e->adjvex = j;
                        e->weight = w;
                        
                        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
                        if (!e)
                        {
                            puts("Error"); 
                            exit(1);
                        }
                        e->next = GL[j].firstEdge;
                        GL[j].firstEdge = e;
                        e->adjvex = i;
                        e->weight = w;
                        
                        m--;
                        if (m == 0)
                            return;
                    }
                } 
            }
        }
    }
} 

int Locate(VertexNode *GL, int u, int v)//判断u,v是否是邻接点 
{
    EdgeNode *e = GL[u].firstEdge;

    while (e)
    {
        if (e->adjvex == v)
            return 1;
        e = e->next;
    }
    return 0;
}

void DestroyGL(VertexNode *GL, int n)
{
    int i;
    EdgeNode *e, *q;
    
    for (i=0; i<n; i++)
    {
        e = GL[i].firstEdge;
        do
        {
            q = e->next;
            free(e);
            e = q;
        } while (e);
        GL[i].firstEdge = NULL;
    }
}

void Prime(VertexNode *GL, int n, int v0)//Prime算法求最小生成树(原始版本) 
{
    int book[MAX] = {0}; //标记该顶点是否已经在路径中 
    int dic[MAX] = {0}; //存储顶点到最小生成树的距离 
    int adj[MAX] = {0}; //存储顶点在最小生成树树中的邻接点序号 
    int min, i, j, k;
    EdgeNode *e;
    
    for (i=0; i<n; i++) //初始化工作 
    {
        dic[i] = INFINITY;
        adj[i] = v0;
    }
    dic[v0] = 0;
    book[v0] = 1;
    
    for (i=0; i<n; i++) //每趟确定一个新顶点,共n趟 
    {
        min = INFINITY;
        k = v0;
        for (j=0; j<n; j++)//找出离最小生成树最近的顶点k 
        {
            if (book[j] == 0 && dic[j] < min)
            {
                min = dic[j];
                k = j;
            }
        }
        
        book[k] = 1;       printf("<%d, %d> = %d   ", adj[k], k, dic[k]);
        
       for (e=GL[k].firstEdge; e; e=e->next)//更新与顶点k的邻接点的dic[]值 
        {
            j = e->adjvex;
            if (book[j] == 0 && dic[j] > e->weight)
            {
                dic[j] = e->weight;
                adj[j] = k;
            }
        }
    }
    
    min = 0;
    for (i=0; i<n; i++) //输出各顶点在最小生成树中的邻接点及边的长度 
    {
//        printf("<%d, %d> = %d\n", adj[i], i, dic[i]);
        min += dic[i];
    }    
    printf("最小生成树总长度(权值)为 %d\n", min); 
}

void Prime_MinHeap(VertexNode *GL, int n, int v0)//Prime算法求最小生成树(优先队列版本) 
{
    int book[MAX] = {0}; //标记该城市是否已经在路径中 
    int dic[MAX] = {0}; //存储顶点到最小生成树的距离 
    int adj[MAX] = {0}; //存储顶点在最小生成树树中的邻接点序号 
    MinHeap que[MAX+1];//最小堆用来存储顶点序号和到最小生成树的距离 
    int min, i, j, k, pos;
    EdgeNode *e;
    
    que[0].num = n; //存储最小堆中的顶点数量 
    for (i=0; i<n; i++) //初始化工作 
    {
        dic[i] = INFINITY;
        adj[i] = v0;
        que[i+1].num = i;
        que[i+1].w = dic[i];
    }
    dic[v0] = 0;
    book[v0] = 1;
    BuildMinHeap(que, n);//构造一个最小堆 

    for (i=0; i<n; i++) //每趟确定一个新顶点,共n趟 
    {
        k = ExtractMin(que);//删除并返回最小堆中具有最小关键字的元素    
        book[k] = 1;   printf("<%d, %d> = %d   ", adj[k], k, dic[k]);
        
        for (e=GL[k].firstEdge; e; e=e->next)//更新与顶点k的邻接点的dic[]值 
        {
            j = e->adjvex;
            if (book[j] == 0 && dic[j] > e->weight)
            {
                pos = SearchKey(que, j, dic[j]);    
                dic[j] = e->weight;
                adj[j] = k;                
                ChangeKey(que, pos, dic[j]);//将第pos个元素的关键字值改为weight  
            }
        }
    }
    
    min = 0;
    for (i=0; i<n; i++) //输出各顶点在最小生成树中的邻接点及边的长度 
    {
//        printf("<%d, %d> = %d\n", adj[i], i, dic[i]);
        min += dic[i];
    }    
    printf("最小生成树总长度(权值)为 %d\n", min); 
}

int ExtractMin(MinHeap que[])//删除并返回最小堆中具有最小关键字的元素
{  
    int pos = que[1].num;  
    
    que[1] = que[que[0].num--];
    MinHeapSiftDown(que, que[0].num, 1);  
      
    return pos;  
}  

int SearchKey(MinHeap que[], int pos, int weight)//查找最小堆中关键字值为k的元素下标,未找到则返回-1(非递归) 
{
    int Stack[MAX] = {0};
    int i = 1, top = -1;
    
    while ((i <= que[0].num && que[i].w <= weight) || top >= 0)//类似先序遍历二叉树的方式查找 
    {
        if (i <= que[0].num && que[i].w <= weight)
        {
            if (que[i].w == weight && que[i].num == pos)//权值与顶点序号都必须对应 
                return i;
            Stack[++top] = i;//该结点入栈 
            i *= 2; //搜索左孩子 
        }
        else
        {
            i = Stack[top--] * 2 + 1; //结点退栈并搜索右孩子 
        }
    }
    
    return -1;
}

void ChangeKey(MinHeap que[], int pos, int weight)//将第pos个元素的关键字值改为weight  
{  
    if (weight < que[pos].w) //关键字值变小,向上调整最小堆   
    {  
        que[pos].w = weight;  
        MinHeapSiftUp(que, que[0].num, pos);    
    }  
    else if (weight > que[pos].w)  //关键字值变大,向下调整最小堆   
    {  
        que[pos].w = weight;   
        MinHeapSiftDown(que, que[0].num, pos);      
    }     
} 

void MinHeapSiftDown(MinHeap que[], int n, int pos)  //向下调整结点 
{  
    MinHeap temp = que[pos];  
    int child = pos * 2; //指向左孩子   
      
    while (child <= n)  
    {  
        if (child < n && que[child].w > que[child+1].w) //有右孩子,且右孩子更小些,定位其右孩子   
            child += 1;  
          
        if (que[child].w < temp.w) //通过向上移动孩子结点值的方式,确保双亲小于孩子   
        {  
            que[pos] = que[child];   
            pos = child;  
            child = pos * 2;  
        }  
        else  
            break;  
    }  
    que[pos] = temp; //将temp向下调整到适当位置   
}  

void MinHeapSiftUp(MinHeap que[], int n, int pos)  //向上调整结点 
{  
    MinHeap temp = que[pos];  
    int parent = pos / 2; //指向双亲结点  
      
    if (pos > n) //不满足条件的元素下标   
        return;  
      
    while (parent > 0)  
    {  
        if (que[parent].w > temp.w) //通过向下移动双亲结点值的方式,确保双亲小于孩子   
        {  
            que[pos] = que[parent];   
            pos = parent;  
            parent = pos / 2;     
        }  
        else  
            break;  
    }  
    que[pos] = temp; //将temp向上调整到适当位置   
}  


void BuildMinHeap(MinHeap que[], int n)//构造一个最小堆 
{
    int i;
    
    for (i=n/2; i>0; i--)
    {
        MinHeapSiftDown(que, n, i);
    }
}


[ 本帖最后由 巧若拙 于 2014-11-26 18:41 编辑 ]
2014-11-26 18:40
soulmate1023
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:6
帖 子:256
专家分:831
注 册:2014-9-23
  得分:10 
赞一个!
2014-11-27 09:35
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
  得分:0 
再补充一个:最小生成树( 克鲁斯卡尔算法)
程序代码:
/*
    Name: 
    Copyright: 
    Author: 
    Date: 01-12-14 20:17
    Description: 最小生成树( 克鲁斯卡尔算法)
    关于并查集的算法,参见《一种简单而有趣的数据结构——并查集》http://blog./qiaoruozhuo/article/details/39674991 
*/
#include<stdio.h>
#include<stdlib.h>

#define MAXN 1000   //最大顶点数量 
#define MAX 20000   //最大边数量 
#define INFINITY 999999   //无穷大 

int map[MAX][MAX] = {0};//邻接矩阵存储图信息 

typedef struct EdgeNode{ //三元组边表集 
    int u, v;  //弧尾和弧头 
    int w; //权值,对于非网图可以不需要 
} EdgeNode;

void CreatGraph(EdgeNode *E, int m);//创建三元组边表集图 
void CreatGraph_2(EdgeNode *E, int m, int n);//创建邻接矩阵图(随机图) 
int Locate(EdgeNode *E, int n, int u, int v);//判断u,v是否是邻接点 
void PrintGraph(EdgeNode *E, int m);//输出图
int cmp (const void *a , const void *b);//快排的配套函数 
int FindFatherAndReducePath(int father[], int pos);//查找族长并压缩路径:找到族长后,将所途经的前辈结点均指向族长
int UnionBySize(int father[], int posI, int posJ);//按大小求并:将成员posI和posJ合并到同一个家族
void KRSL(EdgeNode *E, int m, int n);//克鲁斯卡尔算法求最小生成树

int main()
{
    EdgeNode E[MAX];
    int i, m, n;

    printf("请输入顶点数量:"); 
    scanf("%d", &n);
    printf("\n请输入边数量:"); 
    scanf("%d", &m);
    
    CreatGraph_2(E, m, n);//创建三元组边表集图 
    PrintGraph(E, m);//输出图
    qsort(E, m, sizeof(E[0]), cmp);//按照权值大小递增排序 
    PrintGraph(E, m);//输出图
    
    KRSL(E, m, n);//克鲁斯卡尔算法求最小生成树

    return 0;
}

void CreatGraph(EdgeNode *E, int m)//创建三元组边表集图 
{
    int i;
   
    printf("\n请按照a b c格式输入边信息:\n"); 
    for (i=0; i<m; i++)
    {
        scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
    }
} 

void CreatGraph_2(EdgeNode *E, int m, int n)//创建三元组边表集图 (随机图) 
{
    int i, j, top;

    for (i=1; i<n; i++)//确保是连通图
    {
        E[i-1].u = 0;
        E[i-1].v = i;
        E[i-1].w = rand() % 100 + 1;
    } 

    top = n - 1;
    while (top < m)
    {
        for (i=0; i<n; i++) 
        {
            for (j=i+1; j<n; j++)
            {
                if (rand()%100 == 0) //有10%的概率出现边
                {
                    if (!Locate(E, top, i, j))
                    {
                        E[top].u = i;
                        E[top].v = j;
                        E[top++].w = rand() % 100 + 1;
                        if (top == m)
                            return;
                    }
                } 
            }
        }
    }
} 

int Locate(EdgeNode *E, int n, int u, int v)//判断u,v是否是邻接点 
{
    int i;
    for (i=0; i<n; i++) 
    {
        if (u == E[i].u && v == E[i].v)
            return 1;
    }
    
    return 0;
}

void PrintGraph(EdgeNode *E, int m)//输出图
{
    int i;
    
    for (i=0; i<m; i++)
    {
        printf("<%d, %d> = %d\t", E[i].u, E[i].v, E[i].w);
    }
    printf("\n");
} 

int cmp (const void *a , const void *b)//快排的配套函数 
{
    return (((EdgeNode *)a)->w > ((EdgeNode *)b)->w ? 1 : -1);
}


void KRSL(EdgeNode *E, int m, int n)//克鲁斯卡尔算法求最小生成树
{
    int i, min, top = 1;
    int father[MAXN] = {0};
    EdgeNode minTree[MAXN] = {0};
    
    for (i=0; i<n; i++)//初始化每个家族的成员都是1,为便于比较,取家族成员数的相反数 
        father[i] = -1;
    
    for (i=0; i<m; i++)
    {
        if (UnionBySize(father, E[i].u, E[i].v))//判断该边的两个顶点是否已经连通,未连通则按大小求并
        {
            minTree[top].u = E[i].u;
            minTree[top].v = E[i].v;
            minTree[top++].w = E[i].w;
            
            if (top == n)//选用了n-1条边后退出循环 
                break;
        }
    }
    
    min = 0;
    for (i=1; i<top; i++) //输出各顶点在最小生成树中的邻接点及边的长度 
    {
        printf("<%d, %d> = %d\t", minTree[i].u, minTree[i].v, minTree[i].w);
        min += minTree[i].w;
    }    
    printf("\n最小生成树总长度(权值)为 %d\n", min); 
} 

int FindFatherAndReducePath(int father[], int pos)//查找族长并压缩路径:找到族长后,将所途经的前辈结点均指向族长
{
    if (father[pos] <= 0)
        return pos;
    //若自己不是族长,则找到族长后,将所途经的结点均指向族长   
    return father[pos] = FindFatherAndReducePath(father, father[pos]);
}

int UnionBySize(int father[], int posI, int posJ)//按大小求并:将成员posI和posJ合并到同一个家族
{
    //首先各自去寻找自己的族长
    int fI = FindFatherAndReducePath(father, posI);
    int fJ = FindFatherAndReducePath(father, posJ);

    if (fI == fJ) //如果是同一个族长门下,不必合并,即合并失败 
        return 0;
        
    if (father[fI] < father[fJ])
    {//如果族长fI的实力比fJ强,即|fI|>|fJ|,则fI当族长,并修改father[fI]和father[fJ]
        father[fI] += father[fJ];
        father[fJ] = fI;
    }
    else              //否则fJ当族长
    {
        father[fJ] += father[fI];
        father[fI] = fJ;
    }
    
    return 1;
}
2014-12-01 21:33







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.042907 second(s), 7 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved