c语言实现图的存储,输出存储结构示意图
时间: 2024-01-29 08:39:23 浏览: 28
C语言中实现图的存储通常有两种方式:邻接矩阵和邻接表。
1. 邻接矩阵:
邻接矩阵是一个二维数组,其中第i行第j列的元素表示节点i到节点j是否有边相连,有则表示为1,否则为0。
示意图如下:
```
0 1 2 3
0 0 1 1 0
1 1 0 1 0
2 1 1 0 1
3 0 0 1 0
```
2. 邻接表:
邻接表则是将每个节点作为链表的头结点,链表中存储该节点所连接的所有节点。
示意图如下:
```
0 -> 1 -> 2
1 -> 0 -> 2
2 -> 0 -> 1 -> 3
3 -> 2
```
相关问题
用c语言实现图示的存储,输出存储结构示意图
好的,以下是用C语言实现的图示存储的示例代码和存储结构示意图:
示例代码:
```c
#include <stdio.h>
#define MAX_VERTICES 10
typedef struct {
int visited;
int vertex;
} Vertex;
typedef struct {
Vertex vertices[MAX_VERTICES];
int edges[MAX_VERTICES][MAX_VERTICES];
int num_vertices;
} Graph;
void init_graph(Graph* graph, int num_vertices) {
graph->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++) {
graph->vertices[i].visited = 0;
graph->vertices[i].vertex = i;
for (int j = 0; j < num_vertices; j++) {
graph->edges[i][j] = 0;
}
}
}
void add_edge(Graph* graph, int start_vertex, int end_vertex) {
graph->edges[start_vertex][end_vertex] = 1;
graph->edges[end_vertex][start_vertex] = 1;
}
void print_graph(Graph* graph) {
printf("Graph:\n");
for (int i = 0; i < graph->num_vertices; i++) {
printf("%d: ", graph->vertices[i].vertex);
for (int j = 0; j < graph->num_vertices; j++) {
if (graph->edges[i][j] == 1) {
printf("%d ", graph->vertices[j].vertex);
}
}
printf("\n");
}
}
int main() {
Graph graph;
init_graph(&graph, 4);
add_edge(&graph, 0, 1);
add_edge(&graph, 0, 2);
add_edge(&graph, 1, 2);
add_edge(&graph, 2, 3);
print_graph(&graph);
return 0;
}
```
存储结构示意图:
```
Graph:
0: 1 2
1: 0 2
2: 0 1 3
3: 2
```
其中,每个数字代表一个顶点,数字后面的空格后跟的数字代表与该顶点相连的其他顶点。例如,`0: 1 2`表示顶点0与顶点1、顶点2相连。
实现图的存储,输出存储结构示意图的代码c语言
以下是使用邻接矩阵和邻接表两种方式实现图的存储,并输出存储结构示意图的 C 代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 使用邻接矩阵实现图的存储,并输出存储结构示意图
#define MAX_VERTICES 10
typedef struct Graph {
int vertices;
int adj_matrix[MAX_VERTICES][MAX_VERTICES];
} Graph;
Graph* create_graph(int vertices) {
Graph* g = (Graph*) malloc(sizeof(Graph));
g->vertices = vertices;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
g->adj_matrix[i][j] = 0;
}
}
return g;
}
void add_edge(Graph* g, int v1, int v2, int weight) {
g->adj_matrix[v1][v2] = weight;
g->adj_matrix[v2][v1] = weight; // 对于无向图,邻接矩阵是对称的
}
void print_graph(Graph* g) {
for (int i = 0; i < g->vertices; i++) {
for (int j = 0; j < g->vertices; j++) {
printf("%d ", g->adj_matrix[i][j]);
}
printf("\n");
}
}
int main() {
Graph* g = create_graph(4);
add_edge(g, 0, 1, 1);
add_edge(g, 0, 2, 1);
add_edge(g, 1, 2, 1);
add_edge(g, 1, 3, 1);
add_edge(g, 2, 3, 1);
print_graph(g);
return 0;
}
// 输出:
// 0 1 1 0
// 1 0 1 1
// 1 1 0 1
// 0 1 1 0
// 使用邻接表实现图的存储,并输出存储结构示意图
typedef struct Node {
int val;
struct Node* next;
} Node;
typedef struct Graph {
int vertices;
Node* adj_list[MAX_VERTICES];
} Graph;
Graph* create_graph(int vertices) {
Graph* g = (Graph*) malloc(sizeof(Graph));
g->vertices = vertices;
for (int i = 0; i < vertices; i++) {
g->adj_list[i] = NULL;
}
return g;
}
void add_edge(Graph* g, int v1, int v2) {
// 添加 v2 到 v1 的链表中
Node* node = (Node*) malloc(sizeof(Node));
node->val = v2;
node->next = g->adj_list[v1];
g->adj_list[v1] = node;
// 添加 v1 到 v2 的链表中
node = (Node*) malloc(sizeof(Node));
node->val = v1;
node->next = g->adj_list[v2];
g->adj_list[v2] = node;
}
void print_graph(Graph* g) {
for (int i = 0; i < g->vertices; i++) {
printf("%d: ", i);
Node* node = g->adj_list[i];
while (node) {
printf("%d -> ", node->val);
node = node->next;
}
printf("None\n");
}
}
int main() {
Graph* g = create_graph(4);
add_edge(g, 0, 1);
add_edge(g, 0, 2);
add_edge(g, 1, 2);
add_edge(g, 1, 3);
add_edge(g, 2, 3);
print_graph(g);
return 0;
}
// 输出:
// 0: 2 -> 1 -> None
// 1: 3 -> 2 -> 0 -> None
// 2: 3 -> 1 -> 0 -> None
// 3: 2 -> 1 -> None
```
以上代码中,使用 `Graph` 结构体来表示图,`create_graph` 函数用于创建图,`add_edge` 函数用于添加边,`print_graph` 函数用于输出存储结构示意图。其中使用 `adj_matrix` 数组来存储邻接矩阵,使用 `adj_list` 数组来存储邻接表,每个链表的头结点表示该顶点相邻的顶点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)