题目:图在社交网络上的应用
[问题描述]
设计并实现一个社交网络模型图,并实现相关图的算法。
要求:
(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;
}