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

Sambuke

// 单源最短路径
// Dijsktra.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream infile("dijsktra.in");
ofstream outfile("dijsktra.out");

const int ub = 10;
const int inf = 10000000;
int n;
int nEdge;
int dest;
int original[ub][ub];
bool s[ub];
int d[ub];
int l[ub];

void initialization();
void readData();
void process();
void output();

void initialization()
{
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                {
                        original[j] = inf;
                }

        for(i=0;i<n;i++)
        {
                d = 0;
        }

}

void readData()
{
        infile>>n>>nEdge>>dest;
        dest--;
        initialization();
        for(int i=0;i<nEdge;i++)
        {
                int x,y,z;
                infile>>x>>y>>z;
                original[x-1][y-1] = z;
                original[y-1][x-1] = z;
        }
        process();
        output();
}

void process()
{
        for(int i=0;i<n;i++)
        {
                s = 0;
                l = original[dest];
        }
        s[dest] = true;
       
        for(i=0;i<n;i++)
        {
                int curMin = inf;
                int curNode = 0;
                for(int j=0;j<n;j++)
                {
                        if ((l[j] < curMin)&&(!s[j]))
                        {
                                curMin = l[j];
                                curNode = j;
                        }
                }

                s[curNode] = true;
                d[curNode] = curMin;

                cout<<curNode+1<<' '<<curMin<<endl;

                for(int k=0;k<n;k++)
                {
                        if (k!=dest)
                                cout<<l[k]<<' ';
                }
                cout<<endl;

                for(j=0;j<n;j++)
                {
                        if ((!s[j])&&(l[j]>original[curNode][j]+l[curNode]))
                        {
                                l[j] = original[curNode][j]+l[curNode];
                        }
                }
       
        }



       
}

void output()
{
        for(int i=0;i<n;i++)
        {
                if (i!=dest)
                {
                        cout<<d<<' ';
                }
        }
        cout<<endl;
}

int main(int argc, char* argv[])
{
        readData();
        return 0;
}

Sambuke

// 最小生成树
// Prim.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream infile("prim.in");
ofstream outfile("prim.out");

const int inf = 1000000;
const int ub = 10;
int n;
int nEdge;
int original[ub][ub];
bool s[ub];
int l[ub];
int result[ub];

void initialization();
void readData();
void process();
void output();

void initialization()
{
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                {
                        original[j] = inf;
                }
        for(i=0;i<n;i++)
        {
                s = false;
                l = 0;
                result = 0;
        }
}

void readData()
{
        infile>>n>>nEdge;
        initialization();
        for(int i=0;i<nEdge;i++)
        {
                int x,y,z;
                infile>>x>>y>>z;
                original[x-1][y-1] = z;
                original[y-1][x-1] = z;
        }

        process();
        output();
}

void process()
{
        // minimum cost spanning tree... Prim...

        s[0] = true;
        for(int i=1;i<n;i++)
        {
                l = original[0];
                s = false;
        }

        for(i=0;i<n-1;i++)
        {
                int curMin = inf;
                int curNode = 0;
                for(int j=0;j<n;j++)
                {
                        if ((!s[j])&&(l[j]<curMin))
                        {
                                curMin = l[j];
                                curNode = j;
                        }
                }

                s[curNode] = true;
                result = curMin;

                for(j=0;j<n;j++)
                {
                        if ((!s[j])&&(l[j] > original[j][curNode]))
                        {
                                l[j] = original[j][curNode];
                        }
                }
                       
               
        }
        // end of MST...

}

void output()
{
        for(int i=0;i<n-1;i++)
        {
                cout<<result<<' ';
        }
        cout<<endl;
}

int main(int argc, char* argv[])
{
        readData();
        return 0;
}

Sambuke

// 最小生成树
// Kruskal.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream infile("Kruskal.in");
ofstream outfile("Kruskal.out");

struct Node
{
        int x;
        int y;
        int z;
};

const int ub = 15;
const int inf = 1000000;
int n;
int nEdge;
int original[ub][ub];
int e[ub];
Node ee[ub];
int s[ub];
int r[ub];

void initialization();
void readData();
void process();
void output();

void initialization()
{
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                {
                        original[j] = inf;
                }

        for(int j=0;j<nEdge;j++)
        {
                r[j] = 0;
                s[j] = j;
                e[j] = j;
        }
}

void readData()
{
        infile>>n>>nEdge;
        initialization();
        for(int i=0;i<nEdge;i++)
        {
                int x,y,z;
                infile>>x>>y>>z;
                original[x-1][y-1] = z;
                original[y-1][x-1] = z;
                ee.x = x-1;
                ee.y = y-1;
                ee.z = z;
        }

        process();
        output();
}

bool cmp(int a,int b)
{
        return (ee[e[a]].z <= ee[e].z);
}

bool cmp2(Node a,Node b)
{
        return a.z < b.z;
}

void process()
{
        // minimum cost spanning tree... Kruskal...
        //sort(e,e+nEdge,cmp);
        sort(ee,ee+nEdge,cmp2);

        // get the lowest-weight edge...
        int f_x = ee[0].x;
        int f_y = ee[0].y;

        // merge...
        s[f_x] = s[f_y];
        r[0] = ee[0].z;
       
        int curPos = 1;

        for(int i=1;i<n-1;i++)
        {
                while(s[ee[curPos].x] == s[ee[curPos].y])
                {
                        curPos++;
                }
                int curNo = s[ee[curPos].x];
                for(int j=0;j<nEdge;j++)
                {
                        if (s[j] == curNo)
                        s[j] = s[ee[curPos].y];
                }
                r = ee[curPos].z;
        }

        // end of MST...
}

void output()
{
        for(int i=0;i<n-1;i++)
        {
                cout<<r<<' ';
        }
        cout<<endl;

}


int main(int argc, char* argv[])
{
        readData();
        return 0;
}

Sambuke

// 任意两点间最短路径
// Floyd.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

ifstream infile("TSP321.in");
ofstream outfile("Floyd.m");

const int ub = 100;
const int inf = 10000000;
int n;
int nEdge;
int original[ub][ub];

void initialization();
void readData();
void process();
void output();

void initialization()
{
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
        {
                original[j] = inf;
        }
}

void readData()
{
        infile>>n>>nEdge;
        initialization();
        for(int i=0;i<nEdge;i++)
        {
                int x,y,z;
                infile>>x>>y>>z;
                original[x-1][y-1] = z;
                original[y-1][x-1] = z;
        }

        process();
        output();
}

void process()
{
        // Floyd...
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                        for(int k=0;k<n;k++)
        {
                if ((original[j] + original[j][k] < original[k]) && (i!=j&&i!=k&&j!=k))
                {
                        original[k] = original[j]+original[j][k];
                        original[k] = original[j]+original[j][k];
                }
        }
        // end of Floyd...
}

void output()
{
        for(int i=0;i<n;i++)
        {
                for(int j=0;j<n;j++)
                {
                        outfile<<setw(3)<<original[j]<<' ';
                }
                outfile<<endl;
        }
}

int main(int argc, char* argv[])
{
        readData();
        return 0;
}

Sambuke

声明：我的程序是用Visual C++ 6.0写的，
可能不是标准的Anisi C++程序，
因为涉及到循环变量的重复定义的问题
所以特别保留了Visual C++ 6.0工程生成的注释
程序写的不好，有什么问题欢迎大家指出！谢谢

Sambuke

我的邮箱是：haomiaoforever@sohu.com
非常希望结交喜欢数模和编程的朋友！