邻接表创建无向图C语言
时间: 2024-12-17 15:37:48 浏览: 53
在C语言中,邻接表是一种常见的用于表示无向图的数据结构。它将每个顶点作为一个节点,并存储该顶点的所有邻居(即与其相连的其他顶点)列表。对于无向图,每条边会在两个顶点的邻接表中各出现一次。
以下是创建邻接表表示无向图的基本步骤:
1. 定义数据结构:创建一个结构体,比如`Node`,包含一个指向下一个节点的指针以及一个存储顶点值的数组或链表,表示邻接顶点。
```c
typedef struct Node {
int vertex; // 顶点值
struct Node* next; // 指向相邻节点的指针
} Node;
```
2. 创建图结构:定义一个全局变量,如`Graph`,保存所有节点的头结点。
```c
typedef struct Graph {
Node* nodes; // 图的起始节点
int numVertices; // 顶点数
} Graph;
```
3. 添加顶点:对每个新的顶点,初始化一个新的`Node`并将其添加到图的节点列表。
4. 添加边:对于无向图中的每条边,从一个顶点的`next`指针开始遍历,找到另一个顶点,然后在那个顶点的邻接列表中插入第一个顶点。同时,也要在第一个顶点的邻接表中添加第二个顶点。
5. 访问和操作:通过顶点的索引来访问其邻接节点,如查找、删除边等。
例如,添加一条边`(u, v)`的操作可以写成:
```c
void addEdge(Graph* graph, int u, int v) {
Node* nodeU = findNode(graph, u); // 查找u对应的节点
if (!nodeU) {
nodeU = createNode(u); // 如果找不到,新建节点
graph->nodes = nodeU; // 将新节点设置为当前图的第一个节点
graph->numVertices++;
}
Node* nodeV = findNode(graph, v); // 同理查找v的节点
if (nodeV) {
nodeU->next = nodeV; // u的邻接表加入v
nodeV->next = nodeU; // v的邻接表也加入u(无向图)
} else {
// 对于v,同样处理
}
}
```
阅读全文
相关推荐


















