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