编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表,并在该存储结构上实现图的基本操作:insertvertex(g,v),insertarc(g,v,w),dele
时间: 2023-05-01 13:05:21 浏览: 123
该问题是关于编写算法的,根据输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表,并在该存储结构上实现插入新顶点、插入新弧、删除顶点和删除弧等基本操作。其中,建立邻接表的算法包括insertvertex(插入顶点)和insertarc(插入弧),删除顶点和弧的算法包括delvertex(删除顶点)和delarc(删除弧)。
相关问题
C语言编写算法,由依次输入顶点数目,弧的数目,各顶点的信息,各条弧的信息建立有向图的邻接表
好的,下面是一个简单的 C 语言算法,用于建立有向图的邻接表:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表中的弧节点
typedef struct ArcNode {
int adjvex; // 邻接顶点编号
int weight; // 弧的权值
struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;
// 定义邻接表中的顶点节点
typedef struct VertexNode {
char vertex; // 顶点信息
ArcNode *firstarc; // 指向第一条邻接弧的指针
} VertexNode;
// 定义图结构体
typedef struct {
VertexNode *vertices; // 顶点数组
int vexnum; // 顶点数目
int arcnum; // 弧的数目
} Graph;
// 创建邻接表
Graph* createGraph() {
int vexnum, arcnum, i, j;
scanf("%d %d", &vexnum, &arcnum);
// 初始化图
Graph *g = (Graph*) malloc(sizeof(Graph));
g->vexnum = vexnum;
g->arcnum = arcnum;
g->vertices = (VertexNode*) malloc(sizeof(VertexNode) * vexnum);
// 初始化邻接表中的各个顶点节点
for (i = 0; i < vexnum; i++) {
scanf(" %c", &g->vertices[i].vertex);
g->vertices[i].firstarc = NULL;
}
// 添加邻接表中的各个弧节点
for (i = 0; i < arcnum; i++) {
int start, end, weight;
scanf("%d %d %d", &start, &end, &weight);
// 创建新的弧节点
ArcNode *arcnode = (ArcNode*) malloc(sizeof(ArcNode));
arcnode->adjvex = end;
arcnode->weight = weight;
arcnode->nextarc = NULL;
// 将弧节点添加到起始顶点的邻接表中
if (g->vertices[start].firstarc == NULL) {
g->vertices[start].firstarc = arcnode;
} else {
ArcNode *p = g->vertices[start].firstarc;
while (p->nextarc != NULL) {
p = p->nextarc;
}
p->nextarc = arcnode;
}
}
return g;
}
int main() {
Graph *g = createGraph();
// 打印邻接表
int i;
for (i = 0; i < g->vexnum; i++) {
printf("%c -> ", g->vertices[i].vertex);
ArcNode *p = g->vertices[i].firstarc;
while (p != NULL) {
printf("%c(%d) ", g->vertices[p->adjvex].vertex, p->weight);
p = p->nextarc;
}
printf("\n");
}
return 0;
}
```
在这个算法中,我们首先读取顶点数目和弧的数目,然后创建一个新的图结构体,并初始化其中的顶点节点数组。接着,我们读取每个弧的信息,创建新的弧节点,并将其添加到起始顶点的邻接表中。最后,我们打印出邻接表。
希望这个算法对你有帮助!
编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
1. 首先输入顶点数目和弧的数目。
2. 接着输入各顶点的信息,可以用数组或结构体来存储。
3. 再输入各条弧的信息,包括起点、终点和权值等,也可以用数组或结构体来存储。
4. 建立邻接表,可以用链表来实现。对于每个顶点,创建一个链表,存储与该顶点相连的所有弧的信息。
5. 遍历所有弧的信息,将其插入到对应的链表中。
6. 最终得到有向图的邻接表表示。