分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: 1.增加一个新顶点v,InsertVex(G, v); 2.删除顶点v及其相关的边,DeleteVex(G, v); 3.增加一条边<v,w>,InsertArc(G, v, w); 4.删除一条边<v,w>,DeleteArc(G, v, w)。
时间: 2024-02-11 11:07:17 浏览: 24
好的,我会根据你的要求进行回答。以下是邻接矩阵和邻接表的实现。
邻接矩阵:
```
#define MaxVertexNum 100 // 最大顶点数
typedef struct {
int vertex[MaxVertexNum]; // 顶点信息
int arc[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
int vexnum, arcnum; // 顶点数和边数
} MGraph;
// 在图 G 中插入顶点 v
void InsertVex(MGraph *G, int v) {
if (G->vexnum == MaxVertexNum) {
printf("Error: The graph is full!\n");
return;
}
G->vertex[G->vexnum++] = v;
int i;
for (i = 0; i < G->vexnum; i++) {
G->arc[i][G->vexnum - 1] = 0;
G->arc[G->vexnum - 1][i] = 0;
}
}
// 在图 G 中删除顶点 v 及其相关的边
void DeleteVex(MGraph *G, int v) {
int i, j;
for (i = 0; i < G->vexnum; i++) {
if (i == v) continue;
for (j = v; j < G->vexnum - 1; j++) {
G->arc[i][j] = G->arc[i][j + 1];
}
for (j = v; j < G->vexnum - 1; j++) {
G->arc[j][i] = G->arc[j + 1][i];
}
}
for (i = v; i < G->vexnum - 1; i++) {
G->vertex[i] = G->vertex[i + 1];
}
G->vexnum--;
for (i = 0; i < G->vexnum; i++) {
G->arc[G->vexnum][i] = 0;
G->arc[i][G->vexnum] = 0;
}
}
// 在图 G 中插入一条边 <v, w>
void InsertArc(MGraph *G, int v, int w) {
if (v >= G->vexnum || w >= G->vexnum) {
printf("Error: Invalid vertex!\n");
return;
}
G->arc[v][w] = 1;
}
// 在图 G 中删除一条边 <v, w>
void DeleteArc(MGraph *G, int v, int w) {
if (v >= G->vexnum || w >= G->vexnum) {
printf("Error: Invalid vertex!\n");
return;
}
G->arc[v][w] = 0;
}
```
邻接表:
```
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;
typedef struct {
VNode vertex[MaxVertexNum]; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 在图 G 中插入顶点 v
void InsertVex(ALGraph *G, int v) {
if (G->vexnum == MaxVertexNum) {
printf("Error: The graph is full!\n");
return;
}
G->vertex[G->vexnum].data = v;
G->vertex[G->vexnum].firstarc = NULL;
G->vexnum++;
}
// 在图 G 中删除顶点 v 及其相关的边
void DeleteVex(ALGraph *G, int v) {
int i;
ArcNode *p, *q;
for (p = G->vertex[v].firstarc; p != NULL; p = q) {
q = p->nextarc;
free(p);
G->arcnum--;
}
G->vertex[v].data = 0;
G->vertex[v].firstarc = NULL;
for (i = 0; i < G->vexnum; i++) {
if (i == v) continue;
for (p = G->vertex[i].firstarc; p != NULL; p = p->nextarc) {
if (p->adjvex == v) {
q->nextarc = p->nextarc;
free(p);
G->arcnum--;
break;
}
q = p;
}
}
G->vexnum--;
}
// 在图 G 中插入一条边 <v, w>
void InsertArc(ALGraph *G, int v, int w) {
if (v >= G->vexnum || w >= G->vexnum) {
printf("Error: Invalid vertex!\n");
return;
}
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = w;
p->nextarc = G->vertex[v].firstarc;
G->vertex[v].firstarc = p;
G->arcnum++;
}
// 在图 G 中删除一条边 <v, w>
void DeleteArc(ALGraph *G, int v, int w) {
if (v >= G->vexnum || w >= G->vexnum) {
printf("Error: Invalid vertex!\n");
return;
}
ArcNode *p, *q;
for (p = G->vertex[v].firstarc; p != NULL; p = p->nextarc) {
if (p->adjvex == w) {
if (p == G->vertex[v].firstarc) {
G->vertex[v].firstarc = p->nextarc;
} else {
q->nextarc = p->nextarc;
}
free(p);
G->arcnum--;
break;
}
q = p;
}
}
```
相关推荐
![](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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)