图论方面的算法设计 (荐)

dcyu

另外再补充一个Kruskal算法，这是偶去年准备的，此外图论的算法还有很多，比如网络流算法
二分图匹配算法，更深的有偶今年3月用半个月写的TSP的遗传算法。图论很多问题都有很好的模型可以解决。所以碰到图论问题，很多时候会有很基础的算法可以借鉴，但是竞赛的时候更多的是加入一些限制条件，在这种情况下，就应当头脑中清楚这些算法的推导过程，知道本质才能应用的游刃有余。
/*
Author: dcyu
Date: 2002-09-11
*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

int Max(int a,int b)
{
return a>b?a:b;

}

int Min(int a,int b)
{
return a<b?a:b;

}

void main()
{
float data[20][3] = {{1, 2, 10}, {1, 3, 9.8}, {1, 5, 7.0}, {1, 9, 3.7}, {2, 4, 5.7},
{2, 6, 6}, {2, 10, 10.0}, {3, 4, 3.5}, {3, 6, 7.7}, {3, 8, 8.8}, {3, 10, 4},
{4, 6, 12}, {4, 7, 13}, {4, 8, 3.9}, {5, 6, 4.9}, {5, 8, 4.5}, {6, 9, 1.8},
{7, 10, 12}, {8, 9, 9}, {9, 10, 20.0}};

int i,j,k,m,n=20,v=10;
int flag[11],tree[20];
int min,max;
float t,tt;


for(i=0;i<n-1;i++)
{
  k=i;
  for(j=i+1;j<n;j++)
    if(data[j][2]<data[k][2]) k=j;
  if(k!=i)
    for(m=0;m<=1;m++)
    { tt=data[m]; data[m]=data[k][m]; data[k][m]=tt; }
      t=data[2]; data[2]=data[k][2]; data[k][2]=t;

}

system("cls");

printf("Graph:\n");
j=0;
for(i=0;i<n;i++)
{
  j++;
  printf("%2d: %2d ---- %2d %8.2f\n",j,(int)data[0],(int)data[1],data[2]);

}

for(i=0;i<v;i++)
   flag=i;
for(i=0;i<n;i++)
   tree=0;

for(i=0;i<n;i++)
{
   if(flag[(int)data[0]]!=flag[(int)data[1]])
   {
     tree=1;
     max=Max(flag[(int)data[0]],flag[(int)data[1]]);
     min=Min(flag[(int)data[0]],flag[(int)data[1]]);
     for(j=1;j<=v;j++)
       if(flag[j]==max)
         flag[j]=min;
   }

}

printf("Kruskal MiniSpanTree:\n");

j=0;
for(i=0;i<n;i++)
   if(tree)
   {
     j++;
     printf("%d: %2d ---- %2d %8.2f\n",j,(int)data[0],(int)data[1],data[2]);

   }


}

abcdefg12345

图论有那么重要啊，我们学校怎么没有教啊，我对这方面的知识可什么都不理解啊！
如果自学图论困难大吗？

dcyu

数学建模不教图论是不行的，你看过去很多考题都和图论有关，图论的东西学起来主要先掌握一些基本算法，然后是根据算法会写出程序，要学好不易啊。

happy2003

是的，图论是非常重要的，我们现在就在强化

scfcg

图论的确比较重要，它能解决很多实际问题，而且，所得结果也比较优。但是，它学起来可不是一件容易的事，我看了一些书，连一些最基本的定义我都要看它几次。唉！

onward

图论越往后看越难，有时找个人问一问都难

飞云0616

找谁啊

飞云0616

我们不是有老师的吗
他们厉害啊

飞云0616

一般的学校都有这个方面的老师的

mengze2001

在求最短路的基础上，大家还要对求解最有哈密尔顿圈这种np问题思考一下，《网络算法与复杂性理论》（国防科技大学研究生教材）中提供了几种近似算法，可尝试编一下程序
在这个实际问题中，一种方法为实现将网络图画分为三个部分，分别求每一部分最有哈密尔顿圈及权重和，若三个和十分不均匀，则再稍微调整一下图的划分
我编了一个三边交换调整法求最优哈密尔顿圈的程序，结果还不错。