qq_42786121
qq_42786121
采纳率0%
2019-03-13 16:03 阅读 1.9k

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

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • weixin_44263415 ミ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;
    }
    

    }

    点赞 1 评论 复制链接分享

相关推荐