図論関連アルゴリズムの要約(二)

3219 ワード

一.最小生成ツリー(Kruscalアルゴリズム)
#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;
}