图论模板-白红宇

图论模板

阅读量：4217 次

发布时间：2019-05-26

本文共 5960 字，大约阅读时间需要 19 分钟。

一、最小生成树

(1) prim + 邻接矩阵

int prim(int s)	{		int sum = 0; 		//memset(vis,false,sizeof(vis));		memset(dis,INF,sizeof(dis));		dis[s] = 0;		for(int i = 0; i < n; ++i){			dis[i] = map[s][i];		}		//vis[s] = true;		int cur;		for(int i = 0; i < n; ++i){			if(s == i) continue;			int min_dis = INF;			for(int j = 0; j < n; ++j){//寻找MST外距离MST最近的点 				if(dis[j] != 0 && dis[j] < min_dis){					min_dis = dis[j];					cur = j;					}			}			dis[cur] = 0;			sum += min_dis;			for(int v = 0; v < n; ++v){//更新与当前新加入点cur临接点到生成树的距离 				if(dis[v] != 0 && map[cur][v] < dis[v]){					dis[v] = map[cur][v];				}			} 		}		printf("%d\n",sum);		}

(2)prim + 邻接表

#include
    
     using namespace std;const int MAXM = 50000+5;const int MAXN = 1000+5;bool mark[MAXN];struct Edge{	int to,w;	Edge(int pt,int pw){		to = pt; w = pw;	} 	bool operator<(const Edge o)const{		return w > o.w;	}};int n,m,cnt;vector
     
       adj[MAXN];priority_queue
      
        pq;void vis(int cur){	mark[cur] = true;	++cnt;	for(int i = 0; i < adj[cur].size(); ++i){		Edge e = adj[cur][i];		if(!mark[e.to]){			pq.push(e);		}	}}void prim(int s)	{		cnt = 1;		int sum = 0;		memset(mark,false,sizeof(mark));		mark[s] = true;		for(int i = 0; i < adj[s].size(); ++i){			pq.push((Edge)adj[s][i]);		}		int to;		while(cnt < n){			Edge e = pq.top();			pq.pop();			to = e.to;			if(mark[to]) continue;						sum += e.w;			vis(to);		}					printf("%d\n",sum);	}int main()	{		cin >> n >> m;		int f,t,w;		for(int i = 0; i < m; ++i){			cin >> f >> t >> w;			adj[f].push_back(Edge(t,w));			adj[t].push_back(Edge(f,w));		}					prim(1);		return 0;	}

（3）kruskal + 优先队列 + 并查集

#include
   
    #include
    
     #define MAX 105using namespace std;int n, m,tol;struct Edge{	int from,to,w;	int next;};bool cmp(const Edge a, const Edge b){	return a.w < b.w;}int id[MAX];int head[MAX]; Edge edges[MAX*MAX];int find(int p){	if(id[p] == p)		return p;	else return id[p] = find(id[p]);}void addEdge(int from, int to, int w)	{		edges[tol].from = from;		edges[tol].to = to;		edges[tol].w = w;		edges[tol].next = head[from];		head[from] = tol++;	}int main()	{		int from,to,w;		while(scanf("%d%d",&m,&n) == 2 && n!=0 && m != 0){			tol = 0;			int sum = 0;			int cop = n;			for(int i = 1; i <= n; ++i){				id[i] = i;				head[i] = -1;			} 			for(int i = 0; i < m; ++i){				scanf("%d%d%d",&from,&to,&w);				addEdge(from,to,w);			} 			sort(edges,edges+m,cmp);//排序			for(int i = 0; i < m; ++i){				int p = find(edges[i].from);				int q = find(edges[i].to);				if(p == q)					continue;				id[p] = q;				sum += edges[i].w;					--cop;			}			if(cop > 1){				printf("?\n");			}			else{				printf("%d\n",sum);			}								}						return 0;		}

kruskal(2)

#include
   
    using namespace std;const int MAXM = 50000+5;const int MAXN = 1000+5;int id[MAXN];int n,m;struct Node{	int f,t,w;	bool operator<(const Node o)const{		return w < o.w;	}}nodes[MAXM];int find(int p){	if(p == id[p])		return p;	else return id[p] = find(id[p]);}int main()	{			cin >> n >> m;				for(int i = 0; i <= n; ++i)//这个初始化 不能放在输入m,n之前 否则错误  也不知道为啥  醉了			id[i] = i;		for(int i = 0; i < m; ++i){			cin >> nodes[i].f >> nodes[i].t >> nodes[i].w; 		}		sort(nodes,nodes+m);		int sum = 0;		for(int i = 0; i < m; ++i){			Node tmp = nodes[i];			int p = find(tmp.f);			int q = find(tmp.t);			if(p == q) continue;			id[p] = q;			sum += tmp.w; 		}		printf("%d\n",sum);				return 0;		}

二、最短路径

（1）dijkstra + 优先队列+模拟邻接表

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 105;const int MAXM = 10005;struct Edge{	int to, w;	Edge(int pto, int pw){		to = pto;		w = pw;	}	bool operator < (const Edge o) const{		return w > o.w;			}};long long dis[MAXN];bool vis[MAXN];vector
        
          adj[MAXN];int n, m;int dijkstra() { memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); priority_queue
         
           pq; dis[1] = 0; pq.push(Edge(1,0)); while(!pq.empty()){ Edge tmp = pq.top(); int cur = tmp.to; if(cur == n){ return dis[n]; } vis[cur] = true; pq.pop(); for(int i = 0; i < adj[cur].size(); ++i){ Edge e = adj[cur][i]; if(!vis[e.to]){ if(dis[e.to] > dis[cur] + e.w){ dis[e.to] = dis[cur] + e.w; pq.push(Edge(e.to,dis[e.to])); } } } } return 0; }int main() { int a,b,c; while(scanf("%d%d",&n,&m) && n!=0 && m!=0){ for(int i = 1; i <= n; ++i){ adj[i].clear(); } for(int i = 1; i <= m; ++i){ scanf("%d%d%d",&a,&b,&c); adj[a].push_back(Edge(b,c)); adj[b].push_back(Edge(a,c)); } int ans = dijkstra(); printf("%d\n",ans); } return 0; }

三、tarjan算法

#include
   
    #include
    
      #include
     
      #include
      
        using namespace std;const int N = 1000+5;int low[N];int dfn[N];bool vis[N];vector
       
         adj[N];int index;bool flag[N];bool mark[N][N];int n,m,root;/*	求割点 */void tarjan(int cur, int fa)	{		int child = 0;		low[cur] = dfn[cur] = ++index;		vis[cur] = true;		for(int i = 0; i < adj[cur].size(); ++i){			int v = adj[cur][i];			if(!vis[v]){				++child;				tarjan(v,cur);				low[cur] = min(low[cur],low[v]);				if(cur != root && low[v] >= dfn[cur]){ //注意这里是 low[v] 子节点不能回到更早 不是low[cur] 					flag[cur] = true;				}				if(cur == root && child > 1){					flag[cur] = true;				}			}			else if(fa != v){				low[cur] = min(low[cur],dfn[v]);			}		}			}	 /*	求割边 */void tarjan(int cur, int fa)	{		low[cur] = dfn[cur] = ++index;		vis[cur] = true;		for(int i = 0; i < adj[cur].size(); ++i){			int v = adj[cur][i];			if(!vis[v]){				tarjan(v,cur);				low[cur] = min(low[cur],low[v]);				if(low[v] > dfn[cur]) {					//printf("%d - %d\n",cur,v);					mark[cur][v] = true;				}			}			else if(fa != v){				low[cur] = min(low[cur],dfn[v]);			}		}			}int main()	{		memset(flag,false,sizeof(flag));		index = 0;		scanf("%d%d",&n,&m);		root = 1;		int a,b;		for(int i = 0; i < m; ++i){			scanf("%d%d",&a,&b);			adj[a].push_back(b);			adj[b].push_back(a);		}		tarjan(1,1);		for(int i = 0; i <= n; ++i){			if(flag[i]){				printf("%d",i);			} 		}					return 0;		}