首页 > 其他 > 详细

Chapter 7(图)

时间：2018-07-17 22:52:28      阅读：231      评论：0      收藏：0      [点我收藏+]
技术分享图片

1.Prim算法生成最小生成树
//Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
{
	int min,i,j,k;
	int adjvex[MAXVEX];
	int lowcost[MAXVEX];
	lowcost[0] = 0;
	

	adjvex[0] = 0;
	for(i = 1;i < G.numVertexes;i++)
	{
		lowcost[i] = G.arc[0][i];
		adjvex[i] = 0;
	}
	for(i = 1;i < G.numVertexes;i++)
	{
		min = INFINITY;

		j = 1;k = 0;
		while(j < G.numVertexes)
		{
			if(lowcost[j] != 0 && lowcost[j] < min)
			{
				min = lowcost[j];
				k = j;
			}
			j++;
		}

		printf("(%d,%d)",adjvex[k],k);
		lowcost[k] = 0;
		for(j = i;j < G.numVertexes;j++)
		{
			if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
			{
				lowcost[j] = G.arc[k][j];
				adjvex[j] = k;
			}
		}
	}
}
42
 
1
//Prim算法生成最小生成树
2
void MiniSpanTree_Prim(MGraph G)
3
{
4
    int min,i,j,k;
5
    int adjvex[MAXVEX];
6
    int lowcost[MAXVEX];
7
    lowcost[0] = 0;
8
9
10
    adjvex[0] = 0;
11
    for(i = 1;i < G.numVertexes;i++)
12
    {
13
        lowcost[i] = G.arc[0][i];
14
        adjvex[i] = 0;
15
    }
16
    for(i = 1;i < G.numVertexes;i++)
17
    {
18
        min = INFINITY;
19
20
        j = 1;k = 0;
21
        while(j < G.numVertexes)
22
        {
23
            if(lowcost[j] != 0 && lowcost[j] < min)
24
            {
25
                min = lowcost[j];
26
                k = j;
27
            }
28
            j++;
29
        }
30
31
        printf("(%d,%d)",adjvex[k],k);
32
        lowcost[k] = 0;
33
        for(j = i;j < G.numVertexes;j++)
34
        {
35
            if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
36
            {
37
                lowcost[j] = G.arc[k][j];
38
                adjvex[j] = k;
39
            }
40
        }
41
    }
42
}

