贪心算法的几个应用

野性酷女 2022-03-20 03:15 270阅读 0赞

具体代码：

dijktra：

设邻接矩阵：a\[\]\[\]，有n个节点。

1.初始化：dist\[i\] = a\[v\]\[i\]，原始集合中只有v。

2.取dist的最小值，加入原始集合中，更新其他dist，更新n-1次

具体代码如下：

/\*

0 10 10000 30 100

10000 0 50 10000 10000

10000 10000 0 10000 10

10000 10000 20 0 60

10000 10000 10000 10000 0

\*/

\#include<stdio.h>

\#include<stdlib.h>

\#define NUM 10

\#define MAX\_VALUE 10000

int dist\[NUM\];

int s\[NUM\];

int pre\[NUM\];

void  dijkstra(int v,int a\[NUM\]\[NUM\], int n)\{

//初始化

int i=1,j=1;

for(i=1; i<=n; i++)\{

dist\[i\] = a\[v\]\[i\];

s\[i\] = false;

if(a\[v\]\[i\] == MAX\_VALUE)\{

pre\[i\] = 0;

\}else\{

pre\[i\] = v;

s\[v\] = true;

dist\[v\] = 0;

//更新n-1次

int min = 0,tmp=v;

for(i=1; i<n; i++)\{

//找最小的dist

min = MAX\_VALUE;

for(j=1; j<=n; j++)\{

if(!s\[j\] && min>dist\[j\])\{

min = dist\[j\];

tmp = j;

s\[tmp\] = true;   //tmp的初始值是v，不能为0或者随意

//用最小的dist更新已有的dist

for(j=1; j<=n; j++)\{

if(!s\[j\] && a\[tmp\]\[j\] < MAX\_VALUE && (dist\[tmp\]+a\[tmp\]\[j\] < dist\[j\]))\{

dist\[j\] = dist\[tmp\]+a\[tmp\]\[j\];

pre\[j\] = tmp;

int main()\{

int i=1,j=1,v,n,a\[NUM\]\[NUM\];

//输入邻接矩阵

scanf("%d",&n);

for(i=1; i<=n; i++)\{

for(j=1; j<=n; j++)\{

scanf("%d",&a\[i\]\[j\]);

//输入起始节点

scanf("%d",&v);

//计算dijkstra

dijkstra(v,a,n);

//打印源点到各点的最短距离

int tmp = 0;

for(i=1; i<=n; i++)\{

printf("从%d到%d的距离是%d\\n",v,i,dist\[i\]);

tmp = i;

printf("从%d到%d的最短路经过:");

while(pre\[tmp\]>0 && pre\[tmp\] != v)\{

printf("%d ",pre\[tmp\]);

tmp = pre\[tmp\];

printf("%d\\n",v);

system("pause");

return 0;

时间复杂度分析：使用邻接矩阵，o(n\*n)

最小生成树：prim

/\*  
6  
0 6 1 5 10000 10000  
6 0 5 10000 3 10000  
1 5 0 5 6 1  
5 10000 5 0 10000 2  
10000 3 6 10000 0 6  
10000 10000 1 2 6 0

\*/

\#include<stdio.h>  
\#include<stdlib.h>

\#define NUM 10  
\#define MAX\_VALUE 10000  
   
int closest\[NUM\];  //closest\[j\]记录j和S中的邻接节点中距离最近的节点  
int lowcost\[NUM\];  //lowcost\[j\]记录j和S中最近邻接点的距离  
int s\[NUM\];        //s\[j\] = true，标记j在S中

int prim(int a\[NUM\]\[NUM\],int n)\{  
    //初始化  
    int i,j,sum=0;  
    for(i=1; i<=n; i++)\{  
             closest\[i\] = 1;  
             lowcost\[i\] = a\[i\]\[1\];  
             s\[i\] = false;  
    \}  
    s\[1\] = true;

for(j=1; j<n; j++)\{  
        //寻找离S中节点最近的节点及距离  
        int min = MAX\_VALUE,v=1;  
        for(i=1; i<=n; i++)\{  
             if(!s\[i\] && min > lowcost\[i\])\{  
                      min = lowcost\[i\];  
                      v = i;  
             \}  
        \}  
        s\[v\] = true;  
        sum += lowcost\[v\];  
     
        //每添加一个新的节点到S，比较节点i和S中以前节点的最短距离 和 i和新增节点的最短距离，更新closest和c  
        for(i=1; i<=n; i++)\{  
             if(!s\[i\] && a\[i\]\[v\] < lowcost\[i\])\{  
                      lowcost\[i\] = a\[i\]\[v\];  
             \}  
        \}             
    \}      
     
    return sum;                    
     
\}

int main()\{  
    int i=1,j=1,n,a\[NUM\]\[NUM\];  
     
    //输入邻接矩阵  
    scanf("%d",&n);  
    for(i=1; i<=n; i++)\{  
       for(j=1; j<=n; j++)\{  
           scanf("%d",&a\[i\]\[j\]);  
       \}  
    \}  
     
    printf("%d",prim(a,n));  
     
    system("pause");  
    return 0;  
\}

时间复杂度是：o(n\*n)。

说明：最小生成树prim和dijkstra相似，dijkstra保存了各点和源点的最近距离(dist)，prim保存了各点和S中节点的最近邻接点及和最近邻接点的距离(closest, lowcost)。程序的书写过程相似，先初始化，再找最小的距离，再更新数组。

代码的注释我写得很详细，方便理解，有几点需要说明一下。

1、2个for循环都是从2开始的，因为一般我们默认开始就把第一个节点加入生成树，因此之后不需要再次寻找它。

2、lowcost\[i\]记录的是以节点i为终点的最小边权值。初始化时因为默认把第一个节点加入生成树，因此lowcost\[i\] = graph\[1\]\[i\]，即最小边权值就是各节点到1号节点的边权值。

3、mst\[i\]记录的是lowcost\[i\]对应的起点，这样有起点，有终点，即可唯一确定一条边了。初始化时mst\[i\] = 1，即每条边都是从1号节点出发。

编写程序:对于如下一个带权无向图，给出节点个数以及所有边权值，用Prim算法求最小生成树。![1363613840_9313.jpg][]

输入数据:

7 11  
A B 7  
A D 5  
B C 8  
B D 9  
B E 7  
C E 5  
D E 15  
D F 6  
E F 8  
E G 9  
F G 11

输出:

A - D : 5  
D - F : 6  
A - B : 7  
B - E : 7  
E - C : 5  
E - G : 9  
Total:39

#include <stdio.h>
    #include <stdlib.h>
     
    #define MAX 100
    #define MAXCOST 0x7fffffff
     
    int graph[MAX][MAX];
     
    int Prim(int graph[][MAX], int n)
    {
    	/* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */
    	int lowcost[MAX];
     
    	/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */
    	int mst[MAX];
     
    	int i, j, min, minid, sum = 0;
     
    	/* 默认选择1号节点加入生成树，从2号节点开始初始化 */
    	for (i = 2; i <= n; i++)
    	{
    		/* 最短距离初始化为其他节点到1号节点的距离 */
    		lowcost[i] = graph[1][i];
     
    		/* 标记所有节点的起点皆为默认的1号节点 */
    		mst[i] = 1;
    	}
     
    	/* 标记1号节点加入生成树 */
    	mst[1] = 0;
     
    	/* n个节点至少需要n-1条边构成最小生成树 */
    	for (i = 2; i <= n; i++)
    	{
    		min = MAXCOST;
    		minid = 0;
     
    		/* 找满足条件的最小权值边的节点minid */
    		for (j = 2; j <= n; j++)
    		{
    			/* 边权值较小且不在生成树中 */
    			if (lowcost[j] < min && lowcost[j] != 0)
    			{
    				min = lowcost[j];
    				minid = j;
    			}
    		}
    		/* 输出生成树边的信息:起点，终点，权值 */
    		printf("%c - %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min);
     
    		/* 累加权值 */
    		sum += min;
     
    		/* 标记节点minid加入生成树 */
    		lowcost[minid] = 0;
     
    		/* 更新当前节点minid到其他节点的权值 */
    		for (j = 2; j <= n; j++)
    		{
    			/* 发现更小的权值 */
    			if (graph[minid][j] < lowcost[j])
    			{
    				/* 更新权值信息 */
    				lowcost[j] = graph[minid][j];
     
    				/* 更新最小权值边的起点 */
    				mst[j] = minid;
    			}
    		}
    	}
    	/* 返回最小权值和 */
    	return sum;
    }
     
    int main()
    {
    	int i, j, k, m, n;
    	int x, y, cost;
    	char chx, chy;
     
    	/* 读取节点和边的数目 */
    	scanf("%d%d", &m, &n);
    	getchar();
     
    	/* 初始化图，所有节点间距离为无穷大 */
    	for (i = 1; i <= m; i++)
    	{
    		for (j = 1; j <= m; j++)
    		{
    			graph[i][j] = MAXCOST;
    		}
    	}
     
    	/* 读取边信息 */
    	for (k = 0; k < n; k++)
    	{
    		scanf("%c %c %d", &chx, &chy, &cost);
    		getchar();
    		i = chx - 'A' + 1;
    		j = chy - 'A' + 1;
    		graph[i][j] = cost;
    		graph[j][i] = cost;
    	}
     
    	/* 求解最小生成树 */
    	cost = Prim(graph, m);
     
    	/* 输出最小权值和 */
    	printf("Total:%d\n", cost);
     
    	//system("pause");
    	return 0;	
    }

![1363613947_4360.jpg][]

今天从志权师兄那里学会了最小生成树。所谓生成树，就是n个点之间连成n-1条边的图形。而最小生成树，就是权值（两点间直线的值）之和的最小值。

首先，要用二维数组记录点和权值。如上图所示无向图：

int map\[7\]\[7\];  
       map\[1\]\[2\]=map\[2\]\[1\]=4;  
       map\[1\]\[3\]=map\[3\]\[1\]=2;  
       ......

然后再求最小生成树。具体方法是：

1.先选取一个点作起始点，然后选择它邻近的权值最小的点（如果有多个与其相连的相同最小权值的点，随便选取一个）。如1作为起点。

visited\[1\]=1;

pos=1;

//用low\[\]数组不断刷新最小权值，low\[i\](0<i<=点数)的值为：i点到邻近点（未被标记）的最小距离。

low\[1\]=0;  //起始点i到邻近点的最小距离为0

low\[2\]=map\[pos\]\[2\]=4;

low\[3\]=map\[pos\]\[3\]=2;

low\[4\]==map\[pos\]\[4\]=3;

low\[5\]=map\[pos\]\[5\]=MaxInt;  //无法直达

low\[6\]=map\[pos\]\[6\]=MaxInt;

2.再在伸延的点找与它邻近的两者权值最小的点。

//low\[\]以3作当前位置进行更新

visited\[3\]=1;

pos=3;

low\[1\]=0;   //已标记，不更新

low\[2\]=map\[1\]\[2\]=4;  //比5小，不更新

low\[3\]=2;  //已标记，不更新

low\[4\]=map\[1\]\[4\]=3;   //比1大，更新后为：low\[4\]=map\[3\]\[4\]=1;

low\[5\]=map\[1\]\[5\]=MaxInt;//无法直达，不更新

low\[6\]=map\[1\]\[6\]=MaxInt;//比2大，更新后为：low\[6\]=map\[3\]\[6\]=2;

3.如此类推...

![1363614002_4428.jpg][]

当所有点都连同后，结果最生成树如上图所示。

所有权值相加就是最小生成树，其值为2+1+2+4+3=12。

至于具体代码如何实现，现在结合POJ1258例题解释。代码如下：

`  `

#include <stdio.h>
    
    #include <string.h>
    
    #define MaxInt 0x3f3f3f3f
    
    #define N 110
    
    //创建map二维数组储存图表，low数组记录每2个点间最小权值，visited数组标记某点是否已访问
    
    int map[N][N],low[N],visited[N];
    
    int n;
    
     
    
    int prim()
    
    {
    
        int i,j,pos,min,result=0;
    
        memset(visited,0,sizeof(visited));
    
    //从某点开始，分别标记和记录该点
    
        visited[1]=1;pos=1;
    
    //第一次给low数组赋值
    
        for(i=1;i<=n;i++)
    
            if(i!=pos) low[i]=map[pos][i];
    
    //再运行n-1次
    
        for(i=1;i<n;i++)
    
        {
    
    //找出最小权值并记录位置
    
         min=MaxInt;
    
         for(j=1;j<=n;j++)
    
             if(visited[j]==0&&min>low[j])
    
             {
    
                 min=low[j];pos=j;
    
             }
    
    //最小权值累加
    
        result+=min;
    
    //标记该点
    
        visited[pos]=1;
    
    //更新权值
    
        for(j=1;j<=n;j++)
    
            if(visited[j]==0&&low[j]>map[pos][j])
    
                low[j]=map[pos][j];
    
        }
    
        return result;
    
    }
    
     
    
    int main()
    
    {
    
        int i,v,j,ans;
    
        while(scanf("%d",&n)!=EOF)
    
        {
    
    //所有权值初始化为最大
    
            memset(map,MaxInt,sizeof(map));
    
            for(i=1;i<=n;i++)
    
                for(j=1;j<=n;j++)
    
                {
    
                    scanf("%d",&v);
    
                    map[i][j]=map[i][j]=v;
    
                }
    
                ans=prim();
    
                printf("%d\n",ans);
    
        }
    
        return 0;
    
    }

[1363613840_9313.jpg]: https://img-my.csdn.net/uploads/201303/18/1363613840_9313.jpg
[1363613947_4360.jpg]: https://img-my.csdn.net/uploads/201303/18/1363613947_4360.jpg
[1363614002_4428.jpg]: https://img-my.csdn.net/uploads/201303/18/1363614002_4428.jpg