1、无向图采用那接表作为储存结构,编写算法以实现:(1)求一个顶点的度 (2)往图中插入一个顶点 网 (3)往图中插入一条边 (4)删去图中某顶点 (5)删去图中某条边
时间: 2023-06-24 21:09:29 浏览: 29
以下是五个操作的算法实现:
1. 求一个顶点的度
```
int getDegree(Graph* g, int vertex) {
if(vertex < 0 || vertex >= g->num_vertices) {
return -1;
}
int degree = 0;
for(int i = 0; i < g->num_vertices; i++) {
if(g->adj_list[vertex][i] != 0) {
degree++;
}
}
return degree;
}
```
2. 往图中插入一个顶点
```
void addVertex(Graph* g) {
g->num_vertices++;
g->adj_list = realloc(g->adj_list, sizeof(int*) * g->num_vertices);
g->adj_list[g->num_vertices-1] = calloc(g->num_vertices, sizeof(int));
for(int i = 0; i < g->num_vertices-1; i++) {
g->adj_list[i] = realloc(g->adj_list[i], sizeof(int) * g->num_vertices);
g->adj_list[i][g->num_vertices-1] = 0;
}
}
```
3. 往图中插入一条边
```
void addEdge(Graph* g, int vertex1, int vertex2) {
if(vertex1 < 0 || vertex1 >= g->num_vertices || vertex2 < 0 || vertex2 >= g->num_vertices) {
return;
}
g->adj_list[vertex1][vertex2] = 1;
g->adj_list[vertex2][vertex1] = 1;
}
```
4. 删去图中某顶点
```
void removeVertex(Graph* g, int vertex) {
if(vertex < 0 || vertex >= g->num_vertices) {
return;
}
for(int i = 0; i < g->num_vertices; i++) {
if(g->adj_list[vertex][i] != 0) {
g->adj_list[vertex][i] = 0;
g->adj_list[i][vertex] = 0;
}
}
for(int i = vertex; i < g->num_vertices-1; i++) {
g->adj_list[i] = g->adj_list[i+1];
}
g->adj_list = realloc(g->adj_list, sizeof(int*) * (g->num_vertices-1));
g->num_vertices--;
for(int i = 0; i < g->num_vertices; i++) {
g->adj_list[i] = realloc(g->adj_list[i], sizeof(int) * (g->num_vertices));
}
}
```
5. 删去图中某条边
```
void removeEdge(Graph* g, int vertex1, int vertex2) {
if(vertex1 < 0 || vertex1 >= g->num_vertices || vertex2 < 0 || vertex2 >= g->num_vertices) {
return;
}
g->adj_list[vertex1][vertex2] = 0;
g->adj_list[vertex2][vertex1] = 0;
}
```
需要注意的是,这里的 Graph 结构体中,adj_list 是一个二维数组,用来存储邻接表。其中,adj_list[i] 存储了与第 i 个顶点相连的顶点信息,如果 adj_list[i][j] 不为 0,则表示 i 和 j 之间有一条边。在初始化时,需要将 adj_list 中的所有元素初始化为 0。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)