用c++编写图的邻接表存储及遍历
时间: 2024-06-10 18:10:33 浏览: 13
以下是使用C语言编写的图的邻接表存储及遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct EdgeNode {
int adjvex; // 相邻顶点的下标
int weight; // 边的权值
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
typedef struct VertexNode {
int data; // 顶点数据
EdgeNode *first_edge; // 指向第一个邻接点的指针
} VertexNode;
typedef struct {
VertexNode vertices[MAX_VERTICES]; // 存储顶点的数组
int num_vertices; // 顶点个数
int num_edges; // 边个数
} Graph;
// 初始化图
void init_graph(Graph *g) {
g->num_vertices = 0;
g->num_edges = 0;
int i;
for (i = 0; i < MAX_VERTICES; i++) {
g->vertices[i].data = 0;
g->vertices[i].first_edge = NULL;
}
}
// 添加顶点
void add_vertex(Graph *g, int data) {
g->vertices[g->num_vertices].data = data;
g->vertices[g->num_vertices].first_edge = NULL;
g->num_vertices++;
}
// 添加边
void add_edge(Graph *g, int src, int dest, int weight) {
EdgeNode *new_edge = (EdgeNode*)malloc(sizeof(EdgeNode));
new_edge->adjvex = dest;
new_edge->weight = weight;
new_edge->next = g->vertices[src].first_edge;
g->vertices[src].first_edge = new_edge;
g->num_edges++;
}
// 打印邻接表
void print_graph(Graph *g) {
int i;
for (i = 0; i < g->num_vertices; i++) {
EdgeNode *p = g->vertices[i].first_edge;
printf("%d: ", g->vertices[i].data);
while (p) {
printf("%d(%d) ", g->vertices[p->adjvex].data, p->weight);
p = p->next;
}
printf("\n");
}
}
// 深度优先遍历
void dfs(Graph *g, int v, int *visited) {
visited[v] = 1;
printf("%d ", g->vertices[v].data);
EdgeNode *p = g->vertices[v].first_edge;
while (p) {
if (!visited[p->adjvex]) {
dfs(g, p->adjvex, visited);
}
p = p->next;
}
}
// 广度优先遍历
void bfs(Graph *g, int v, int *visited) {
int queue[MAX_VERTICES];
int front = 0, rear = 0;
queue[rear++] = v;
visited[v] = 1;
printf("%d ", g->vertices[v].data);
while (front != rear) {
int w = queue[front++];
EdgeNode *p = g->vertices[w].first_edge;
while (p) {
if (!visited[p->adjvex]) {
queue[rear++] = p->adjvex;
visited[p->adjvex] = 1;
printf("%d ", g->vertices[p->adjvex].data);
}
p = p->next;
}
}
}
int main() {
Graph g;
init_graph(&g);
add_vertex(&g, 1);
add_vertex(&g, 2);
add_vertex(&g, 3);
add_vertex(&g, 4);
add_edge(&g, 0, 1, 1);
add_edge(&g, 0, 2, 2);
add_edge(&g, 1, 3, 3);
add_edge(&g, 2, 3, 4);
print_graph(&g);
int visited[MAX_VERTICES] = {0};
printf("DFS: ");
dfs(&g, 0, visited);
printf("\nBFS: ");
bfs(&g, 0, visited);
printf("\n");
return 0;
}
```
该示例代码定义了一个`Graph`结构体,包含一个`VertexNode`结构体数组`vertices`(存储顶点信息)、一个`num_vertices`变量(存储顶点个数)和一个`num_edges`变量(存储边个数)。`VertexNode`结构体包含一个`data`变量(存储顶点数据)和一个`first_edge`指针(指向第一个邻接点)。`EdgeNode`结构体表示边,包含一个`adjvex`变量(存储相邻顶点的下标)、一个`weight`变量(存储边的权值)和一个`next`指针(指向下一个邻接点)。
该示例代码实现了图的初始化、顶点添加、边添加、邻接表打印、深度优先遍历和广度优先遍历。其中,深度优先遍历使用递归实现,广度优先遍历使用队列实现。在深度优先遍历和广度优先遍历中,用一个`visited`数组记录已经访问过的顶点,以避免重复访问。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)