SDRAGON 发表于 2023-5-30 14:43:44

通过对本班好友的多少分析,发现本班的社交达人。

【问题描述】
通过对本班好友的多少分析,发现本班的社交达人。
【基本要求】
下面的图表示好友间的连通关系,通过适当建模,发现交友最广泛的社交达人,通过定义好友间的连接紧密度,例如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;
}



歌者文明清理员 发表于 2023-5-30 16:56:27

代码放在"<>“里

赚小钱 发表于 2023-6-9 09:01:13

把图转为邻接表,或者邻接矩阵。
页: [1]
查看完整版本: 通过对本班好友的多少分析,发现本班的社交达人。