数据结构C++ 社交网络图的实现 设计并实现一种简单的社交网络模型图。

Question

要求： （1）每个人的信息是一个结点，人与人的联系构成边。个人信息里要有地理坐标信息， 以便后续应用中能方便找附近的人。
（2）根据输入的任意两个人信息，给出他们之间的所有联系路径；以及最少经过多少
人构成联系。
（3）根据位置信息的动态变化，找寻附近能够联络的人、能够通过 1 次中间人联络的 人等。
（4）模拟仿真结点的联络密切程度，根据联络密切程度发现社交网络中的小团体，即 社区发现。社区发现可以从不同角度考虑。第一种是划分，把无关联的边去掉，进而识别出 重要的社区；第二种是聚合，将关联性比较大的顶点聚集起来，关联性较小的顶点剔除出去； 还有一种是基于模块度的算法。可选择一种算法实现社区发现。

Answer 1

#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;
}

}