通过对本班好友的多少分析，发现本班的社交达人。
【问题描述】通过对本班好友的多少分析，发现本班的社交达人。
【基本要求】
下面的图表示好友间的连通关系，通过适当建模，发现交友最广泛的社交达人，通过定义好友间的连接紧密度，例如1表示关系最密切，发现关系最铁的组合。
【扩展】：探索发现新冠密切接触者。
好友最多的人怎么确定啊，求大神指导
#include<stdio.h>
#include<stdlib.h>
#define MAX_VEX_NUM 20 //最大顶点数
#define M 50 //队列长度
typedef char VertextType;
typedef struct
{
VertextType vexs; //存放结点的char行数组
int arcs; //存放边的数组
int vexnum, arcnum;//结点数，边数
}MGraph;
//循环队列的结构类型定义
typedef int DataType;
typedef struct
{
DataType sequ;
intrear, quelen;
}Queue;
//建立队
Queue* creatQueue()
{
Queue* sq;
sq = (Queue*)malloc(sizeof(Queue));
return sq;
}
//置空队
void InitQueue(Queue* sq)
{
sq->rear = M - 1;
sq->quelen = 0;
}
//入队
void QueueIn(Queue* sq, DataType x)
{
if (sq->quelen == 50)
printf("ERROR\n");
else if ((sq->rear + 1) == M)
{
sq->rear = (sq->rear + 1) % M;
sq->sequ = x;
sq->quelen++;
}
else
{
sq->rear++;
sq->sequ = x;
sq->quelen++;
}
}
//出队
DataType QueueOut(Queue* sq)
{
DataType sun = 0;
if (sq->quelen == 0)
{
printf("Error! The queue will be under flow!\n");
return 0;
}
else if ((sq->rear + 1) >= sq->quelen)
{
sq->quelen--;
sun = sq->sequ;
return(sun);
}
else
{
sq->quelen--;
sun = sq->sequ;
return(sun);
}
}
//判断队列是否为空
int Empty(Queue* sq)
{
if (sq->quelen == 0)
{
printf("ERROR\n");
return 0;
}
return 1;
}
//索引判断
int index(char vex, MGraph* mg)
{
int i;
for (i = 1;i <= mg->vexnum;i++)
{
if (mg->vexs == vex)
return i;
}
return 0;
}
//生成邻接矩阵
void Creat(MGraph* mg)
{
int type, i, j, k, v1_index, v2_index,friend,a;
int F;
char v1, v2;
printf("输入人数");
scanf("%d", &mg->vexnum); //输入结点数
printf("输入好友关系");
scanf("%d", &mg->arcnum);//输入边数
getchar();
for (i = 1;i <= mg->vexnum;i++)
{
printf("输入同学%d :", i);
scanf("%c", &mg->vexs,1);//循环存放每个结点
getchar();
}
for (i = 1;i <= mg->vexnum;i++)
for (j = 1;j <= mg->vexnum;j++)
mg->arcs = 0;//初始化边，全部设为0
for (k = 1;k <= mg->arcnum;k++)
{
printf("输入 %d 好友关系:", k);
scanf("%c %c", &v1, &v2);
v1_index = index(v1, mg);//索引该结点对应的位置
v2_index = index(v2, mg);//索引该结点对应的位置
mg->arcs = 1;
getchar();
}
}
//BFS算法
int visited = {0};
void BFS(MGraph G, int v0) //vo搜索起点
{
int i, j, v = 0;
Queue* Q = creatQueue();
InitQueue(Q);
//起点入队
if (!visited)
{
QueueIn(Q, v0);
visited = 1;
printf("%c", G.vexs);
while (!Empty(Q))
{
v = QueueOut(Q);
for (j = 1;j <= G.vexnum; j++)
{
if (G.arcs == 1 && visited != 1)
{
printf("%c", G.vexs);
visited = 1;
QueueIn(Q, j);
}
}
}
}
//搜索其他树，防止森林其他树为搜索
for (i = 1; i <= G.vexnum; i++)
{
if (visited != 1 )
{
BFS(G, i);
}
}
}
void Print(MGraph* mg)
{
int i, j;
for (i = 1;i <= mg->vexnum;i++)
{
for (j = 1;j <= mg->vexnum;j++)
{
printf("%d ", mg->arcs);//遍历输出矩阵
}
printf("\n");
}
}
int main()
{
MGraph MG;
Creat(&MG);
Print(&MG);
BFS(MG, 1);
return 0;
}
代码放在"<>“里 把图转为邻接表，或者邻接矩阵。
页:
[1]