图论板子dijkstra,Floyd,prime,bfs,dfs, krustral

待我称王封你为后i 2022-04-23 03:22 172阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    void bfs(){
    	for(int i=1;i<=n;i++)v[i]=0;
    	queue<Node> q;
    	for(int i=1;i<=number;i++){
    		if(!v[i]){
    			q.push(i);
    			while(!q.empty()){
    				e=q.front();
    				q.pop();
    				for(){//遍历邻接点加入到队列中 
    				}
    			}
    		}
    	}
    }
    void mst_prime(){
    	for(int i=1;i<=n;i++){
    		cost[i]=inf;
    		used[i]=0;
    	}
    	cost[1]=0;
    	int res=0;
    	while(1){
    		int v=-1;
    		for(int i=1;i<=n;i++)
    			if(!used[i]&&(v==-1||cost[i]<cost[v]))
    				v=i;
    		if(v==-1)break;
    		res+=cost[v];
    		used[v]=1;
    		for(u遍历v的所有邻接点)
    			if(!used[u])
    				cost[u]=min(cost[u],cost[v]+G[v][u]);
    	}	
    	cout<<res;
    }
    
    void kudikaer(){//设edge[]是存放边的结构体数组,一共有m条边 
    	for(int i=1;i<=n;i++)
    		used[i]=0;
    	int res=0;
    	sort(edge,edge+m);//吧边从小到大排序 
    	for(int i=1;i<=m;i++){
    		if(sed[edge[i].pre]==0||used[edge[i].end]==0;){
    			used[edge[i].pre]=used[edge[i].end]=1;
    			res+=edge[i].cost;
    		}
    	}
    	cout<<res;//克鲁笛卡尔是把所有边都排一下序，然后进行最小生成树的筛选 
    }
    void dijisitla(){//迪杰斯特拉算法：单源最短路径 (和普利姆算法差不多)
    	for(int i=1;i<=n;i++){
    		d[i]=inf;
    		used[i]=0;
    	}
    	d[1]=0;
    	while(1){
    		int v=-1;
    		for(int u=1;u<=n;u++)
    			if(!used[i]&&(v==-1||d[u]<d[v]))
    				v=u;
    		if(v==-1)break;
    		used[v]=1;
    		for(int i=1;i<=n;i++)\
    			d[i]=min(d[i],d[v]+G[v][i]);		
    	}
    	for(int i=1;i<=n;i++)cout<<d[i];
    } 
    void floyd(){//弗洛伊德五行算法。 
    	for(int k=1;k<=n;k++)
    		for(int i=1;i<=n;i++)
    			for(int j=1;j<=n;j++)
    				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    } 
    void  dfs(int x){
    	for(遍历x的邻接点u){
    		if(!used[u]){
    			used[u]=1;
    			要进行的操作；
    			 dfs(u); 
    		}	
    	} 
    } 
    void bfs(int x){
    	queue<Node> q;
    	q.push(x);
    	while(!q.empty()){
    		Node e=q.front();
    		q.pop();
    		for(遍历e的邻接点){
    			if(!used[i]){
    				used[i];
    				bfs要进行的操作； 
    				q.push(i);			
    			}
    		} 
    	}	
    }
    void monst(){
    	for(int i=1;i<=n;i++)used[i]=0;
    	for(int i=1;i<=n;i++)
    		if(!used[i]){
    			used[u]=1;
    			要进行的操作；
    			 dfs(u); 
    	}
    		
    	for(int i=1;i<=n;i++)
    		used[i]=0;
    	for(int i=1;i<=n;i++){
    		if(!used){
    			bfs(i);
    		}
    	}
    }