图的应用

╰半夏微凉° 2021-07-16 23:04 391阅读 0赞

题目：图在社交网络上的应用  
\[问题描述\]  
设计并实现一个社交网络模型图，并实现相关图的算法。  
要求：  
（1）每个人的信息是一个顶点，A关注了B，则构成A到B的边。请随机生成不少于50个点，和不少于500条边，边有方向，带权重（0-1之间），权重可以认为是两个人的亲密度，可随机生成。  
（2）根据输入的任意两个人的信息，可以查询打印他们之间的所有可能的路径。  
（3）实现图的深度优先遍历和广度优先遍历算法，打印图中所有点。  
（4）求图的所有强连通分量。  
（5）在最大的强连通分量上用prim和chruscal算法求最小生成树。  
（6）在最大的强连通分量上，实现dijstra和floyd算法求节点之间最短路径。

//suda的同学请勿直接copy，可参考。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<ctime>
    #include<queue>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int first[1505], nex[1505];
    int sta[1505], top = 0;
    int b[105][105];
    int book[105];
    int f[105];
    
    class Grapth
    { 
    public:
    	Grapth();
    	void put();//打印两点间的路径，为降低复杂度用链式前向星进行DFS
    	void dfs(int n,int pre,int f);
    	void dfs_grapth(int n);
    	void bfs_grapth(int n);
    	int get_vertex() {  return vertexNum; }
    	int get_edge() {  return edgeNum; }
    	void prim();
    	void kruskal();
    	void floyd();
    	void dijkstra();
    	//并查集求连通图的构造
    	int getf(int n);
    	int merge(int a, int b);
    	void conected_grapth();
    private:
    	int vertexNum, edgeNum;
    	double edge[105][105];//邻接表存储
    	int u[1505], v[1505];
    	double w[1505];//链式前向星存储
    };
    
    Grapth::Grapth()
    { 
    	int n = 50 + rand() % 51;//点的个数50-100
    	int m = 500 + rand() % 51;//边的个数500-550
    	vertexNum = n, edgeNum = 2 * m;
    	//本图依题意（社交网络）无自环和重边
    	int g = 0;memset(first, -1, sizeof(first));int q = 0;
    	for (int i = 1;i <= n;i++)
    	{ 
    		for (int j = 1;j <= n;j++)
    			if (i == j)edge[i][j] = 0;
    			else edge[i][j] = 1e7;
    	}
    	for (int i = 1;i <= m;i++)
    	{ 
    		if (++q > 10000)break;
    		double w0 = double(rand() % 101) / 100;//权值0-1
    		int u0 = 1 + rand() % n, v0 = 1 + rand() % n;
    		if (b[u0][v0] || u0 == v0 || b[v0][u0]) i--;//已有
    		else
    		{ 
    			edge[u0][v0] = w0;
    			edge[v0][u0] = w0;
    			b[u0][v0] = 1;
    			u[++g] = u0;v[g] = v0;w[g] = w0;
    			nex[g] = first[u0];first[u0] = g;
    			u[++g] = v0;v[g] = u0;w[g] = w0;
    			nex[g] = first[v0];first[v0] = g;
    		}
    	}
    }
    
    int Grapth::getf(int n)
    { 
    	if (f[n] == n)return n;
    	return f[n] = getf(f[n]);
    }
    
    int Grapth::merge(int a, int b)
    { 
    	if (getf(a) == getf(b))return 1;
    	f[getf(b)] = getf(a);return 0;
    }
    
    void Grapth::conected_grapth()
    { 
    	for (int i = 1;i <= vertexNum;i++)f[i] = i;
    	for (int i = 1;i <= edgeNum;i++)merge(u[i], v[i]);
    	int num = 0;int ls[105];int n[105];	int lst[105][105];
    	memset(ls, 0, sizeof(ls));memset(n, 0, sizeof(n));
    	for (int i = 1;i <= vertexNum;i++)
    	{ 
    		if (getf(i) == i)
    		{ 
    			ls[++num] = i;
    			
    		}
    		lst[getf(i)][++n[getf(i)]] = i;
    	}
    	if (num == 1)
    	{ 
    		cout << "该图为连通图" << endl;
    		for (int i = 1;i <= num;i++)
    		{ 
    			//cout << "case " << i << " :";
    			for (int j = 1;j <= n[ls[i]];j++)cout << lst[ls[i]][j] << " ";
    			cout << endl;
    		}
    	}
    	else
    	{ 
    		cout << "该非连通的连通分量有" << num << "个" << endl;
    		for (int i = 1;i <= num;i++)
    		{ 
    			cout << "case " << i << " :";
    			for (int j = 1;j <= n[ls[i]];j++)cout << lst[ls[i]][j] << " ";
    			cout << endl;
    		}
    	}
    }
    
    void Grapth::dijkstra()
    { 
    	cout << "dijkstra算法输入想要求哪个顶点到其余顶点的最短距离" << endl;
    	int u;cin >> u ;
    	int n = vertexNum, j;
    	double dis[105], mi, e[105][105];
    	memset(book, 0, sizeof(book));
    	for (int i = 1;i <= n;i++)
    		for (int j = 1;j <= n;j++)
    			e[i][j] = edge[i][j];
    	for (int i = 1;i <= n;i++)dis[i] = e[u][i];
    	book[u] = 1;
    	for (int i = 1;i <= n - 1;i++)
    	{ 
    		mi = 1e8;
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (dis[i] < mi&&book[i]==0) 
    			{ 
    				j = i;mi = dis[j];
    			}
    		}
    		book[j] = 1;
    		for (int i = 1;i <= n;i++)
    		{ 
    			dis[i] = min(dis[i], dis[j] + e[j][i]);
    		}
    	}
    	cout << "dijkstra所求得结果如下:" << endl;
    	for (int i = 1;i <= n;i++)
    	{ 
    		cout <<u<< " 到点 " << i << " 的最短距离为" << dis[i] << " " << endl;
    	}
    	cout << endl;
    }
    
    void Grapth::floyd()
    { 
    	cout << "floyd输入想要求哪个顶点到其余顶点的最短路径" << endl;
    	int u;cin >> u ;
    	int n = vertexNum, m = edgeNum;
    	double e[105][105];
    	for(int i=1;i<=n;i++)
    		for (int j = 1;j <= n;j++)
    		{ 
    			e[i][j] = edge[i][j];
    		}
    	for(int k=1;k<=n;k++)
    		for(int i=1;i<=n;i++)
    			for (int j = 1;j <= n;j++)
    			{ 
    				e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
    			}
    	cout << "floyd所求得结果如下:" << endl;
    	for (int i = 1;i <= n;i++)
    	{ 
    		cout << u << " 到点 " << i << " 最短距离" << e[u][i] << endl;
    	}
    	cout << endl;
    }
    
    
    
    void Grapth::bfs_grapth(int n)
    { 
    	queue<int> que;
    	que.push(n);
    	memset(book, 0, sizeof(book));
    	book[n] = 1;
    	while (!que.empty())
    	{ 
    		int u = que.front();
    		que.pop();
    		cout << u << " ";
    		int k = first[u];
    		while (k != -1)
    		{ 
    			if (book[v[k]])
    			{ 
    				k = nex[k];continue;
    			}
    			book[v[k]] = 1;
    			que.push(v[k]);
    			k = nex[k];
    		}
    	}
    	for (int i = 1;i <= vertexNum;i++)if(book[i]==0)cout << i << " ";
    	cout << endl;
    }
    
    void Grapth::dfs_grapth(int n)
    { 
    	if (book[n])return;
    	cout << n << " ";
    	book[n] = 1;
    	int k = first[n];
    	while (k != -1)
    	{ 
    		if (book[v[k]])
    		{ 
    			k = nex[k];continue;
    		}
    		dfs_grapth(v[k]);
    		k = nex[k];
    	}
    }
    
    void Grapth::dfs(int n, int pre,int f)
    { 
    	if (n == f)
    	{ 
    		cout <<"一条路径为：" << endl;
    		for (int i = 1;i <= top;i++)cout << sta[i] << " ";cout << endl << endl;;return;
    	}
    	int k = first[n];
    	while (k != -1)
    	{ 
    		if (v[k] == pre||book[v[k]]==1)
    		{ 
    			k = nex[k];continue;
    		}
    		sta[++top] = v[k];
    		book[v[k]] = 1;
    		dfs(v[k], n, f);
    		book[v[k]] = 0;
    		top--;
    		k = nex[k];
    	}
    }
    
    void Grapth::put()
    { 
    	cout << "输入两个顶点，将会输出路径" << endl;
    	int a, b;cin >> a >> b;
    	memset(book, 0, sizeof(book));
    	sta[++top] = a;book[a] = 1;
    	dfs(a, -9, b);
    }
    
    struct ed
    { 
    	int u, v;double w;
    	bool operator<(const ed& a)const
    	{ 
    		return w < a.w;
    	}
    };
    //开为全局变量，栈区存放的空间太小。
    Grapth gt;
    ed edg[105];
    
    void Grapth::kruskal()
    { 
    	for (int i = 1;i <= vertexNum;i++)f[i] = i;
    
    	for (int i = 1;i <= edgeNum;i++)
    	{ 
    		edg[i].u = u[i];edg[i].v = v[i];edg[i].w = w[i];
    	}
    	sort(edg + 1, edg + 1 + edgeNum);
    	double ans = 0;
    	for (int i = 1;i <= edgeNum;i++)
    	{ 
    		if (merge(edg[i].u, edg[i].v) == 0)
    			ans += edg[i].w;
    	}
    	cout << "kruskal最小生成树的权值和为:" << ans << endl;
    }
    
    void Grapth::prim()
    { 
    	int n = vertexNum, m = edgeNum, count = 1;
    	double dis[105],mi=1e8;memset(book, 0, sizeof(book));
    	for (int i = 1;i <= n;i++)dis[i] = 1e8;
    	book[1] = 1;dis[1] = 0;
    	int k = first[1];
    	while (k != -1)
    	{ 
    		dis[v[k]] = w[k];
    		k = nex[k];
    	}
    	double ans = 0;
    	while (1)
    	{ 
    		if (++count == n + 1)break;
    		mi = 1e9;int j=0;
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (mi > dis[i] && book[i] == 0)
    			{ 
    				mi = dis[i];j = i;
    			}
    		}
    		book[j] = 1;ans += dis[j];
    		int k = first[j];
    		while (k != -1)
    		{ 
    			dis[v[k]] = min(dis[v[k]], w[k]);
    			k = nex[k];
    		}
    	}
    	cout << "prim生成树的最小权值和:" << ans << endl;
    }
    
    void view()
    { 
    	cout << "输入 1 输出，查询两个顶点的路径" << endl;
    	cout << "输入 2 根据深度优先搜索打印途中所有点" << endl;
    	cout << "输入 3 根据广度优先搜索打印图中所有点" << endl;
    	cout << "输入 4 求图的所有强连通分量" << endl;
    	cout << "输入 5 在最大强连通分量上用prim和kruskal求图的最小生成树" << endl;
    	cout << "输入 6 在最大强连通份量上用dijstra和floyd求结点之间的最短路径" << endl;
    }
    
    void project()
    { 
    	Grapth gra;
    	int sec=1;
    	while (sec != 0)
    	{ 
    		system("cls");
    		view();cin >> sec;
    		if (sec == 1)gra.put();
    		else if (sec == 2) { memset(book, 0, sizeof(book));gra.dfs_grapth(1);}
    		else if (sec == 3)gra.bfs_grapth(1);
    		else if (sec == 4)gra.conected_grapth();
    		else if (sec == 5)
    		{ 
    			gra.prim();gra.kruskal();
    		}
    		else if (sec == 6)
    		{ 
    			gra.floyd();gra.dijkstra();
    		}
    		cout << endl;
    		cout << "输入0退出1继续" << endl;
    		int f;cin >> f;if (f == 0)break;
    	}
    }
    
    int main()
    { 
    	project();
    	return 0;
    }