用邻接表存储图c语言
时间: 2023-11-27 11:48:10 浏览: 38
以下是使用C语言实现图的邻接表存储的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表中的边结构体
typedef struct EdgeNode {
int adjvex; // 邻接点在顶点数组中的下标
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
// 定义邻接表中的顶点结构体
typedef struct VertexNode {
char data; // 顶点数据
EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode;
// 定义图结构体
typedef struct {
VertexNode vertex[100]; // 顶点数组,最多存储100个顶点
int vexnum, edgenum; // 顶点数和边数
} Graph;
// 初始化图
void InitGraph(Graph *G) {
int i;
G->vexnum = G->edgenum = 0;
for (i = 0; i < 100; i++) {
G->vertex[i].data = '\0';
G->vertex[i].firstedge = NULL;
}
}
// 向图中添加顶点
void AddVertex(Graph *G, char data) {
G->vertex[G->vexnum].data = data;
G->vexnum++;
}
// 向图中添加边
void AddEdge(Graph *G, int v1, int v2) {
EdgeNode *e1 = (EdgeNode *)malloc(sizeof(EdgeNode));
e1->adjvex = v2;
e1->next = G->vertex[v1].firstedge;
G->vertex[v1].firstedge = e1;
EdgeNode *e2 = (EdgeNode *)malloc(sizeof(EdgeNode));
e2->adjvex = v1;
e2->next = G->vertex[v2].firstedge;
G->vertex[v2].firstedge = e2;
G->edgenum++;
}
// 遍历图
void BFS(Graph *G, int v) {
int visited[100] = {0}; // 标记数组,用于记录每个顶点是否被访问过
int queue[100], front = 0, rear = 0; // 队列,用于存储待访问的顶点
EdgeNode *p;
printf("%c ", G->vertex[v].data);
visited[v] = 1;
queue[rear++] = v;
while (front != rear) {
int w = queue[front++];
for (p = G->vertex[w].firstedge; p != NULL; p = p->next) {
int u = p->adjvex;
if (!visited[u]) {
printf("%c ", G->vertex[u].data);
visited[u] = 1;
queue[rear++] = u;
}
}
}
}
// 示例代码
int main() {
Graph G;
InitGraph(&G);
AddVertex(&G, 'a');
AddVertex(&G, 'b');
AddVertex(&G, 'c');
AddVertex(&G, 'd');
AddVertex(&G, 'e');
AddEdge(&G, 0, 1);
AddEdge(&G, 0, 2);
AddEdge(&G, 0, 3);
AddEdge(&G, 1, 2);
AddEdge(&G, 1, 4);
AddEdge(&G, 2, 3);
AddEdge(&G, 3, 4);
BFS(&G, 0);
return 0;
}
```