2.克鲁斯卡尔（Kruskal）算法
//Kruskal算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G)
{
	int i,n,m;
	Edge edges[MAXEDGE];
	int parentp[MAXVEX];

	//省略将邻接矩阵转化为边集数组edges并按权由小到大排序的代码
	for(i = 0; i < G.numEdges;i++)
	{
		parent[i] = 0;
	}
	for(i = o;i < G.numEdges;i++)
	{
		n = Find(parent,edges[i].begin);
		m = Find(parent,edges[i].end);
		if(n != m)
		{
			parent[n] = m;
			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;
}
34
 
1
//Kruskal算法生成最小生成树
2
void MiniSpanTree_Kruskal(MGraph G)
3
{
4
    int i,n,m;
5
    Edge edges[MAXEDGE];
6
    int parentp[MAXVEX];
7
8
    //省略将邻接矩阵转化为边集数组edges并按权由小到大排序的代码
9
    for(i = 0; i < G.numEdges;i++)
10
    {
11
        parent[i] = 0;
12
    }
13
    for(i = o;i < G.numEdges;i++)
14
    {
15
        n = Find(parent,edges[i].begin);
16
        m = Find(parent,edges[i].end);
17
        if(n != m)
18
        {
19
            parent[n] = m;
20
            printf("(%d,%d) %d ",edges[i].begin,edges[i].end,edges[i].weight);
21
22
        }
23
    }
24
}
25
26
27
int Find(int *parent,int f)
28
{
29
    while(parent[f] > 0)
30
    {
31
        f = parent[f];
32
    }
33
    return f;
34
}


3.迪杰斯特拉（Dijkstra）算法
//迪杰斯特拉（Dijkstra）算法
#define MAXVEX 9
#define INFINITY 65535

typedef int Patharc[MAXVEX];
typedef int ShortPathTable[MAXVEX];


void ShortestPath_Dijkstra(MGraph G,INT V0,Patharc *P,ShortPathTable *D)
{
	int v,w,k,min;
	int final[MAXVEX];
	for(v = 0;v < G.numVertexes;v++)
	{
		final[v] = 0;
		(*D)[v] = G.arc[v0][v];
		(*P)[v] = 0;
	}
	(*D)[v0] = 0;
	final[vo] = 1;

	for(v = 1;v < G.numVertexes;w++)
	{
		min = INFINITY;
		for(w = 0;w < G.numVertexes;w++)
		{
			if(!final[w] && (*D)[w] < min)
			{
				k = w;
				min = (*D)[w];
			}
		}

		final[k] = 1;
		for(w = 0;w < G.numVertexes;w++)
		{
			if(!final[w] && (min+G.arc[k][w])< (*D)[w])
			{
				(*D)[w] = min + G.arc[k][w];
				(*P)[w] = k;
			}
		}
	}
}
44
 
1
//迪杰斯特拉（Dijkstra）算法
2
#define MAXVEX 9
3
#define INFINITY 65535
4
5
typedef int Patharc[MAXVEX];
6
typedef int ShortPathTable[MAXVEX];
7
8
9
void ShortestPath_Dijkstra(MGraph G,INT V0,Patharc *P,ShortPathTable *D)
10
{
11
    int v,w,k,min;
12
    int final[MAXVEX];
13
    for(v = 0;v < G.numVertexes;v++)
14
    {
15
        final[v] = 0;
16
        (*D)[v] = G.arc[v0][v];
17
        (*P)[v] = 0;
18
    }
19
    (*D)[v0] = 0;
20
    final[vo] = 1;
21
22
    for(v = 1;v < G.numVertexes;w++)
23
    {
24
        min = INFINITY;
25
        for(w = 0;w < G.numVertexes;w++)
26
        {
27
            if(!final[w] && (*D)[w] < min)
28
            {
29
                k = w;
30
                min = (*D)[w];
31
            }
32
        }
33
34
        final[k] = 1;
35
        for(w = 0;w < G.numVertexes;w++)
36
        {
37
            if(!final[w] && (min+G.arc[k][w])< (*D)[w])
38
            {
39
                (*D)[w] = min + G.arc[k][w];
40
                (*P)[w] = k;
41
            }
42
        }
43
    }
44
}

4.弗洛伊德（Floyd算法）
//弗洛伊德（Floyd算法）
typedef int PathMatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

void ShortestPath_Floyd(MGraph G,Pathmatirx *P,ShortPathTable *D)
{
	int v,w,k;
	for(v = 0;v < G.numVertexes; ++v)
	{
		for(w = 0;w < G.numVertexes;++w)
		{
			(*D)[v][w] = G.matirx[v][w]；
			(*P)[v][w] = w;
		}
	}

	for(k = 0;k < G.numVertexes;++k)
	{
		for(v = 0;v < G.numVertexes;++v)
		{
			for(w = 0;w < G.numVertexes;++w)
			{
				if((*D)[v][w] > (*D)[v][k]+(*D)[k][w])
				{
					(*D)[v][w] = (*D)[v][w]+(*D)[k][w];
					(*P)[v][w] = (*P)[v][k];
				}
			}
		}
	}
}



//最短路径显示代码段
for(v = 0;v < Q.numVertexes;++v)
{
	for(w = v+1;w < G.numVertexes;w++)
	{
		printf("v%d-v%d weight: %d ",v,w,D[v][w]);
		k = P[v][w];
		printf(" path: %d",v);

		while(k != w)
		{
			printf(" -> %d",k);
			k = P[k][w];
		}
		printf(" -> %d\n",w);
	}
	printf("\n");
}
x
 
1
//弗洛伊德（Floyd算法）
2
typedef int PathMatirx[MAXVEX][MAXVEX];
3
typedef int ShortPathTable[MAXVEX][MAXVEX];
4
5
void ShortestPath_Floyd(MGraph G,Pathmatirx *P,ShortPathTable *D)
6
{
7
    int v,w,k;
8
    for(v = 0;v < G.numVertexes; ++v)
9
    {
10
        for(w = 0;w < G.numVertexes;++w)
11
        {
12
            (*D)[v][w] = G.matirx[v][w]；
13
            (*P)[v][w] = w;
14
        }
15
    }
16
17
    for(k = 0;k < G.numVertexes;++k)
18
    {
19
        for(v = 0;v < G.numVertexes;++v)
20
        {
21
            for(w = 0;w < G.numVertexes;++w)
22
            {
23
                if((*D)[v][w] > (*D)[v][k]+(*D)[k][w])
24
                {
25
                    (*D)[v][w] = (*D)[v][w]+(*D)[k][w];
26
                    (*P)[v][w] = (*P)[v][k];
27
                }
28
            }
29
        }
30
    }
31
}
32
33
34
35
//最短路径显示代码段
36
for(v = 0;v < Q.numVertexes;++v)
37
{
38
    for(w = v+1;w < G.numVertexes;w++)
39
    {
40
        printf("v%d-v%d weight: %d ",v,w,D[v][w]);
41
        k = P[v][w];
42
        printf(" path: %d",v);
43
44
        while(k != w)
45
        {
46
            printf(" -> %d",k);
47
            k = P[k][w];
48
        }
49
        printf(" -> %d\n",w);
50
    }
51
    printf("\n");
52
}

附件列表

 

Chapter 7(图)

原文：https://www.cnblogs.com/LyndonMario/p/9326355.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！