要求: (1)每个人的信息是一个结点,人与人的联系构成边。个人信息里要有地理坐标信息, 以便后续应用中能方便找附近的人。
(2)根据输入的任意两个人信息,给出他们之间的所有联系路径;以及最少经过多少
人构成联系。
(3)根据位置信息的动态变化,找寻附近能够联络的人、能够通过 1 次中间人联络的 人等。
(4)模拟仿真结点的联络密切程度,根据联络密切程度发现社交网络中的小团体,即 社区发现。社区发现可以从不同角度考虑。第一种是划分,把无关联的边去掉,进而识别出 重要的社区;第二种是聚合,将关联性比较大的顶点聚集起来,关联性较小的顶点剔除出去; 还有一种是基于模块度的算法。可选择一种算法实现社区发现。
数据结构C++ 社交网络图的实现 设计并实现一种简单的社交网络模型图。
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- ミForever 2019-06-18 19:34关注
#include
#include
#include
#include
#include
using namespace std;
const int MAXV = 100;
#define maxint 32767
const int inf = 1000000000;
int d[100];typedef int Vertextype; //假设顶点的数据类型为整型
typedef int Arctype; //假设边的权值类型为整型
#define mvnum 100//最大顶点数
#define maxvex 100
struct node {
int x;
int y;
}people[MAXV];
int n, m;
typedef struct
{
vectorV;
Vertextype ves[mvnum]; //顶点表
Arctype arcs[mvnum][mvnum]; //邻接矩阵
int vexnum, arcnum; //图当前点数和边数}AMGraph;
AMGraph G;
int LocateVex(AMGraph G, char v){
int i; for (i = 0; i < G.vexnum; i++) { if (G.ves[i] == v)break; } return i;
}
void createudn(AMGraph& G) //采用邻接矩阵表示法,创建无向图G{
cout << "请输入无向图的总顶人数:";
cin >> G.vexnum;
cout << endl << "请输入无向图的总边数:";
cin >> G.arcnum;
for (int i = 0; i < G.vexnum; ++i)
{
cin >> G.ves[i];
G.V.push_back(G.ves[i]);
}for (int i = 0; i < G.vexnum; ++i) for (int j = 0; j < G.vexnum; ++j) G.arcs[i][j] = maxint; for (int k = 0; k < G.arcnum; ++k) { cout << "请输入一条边依附的两人之间的关系其权值为1:"; int v1, v2, w, i, j; cin >> v1 >> v2; i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j] = 1; G.arcs[j][i] = 1; }
}
void dijkstra(int s, int G[][MAXV])
{
bool vis[MAXV] = { false };
fill(d, d + MAXV, inf);//对数组的定义,相当于从d[0]到d[MAXV-1]的数组定义,它的值最大可以为inf;
d[s] = 0;
for (int i = 0; i < n; i++)
{
int MIN = inf, u = -1;
for (int j = 0; j < n; j++)
{
if (vis[j] == false && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}if (u == -1)return; vis[u] = true; for (int v = 0; v < n; v++) { if (vis[v] == false && G[u][v] != inf && d[u] + G[u][v] < d[v]) { d[v] = d[u] + G[u][v]; } } }
}
/*struct Graph{ vectorV; //保存图中顶点的值
vector>E;//图的邻接矩阵
};
Graph G;*///vectorV;
vectorpath;//用于保存遍历过程中所走过的顶点值
void dfs(int b, int e)
{
path.push_back(b);//保存顶点值到路径中
if (e == b)//如果找到了路径输出路径
{
for (auto it = path.begin(); it != path.end(); ++it)
cout << *it << "\t";
cout << endl;
path.pop_back();//返回上一层时删除路径末尾值
return;} //如果未能找到终点,继续深度遍历 int index = find(G.V.begin(), G.V.end(), b) - G.V.begin(); for (int j = 0; j < G.vexnum; j++) { if (find(path.begin(), path.end(), G.V[j]) != path.end()) continue; if (G.arcs[index][j] == 1) dfs(LocateVex(G,G.ves[j]), e); } path.pop_back();
}
int main()
{
int i, j;
AMGraph G;
createudn(G);for (i = 0; i < G.vexnum; ++i) { for (j = 0; j < G.vexnum; ++j) { if (G.arcs[i][j] != maxint) cout << G.arcs[i][j] << "\t"; else cout << "0" << "\t"; } cout << endl << endl; } cout << endl; int b, e; cout << "lujing "; cin >> b >> e; dfs(b, e); int juzhen[MAXV][MAXV]; int u, v, w; n = G.vexnum; m = G.arcnum; cout << "请输入每个人的坐标x、y" << endl; int x, y; for (int i = 0; i < n; i++) { cin >> x >> y; people[i].x = x; people[i].y = y; } cout << "所有相互认识的两个人:" << endl; int GD[100][100]; //记录两个有联系的人的最短物理距离 int GP[100][100]; //记录两个有联系的人经过多少人 fill(GD[0], GD[0] + MAXV * MAXV, inf); fill(GP[0], GP[0] + MAXV * MAXV, inf); for (int i = 0; i < m; i++) { cin >> u >> v; GP[u][v] = GP[v][u] = 1; GD[u][v] = GD[v][u] = pow((double)(people[u].x - people[v].x), 2) + pow((double)(people[u].y - people[v].y), 2); GD[u][v] = GD[v][u] = sqrt(GD[u][v]); } while (true) { cout << "请输入任意一个人的序号以查出与其距离最近的人:"; int anyOne; cin >> anyOne; dijkstra(anyOne, GD); cout << endl; int sum = inf, flagIndex = -1; for (int i = 0; i < n; i++) { if (i != anyOne && d[i] < sum) { sum = d[i]; flagIndex = i; } } if (flagIndex == -1) cout << "此人没有可联系的人" << endl; else cout << "与" << anyOne << "距离最近的人是:" << flagIndex << endl; cout << "请输入人的序号和限定的距离范围:"; int distance; cin >> anyOne >> distance; dijkstra(anyOne, GD); cout << "在距离" << distance << "以内所有与人员" << anyOne << "有联系或间接联系的人" << endl; int count = 0; for (int i = 0; i < n; i++) { if (i != anyOne && d[i] <= distance) { count++; cout << i << '\t'; } } cout << endl; if (count == 0) cout << "该范围内没有满足条件的人" << endl; cout << "请输入两个人的序号以查询两者最少经过的人数:"; int p1, p2; cin >> p1 >> p2; dijkstra(p1, GP); cout << "最少经过" << d[p2] - 1 << "人构成联系" << endl; cout << endl; }
}
解决 2无用 7
悬赏问题
- ¥15 程序不包含适用于入口点的静态Main方法
- ¥15 素材场景中光线烘焙后灯光失效
- ¥15 请教一下各位,为什么我这个没有实现模拟点击
- ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
- ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
- ¥20 有关区间dp的问题求解
- ¥15 多电路系统共用电源的串扰问题
- ¥15 slam rangenet++配置
- ¥15 有没有研究水声通信方面的帮我改俩matlab代码
- ¥15 ubuntu子系统密码忘记