用c语言六度空间法则
时间: 2023-11-27 08:54:08 浏览: 113
使用C语言实现
六度空间法则指的是人与人之间通过不超过六个中间人就可以达成联系的理论。在C语言中,我们可以利用图的数据结构来实现这一理论。
首先,我们需要定义一个图的结构体:
```
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
int weight; // 弧的权值
} ArcNode;
typedef struct VNode {
char data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 图中顶点数组
int vexnum, arcnum; // 顶点数和弧数
} ALGraph;
```
然后,我们需要实现一个函数来建立图,这里以无向图为例:
```
void CreateGraph(ALGraph *G) {
printf("请输入顶点数和边数(用空格隔开):");
scanf("%d %d", &G->vexnum, &G->arcnum);
getchar();
for (int i = 0; i < G->vexnum; i++) {
printf("请输入第 %d 个顶点的信息:", i + 1);
scanf("%c", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
getchar();
}
for (int i = 0; i < G->arcnum; i++) {
char v1, v2;
int w;
printf("请输入第 %d 条边的顶点及权值(用空格隔开):", i + 1);
scanf("%c %c %d", &v1, &v2, &w);
getchar();
int pos1 = LocateVex(*G, v1);
int pos2 = LocateVex(*G, v2);
ArcNode *p1 = (ArcNode *)malloc(sizeof(ArcNode));
p1->adjvex = pos2;
p1->nextarc = G->vertices[pos1].firstarc;
p1->weight = w;
G->vertices[pos1].firstarc = p1;
ArcNode *p2 = (ArcNode *)malloc(sizeof(ArcNode));
p2->adjvex = pos1;
p2->nextarc = G->vertices[pos2].firstarc;
p2->weight = w;
G->vertices[pos2].firstarc = p2;
}
}
```
其中,`LocateVex` 函数用于查找顶点在图中的位置。
接下来,我们可以使用广度优先搜索算法来实现六度空间法则的功能:
```
#define MAX_SIZE 100
void BFS(ALGraph G, int start, int visited[]) {
int queue[MAX_SIZE], front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int v = queue[front++];
printf("%c ", G.vertices[v].data);
for (ArcNode *p = G.vertices[v].firstarc; p != NULL; p = p->nextarc) {
int w = p->adjvex;
if (!visited[w]) {
visited[w] = 1;
queue[rear++] = w;
}
}
}
}
void SixDegrees(ALGraph G, char c) {
int start = LocateVex(G, c);
int visited[G.vexnum];
memset(visited, 0, sizeof(visited));
BFS(G, start, visited);
}
```
这个算法接受一个图和一个顶点作为输入,然后使用广度优先搜索从该顶点开始遍历图,并输出与该顶点有联系的所有顶点。
最后,我们可以在主函数中调用 `CreateGraph` 和 `SixDegrees` 函数来实现六度空间法则的功能:
```
int main() {
ALGraph G;
CreateGraph(&G);
char c;
printf("请输入起始顶点:");
scanf("%c", &c);
SixDegrees(G, c);
return 0;
}
```
阅读全文