図論関連アルゴリズムの要約(二)
3219 ワード
一.最小生成ツリー(Kruscalアルゴリズム)
二.最小生成ツリー(Primアルゴリズム)
三.シングルソース最短パス(Dijkstraアルゴリズム)
#include "iostream"
#include "cstdlib"
#include "cstring"
#include "cstdio"
#define N 10000
#define M 100000
using namespace std;
struct edge //
{
int start; //
int end; //
int weight; //
}e[M];
int n,m; // ,
int cmp(const void *a,const void *b);//
void kruscal(int *sum);
int main(){
//freopen("a.txt","r",stdin);
int i,sum;
cin>>n>>m;
for(i=0;i>e[i].start>>e[i].end>>e[i].weight;//
kruscal(&sum);
cout<weight - ((struct edge*)b)->weight ;
}
void kruscal(int *sum){
int i,k,g,x[N],num;
for(i=1;i<=n;i++)
x[i]=i;
qsort(e,m,sizeof(e[0]),cmp); //
*sum=num=0;
for(i=0;i
二.最小生成ツリー(Primアルゴリズム)
#include "iostream"
#include "cstdio"
#define M 100000 //
#define N 10000 //
#define INF 100000
using namespace std;
struct edge{ //
int start; //
int end; //
int weight; //
}e[M];
int n,m; //
int getWeight(int v,int w); // w v
void prim(int fa[],int *sum);
int main(void)
{
//freopen("a.txt","r",stdin);
int sum; //
int i;
cin>>n>>m;
for(i=0; i>e[i].start>>e[i].end>>e[i].weight;
int fa[N];
prim(fa,&sum);
cout<getWeight(k,j) && d[j] != 0){
d[j] = getWeight(k,j);
fa[j] = k;
}
}
}
三.シングルソース最短パス(Dijkstraアルゴリズム)
#include"iostream"
#include"cstdlib"
#include"cstdio"
#include"cstring"
#define N 100 //
#define M 10000 //
#define INF 1000000 //
using namespace std;
typedef struct node //
{
int adjvex;
int weight;
node* next;
}EdgeNode;
EdgeNode * node[N+1]; //node[i] i , 1
int D[N+1]; //
int p[N+1][N+1]; //
int final[N+1]; // final[i] = 1 vi S
int n,m; //
void Dijkstra(int v); // DijKstra
int getWeight(int v,int w); // v w
int main()
{
//freopen("a.txt","r",stdin);
int i;
EdgeNode *s;
cin>>n>>m;
for(i=1; i>x>>y>>z;
s = (EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex = y; //
s->weight = z;
s->next = node[x];
node[x] = s;
s = (EdgeNode*)malloc(sizeof(EdgeNode)); // ,
s->adjvex = x;
s->weight = z;
s->next = node[y];
node[y] = s;
}
int v0=1;
Dijkstra(v0);
for(i=1;i<=n;i++){
cout<"<adjvex==w)
return p->weight;
p=p->next;
}
return INF;
}