试在邻接矩阵存储结构上实现图的基本操作InsertVex(G,v);InsertArc(G,v,w);DeleteVex(G,v);DeleteArc(G,v,w)
时间: 2023-11-18 08:02:59 浏览: 219
C++ 邻接矩阵
好的,针对您的问题,我可以给出如下实现:
假设邻接矩阵存储结构为:
```c++
#define MaxVertexNum 100 //最大顶点数
typedef int Vertex; //顶点类型
typedef int WeightType; //边的权值类型
typedef char DataType; //顶点储存的数据类型
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; //顶点数
int Ne; //边数
WeightType G[MaxVertexNum][MaxVertexNum]; //邻接矩阵
DataType Data[MaxVertexNum]; //存顶点的数据
};
typedef PtrToGNode MGraph; //以邻接矩阵存储的图类型
```
其中,G[i][j]表示顶点i和顶点j之间的边的权重,如果G[i][j]==0,表示i和j之间没有边相连。
InsertVex(G,v)的实现:
```c++
bool InsertVex(MGraph &G, Vertex v)
{
if (G->Nv==MaxVertexNum) return false; //顶点已满,无法插入
G->Data[G->Nv]=v; //插入顶点v的数据
for (int i=0; i<=G->Nv; i++) {
G->G[i][G->Nv]=0; //初始化新顶点与其他顶点之间的边
G->G[G->Nv][i]=0; //初始化其他顶点与新顶点之间的边
}
G->Nv++; //顶点数加1
return true;
}
```
InsertArc(G,v,w)的实现:
```c++
bool InsertArc(MGraph &G, Vertex v, Vertex w, WeightType weight)
{
if (v<0 || v>=G->Nv || w<0 || w>=G->Nv) return false; //v或w越界,无法插入边
if (G->G[v][w]!=0) return false; //边<v, w>已存在,无法插入
G->G[v][w]=weight; //插入边<v, w>
G->Ne++; //边数加1
return true;
}
```
DeleteVex(G,v)的实现:
```c++
bool DeleteVex(MGraph &G, Vertex v)
{
if (v<0 || v>=G->Nv) return false; //v越界,无法删除
for (int i=0; i<G->Nv; i++) {
if (G->G[i][v]!=0) { //如果存在边<i, v>,则删除边<i, v>
G->G[i][v]=0;
G->Ne--;
}
if (G->G[v][i]!=0) { //如果存在边<v, i>,则删除边<v, i>
G->G[v][i]=0;
G->Ne--;
}
}
G->Data[v]=0; //删除顶点v的数据
for (int i=v; i<G->Nv-1; i++) {
G->Data[i]=G->Data[i+1]; //顶点数据前移
}
for (int i=0; i<G->Nv; i++) {
for (int j=v; j<G->Nv-1; j++) {
G->G[i][j]=G->G[i][j+1]; //邻接矩阵中顶点前移
}
}
for (int i=0; i<G->Nv; i++) {
G->G[i][G->Nv-1]=0; //清空新顶点所在的列
G->G[G->Nv-1][i]=0; //清空新顶点所在的行
}
G->Nv--; //顶点数减1
return true;
}
```
DeleteArc(G,v,w)的实现:
```c++
bool DeleteArc(MGraph &G, Vertex v, Vertex w)
{
if (v<0 || v>=G->Nv || w<0 || w>=G->Nv) return false; //v或w越界,无法删除边
if (G->G[v][w]==0) return false; //边<v, w>不存在,无法删除
G->G[v][w]=0; //删除边<v, w>
G->Ne--; //边数减1
return true;
}
```
以上就是在邻接矩阵存储结构上实现图的基本操作InsertVex(G,v)、InsertArc(G,v,w)、DeleteVex(G,v)、DeleteArc(G,v,w)的代码实现。
阅读全文