如何计算社交网络图中节点的重要性，然后进行图的遍历输出？

C++ 数据结构 图 社交网络图中结点的“重要性”计算
实现计算每个节点的紧密度中心性，然后进行图的遍历输出，

img

仅供参考



#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#define INIFITY 65535
typedef struct ENode* Edge;
struct ENode
{
    int V1, V2;
};
typedef struct GNode* Graph;
struct  GNode
{
    int G[10000][10000];
    float Nv;
    int Ne;
};

int IsEdge(Graph Gra, int V1, int V2)
{
    return Gra->G[V1][V2]!=INIFITY;
}

void Insert(Graph Gra, Edge E)
{
    Gra->G[E->V1][E->V2] = 1;
    Gra->G[E->V2][E->V1] = 1;
}

Graph CreateGraph(int Nv)
{
    Graph Gra = (Graph)malloc(sizeof(struct GNode));
    Gra->Nv = Nv;
    Gra->Ne = 0;
    for (int i = 1; i <=Gra->Nv; i++)
        for (int j = 1; j <= Gra->Nv; j++)
    {
        Gra->G[i][j] = INIFITY;
        if (i == j)
            Gra->G[i][j] = 0;
    }
    return Gra;
}

int Dist[10000][10000];
int Flag=1;
void Floyd(Graph Gra)
{
    int i, j, k;
    for (i = 1; i <= Gra->Nv; i++)
        for (j = 1; j <= Gra->Nv; j++)
            Dist[i][j] = Gra->G[i][j];
    for(int k=1;k<=Gra->Nv;k++)
        for(int i=1;i<=Gra->Nv;i++)
            for (int j = 1; j <= Gra->Nv; j++)
    {
        if (Dist[i][k] + Dist[k][j] < Dist[i][j])
            Dist[i][j] = Dist[i][k] + Dist[k][j];
    }
    for (i = 1; i <= Gra->Nv; i++)
        for (j = 1; j <= Gra->Nv; j++)
            if (Dist[i][j] == INIFITY)
    {
        Flag = 0;
        break;
    }
}

int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    Graph Gra = CreateGraph(N);
    Gra->Ne = M;
    Edge E = (Edge)malloc(sizeof(struct ENode));
    for (int i = 0; i < Gra->Ne; i++)
    {
        scanf("%d%d", &(E->V1), &(E->V2));
        Insert(Gra, E);
    }
    Floyd(Gra);
    float num=0;
    int K;
    scanf("%d", &K);
    while (K--)
    {
        num = 0;
        int n;
        scanf("%d", &n);
        if (Flag)
        {
            for (int i = 1; i <= Gra->Nv; i++)
                num += Dist[n][i];
            printf("Cc(%d)=%.2f\n", n, (Gra->Nv - 1) / num);
        }
        else
            printf("Cc(%d)=0.00\n", n);
    }
    return 0;
}
/*
9 14
1 2
1 3
1 4
2 3
3 4
4 5
4 6
5 6
5 7
5 8
6 7
6 8
7 8
7 9
9 1 2 3 4 5 6 7 8 9
*/
上面的代码已经实现了Cc（i）的计算，还差图的遍历输出

#include <iostream>
#include <queue>
#include <climits>
#include <map>

using namespace std;

class Graph {
public:

    Graph(int v, int e) : Vertex(v), Edge(e) {
        G = new int *[v];
        for (int i = 0; i < v; i++) {
            G[i] = new int[v];
            for (int j = 0; j < v; j++) {
                G[i][j] = 0;
            }
        }
    }
    
    ~Graph(){
        for (int i = 0; i < Vertex; i++) {
            delete[] G[i];
        }
        delete[] G;
    }

    void Insert(int v1, int v2) {
        G[v1][v2] = 1;
        G[v2][v1] = 1;
    }

    double Importance(int v) {
        int distance[Vertex];
        for (int i = 0; i < Vertex; i++) {
            distance[i] = INT_MAX;
        }
        distance[v] = 0;
        int Visited[Vertex][Vertex];
        for (int i = 0; i < Vertex; i++) {
            for (int j = 0; j < Vertex; j++) {
                Visited[i][j] = 0;
            }
        }
        map<int,int> visitedNode;
        queue<int> q;
        q.push(v);
        while (!q.empty()) {
            int temp = q.front();
            q.pop();
            for (int i = 0; i < Vertex; i++) {
                if (G[temp][i] == 1 && Visited[temp][i] == 0 && visitedNode[i]==0) {
                    if (distance[i] > distance[temp] + 1)
                        distance[i] = distance[temp] + 1;
                    visitedNode[i]=1;
                    q.push(i);
                    Visited[temp][i] = 1;
                    Visited[i][temp] = 1;
                }
            }
        }
        double sum = 0;
        for (int i = 0; i < Vertex; i++) {
            sum += distance[i];
        }
        return (Vertex - 1.0) / sum;
    }

private:
    int Vertex;
    int Edge;
    int **G;
};

int main() {
    int vertex, edge;
    scanf("%d %d", &vertex, &edge);
    Graph graph(vertex, edge);
    int temp1, temp2;
    for (int i = 0; i < edge; i++) {
        scanf("%d %d", &temp1, &temp2);
        graph.Insert(temp1 - 1, temp2 - 1);
    }
    int num;
    scanf("%d", &num);
    int n;
    for (int i = 0; i < num; i++) {
        scanf("%d", &n);
        printf("Cc(%d)=%.2f\n", n, graph.Importance(n - 1));
    }
}

在社交网络中，节点的重要性通常是指节点在网络中的影响力或权威度。有许多方法可以用来计算节点的重要性，其中一些常见的方法包括：

1.度量：度量是指节点的度数，即与该节点相连的边的数量。节点的度数越高，该节点就越重要。

2.中心性：中心性是指节点与其他节点的距离。节点的中心性越高，该节点就越重要。常用的中心性度量包括度中心性、接近中心性和哈密尔顿中心性。

3.介数中心性：介数中心性是指节点在网络中的社交中介作用。节点的介数中心性越高，该节点就越重要。常用的介数中心性度量包括最短路径介数中心性和欧拉介数中心性。

要进行图的遍历，可以使用深度优先搜索(DFS)或广度优先搜索(BFS)。DFS和BFS的主要区别在于搜索的顺序不同：DFS是深入搜索，而BFS是广度搜索。

下面是一个使用DFS进行图遍历的示例代码：

void DFS(int start, vector<Node>& nodes, vector<bool>& visited) {
  // 将起始节点标记为已访问
  visited[start] = true;
  cout << "Visited node " << start << endl;

  // 遍历起始节点的每一个邻居
  for (int neighbor : nodes[start].neighbors) {
    // 如果邻居节点未被访问，则递归调用DFS函数
    if (!visited[neighbor]) {
      DFS(neighbor, nodes, visited);
    }
  }
}

这段代码定义了一个DFS函数，接受三个参数：起始节点的编号、图的节点集合和节点是否被访问的标志集合。

在函数内部，首先将起始节点标记为已访问，然后遍历起始节点的每一个邻居。如果邻居节点未被访问，则递归调用DFS函数，将邻居节点作为起始节点，继续进行遍历。

你可以使用这段代码作为基础，根据自己的需求进行更改和扩展。

提供参考实例，实例中讲解了2种解法思路，链接：http://t.zoukankan.com/snzhong-p-12532539.html

参考一下