int InsertVex(AMGragh &G) {//在以邻接矩阵形式存储的无向图G上插入顶点 /**begin/ /**************end************/ }
时间: 2024-06-17 18:06:50 浏览: 10
函数名为InsertVex,作用是在邻接矩阵表示的无向图G中插入一个顶点。函数的参数为引用类型的AMGraph结构体,表示我们要修改的无向图。以下是函数的实现:
int InsertVex(AMGraph &G)
{
// 如果图已满,则无法插入新的顶点
if(G.vexnum == MAX_VERTEX_NUM)
{
cout<<"Error: the graph is full."<<endl;
return 0;
}
// 输入新顶点的信息
cout<<"Please input the vertex information:"<<endl;
VertexType v;
cin>>v;
// 在顶点表中添加新的顶点
G.vexs[G.vexnum] = v;
// 初始化新顶点的行和列
for(int i = 0; i < G.vexnum; i++)
{
G.arcs[G.vexnum][i] = 0;
G.arcs[i][G.vexnum] = 0;
}
// 更新顶点数目
G.vexnum++;
return 1;
}
相关问题
int InsertVex(ALGragh &G) {//在以邻接表形式存储的无向图G上插入顶点v
插入顶点v的过程可以按照以下步骤进行:
1. 创建一个新的顶点节点,表示顶点v的信息。
2. 将新的顶点节点添加到邻接表的末尾,并将其指针设置为NULL。
3. 对于每个已有的顶点节点,创建一个新的邻接点节点,并将其指针设置为NULL。
4. 将新的邻接点节点添加到邻接表末尾,并将其指针设置为NULL。
5. 将新的邻接点节点添加到该顶点节点的邻接点列表的末尾。
6. 将该顶点节点的指针设置为新的邻接点节点。
7. 在无向图中,需要同时修改与该顶点相邻的其他顶点节点的邻接点列表,将新的邻接点节点添加到其末尾,并将其指针设置为新的顶点节点。
8. 最后,修改无向图的顶点数加1。
具体的代码实现如下:
```C++
int InsertVex(ALGraph &G, VertexType v)
{
if(G.vexnum == MAX_VERTEX_NUM) // 图的顶点数已经达到最大值
return ERROR;
G.vertices[G.vexnum].data = v; // 创建新的顶点节点
G.vertices[G.vexnum].firstarc = NULL;
// 初始化邻接点列表
for(int i = 0; i < G.vexnum; i++)
{
ArcNode *p = new ArcNode;
p->adjvex = G.vexnum;
p->nextarc = NULL;
// 将新的邻接点节点添加到该顶点节点的邻接点列表的末尾
ArcNode *q = G.vertices[i].firstarc;
if(q == NULL)
G.vertices[i].firstarc = p;
else
{
while(q->nextarc != NULL)
q = q->nextarc;
q->nextarc = p;
}
}
// 在无向图中,需要同时修改与该顶点相邻的其他顶点节点的邻接点列表
ArcNode *p = new ArcNode;
p->adjvex = G.vexnum;
p->nextarc = NULL;
ArcNode *q = G.vertices[G.vexnum-1].firstarc;
if(q == NULL)
G.vertices[G.vexnum-1].firstarc = p;
else
{
while(q->nextarc != NULL)
q = q->nextarc;
q->nextarc = p;
}
G.vexnum++; // 修改顶点数加1
return OK;
}
```
其中,ALGraph 是邻接表存储结构的图类型,VertexType 是顶点数据类型。在这里,我们假设邻接表存储结构中的顶点节点和邻接点节点的数据类型分别为:
```C++
typedef struct ArcNode { // 邻接点
int adjvex; // 邻接点的位置
ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode { // 顶点
VertexType data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的当前顶点数和边数
} ALGraph;
```
int InsertVex(ALGragh &G) {//在以邻接表形式存储的无向图G上插入顶点v /**************begin************/
以下是在以邻接表形式存储的无向图G上插入顶点v的代码实现:
```c
int InsertVex(ALGraph &G, VertexType v)
{
// 判断图是否已满
if (G.vexnum == MAX_VERTEX_NUM)
{
return ERROR;
}
// 在图中查找是否已存在该顶点
int i = LocateVex(G, v);
if (i != -1)
{
return ERROR;
}
// 在邻接表中增加新顶点
G.xlist[G.vexnum].data = v;
G.xlist[G.vexnum].firstin = NULL;
G.xlist[G.vexnum].firstout = NULL;
G.vexnum++;
return OK;
}
```