数据结构之C++实现图(Graph)(无主函数)
程序员文章站
2023-12-27 08:46:21
...
图:由顶点的有穷非空集合和顶点之间边的集合组成,表示为G(V,E),V表示为顶点的集合,E表示为边的集合。
两种存储方式:邻接矩阵和邻接表
邻接矩阵存储:
1. 存储顶点:用一个连续的空间存储n个顶点,如有5个顶点{a,b,c,d,e},可以存储为char VertexList[] = {‘a’,’b’,’c’,’d’,’e’};
2. 存储顶点之间的边:将由n个顶点组成的边用一个n*n的矩阵来存储,如果两个顶点之间有边,则表示为1,否则为0。例如矩阵为int Edge[n][n],如果a-b顶点有边,则将Edge[a下标][b下标] = 1。
例如下图
存储矩阵为
代码如下:使用二维数组实现
#include<iostream>
using namespace std;
#define SIZE 10
///////////////////////////////图邻接矩阵
class Graph
{
public:
Graph()
{
MaxVertex = SIZE;
NumVertex = NumEdge = 0;//顶点数和边数初始化为0
Vertex = new char[MaxVertex];
Edge = new int*[MaxVertex];//int *Edge[10];
int i,j;
for(i = 0;i<MaxVertex;i++)
Edge[i] = new int[MaxVertex]; //Edge[10][10]
for(i = 0;i<MaxVertex;i++)
{
for(j = 0;j<MaxVertex;j++)
Edge[i][j] = 0;
}
}
void InsertVertex(char v)//插入一个顶点v
{
if(NumVertex >= MaxVertex)
return;
Vertex[NumVertex++] = v;
}
int GetVertexI(char v)//查找一个顶点v
{
int i;
for(i = 0;i<NumVertex;i++)
{
if(Vertex[i] == v)
return i;
}
return -1;
}
void InsertEdge(char v1,char v2)//插入一条由点v1和v2组成的边
{
int p1 = GetVertexI(v1);
int p2 = GetVertexI(v2);
if(p1 == -1 || p2 == -1)
return;
Edge[p1][p2] = Edge[p2][p1] = 1;
NumEdge++;
}
void ShowGraph()//打印函数
{
int i,j;
cout<<" ";
for(i = 0;i<NumVertex;i++)
cout<<Vertex[i]<<" ";
cout<<endl;
for(i = 0;i<NumVertex;i++)
{
cout<<Vertex[i]<<" ";
for(j = 0;j<NumVertex;j++)
cout<<Edge[i][j]<<" ";
cout<<endl;
}
}
int GetEdgeNum(char v)//获取图的边数
{
int p = GetVertexI(v);
if(p == -1)
return 0;
int n = 0;
for(int i = 0;i<NumVertex;i++)
{
if(Edge[p][i] == 1)
n++;
}
return n;
}
void DeleteVertex(char v)//删除一个顶点
{
int p = GetVertexI(v);
if(p == -1)
return;
int i,j;
int n=GetEdgeNum(v);
for(i = p;i<NumVertex-1;i++) //顶点先删除
Vertex[i] = Vertex[i+1];
for(i = p;i<NumVertex-1;i++) //行上移
{
for(j = 0;j<NumVertex;j++)
Edge[i][j] = Edge[i+1][j];
}
for(i = 0;i<NumVertex-1;i++) //列左移
{
for(j = p;j<NumVertex-1;j++)
{
Edge[i][j] = Edge[i][j+1];
}
}
NumVertex--;
NumEdge-=n;
}
void DeleteEdge(char v1,char v2)//删除顶点v1和v2之间的边
{
int p1 = GetVertexI(v1);
int p2 = GetVertexI(v2);
if(p1 == -1 || p2 == -1)
return;
if(Edge[p1][p2] == 0)
return;
Edge[p1][p2] = Edge[p2][p1] = 0;
NumEdge--;
}
~Graph()
{
delete []Vertex;
Vertex = NULL;
for(int i=0;i<MaxVertex;i++)
{
delete []Edge[i];
Edge[i] = NULL;
}
delete []Edge;
Edge = NULL;
NumVertex=0;//析构函数释放空间可不写
}
private:
int MaxVertex;
int NumVertex;
int NumEdge;
char *Vertex;
int **Edge;
};
邻接表存储:用数组存储顶点,用链表存储和顶点相关联的边。边值为当前顶点在数组中的下标
如图:
用邻接表存储如下:
代码如下所示:使用链表实现
各函数名同图邻接矩阵
#include <iostream>
using namespace std;
#define SIZE 10
struct Edge
{
Edge(int v):destvalue(v),link(NULL){}
int destvalue;
Edge *link;
};
struct Vertex
{
Vertex():list(NULL){}
char data;
Edge *list;
};
class GraphLink
{
public:
GraphLink()
{
MaxVertex = SIZE;
NumVertex = NumEdge = 0;
VertexTable = new Vertex[MaxVertex];
}
void InsertVertex(char v)
{
if(NumVertex >= MaxVertex)
return;
VertexTable[NumVertex++].data = v;
}
int GetVertexI(char v)
{
for(int i = 0;i<NumVertex;i++)
{
if(VertexTable[i].data == v)
return i;
}
return -1;
}
void InsertEdge(char v1,char v2)
{
int p1 = GetVertexI(v1);
int p2 = GetVertexI(v2);
if(p1 == -1 || p2 == -1)
return;
//p1->p2
Edge *ed = new Edge(p2);
ed->link = VertexTable[p1].list;
VertexTable[p1].list = ed;
//p2->p1
ed = new Edge(p1);
ed->link = VertexTable[p2].list;
VertexTable[p2].list = ed;
NumEdge++;
}
void Show()
{
int i;
for(i = 0;i<NumVertex;i++)
{
cout<<VertexTable[i].data<<"->";
Edge *p = VertexTable[i].list;
while(p)
{
cout<<p->destvalue<<"->";
p = p->link;
}
cout<<"nul"<<endl;
}
}
void DeleteEdge(char v1,char v2)
{
int p1 = GetVertexI(v1);
int p2 = GetVertexI(v2);
if(p1 == -1 || p2 == -1)
return;
//p1->p2
Edge *p = VertexTable[p1].list;
Edge *s = NULL;
while(p && p->destvalue != p2)
{
s = p;
p = p->link;
}
if(p == NULL)
return;
if(s == NULL)
VertexTable[p1].list = p->link;
else
s->link = p->link;
delete p;
//p2->p1
p = VertexTable[p2].list;
s = NULL;
while(p && p->destvalue != p1)
{
s = p;
p = p->link;
}
if(s == NULL)
VertexTable[p2].list = p->link;
else
s ->link = p->link;
delete p;
p = NULL;
NumEdge--;
}
void DeleteVertex(char v)
{
int p = GetVertexI(v);
if(p == -1)
return;
//先删除和顶点相关联的边
Edge *s = NULL;
Edge *edp = VertexTable[p].list;//找到v的边
while(edp)
{
int destvalue = edp->destvalue;
Edge *q = VertexTable[destvalue].list;
s = NULL;
while(q && q->destvalue != p)
{
s = q;
q = q->link;
}
if(s == NULL)
VertexTable[destvalue].list = q->link;
else
s->link = q->link;
delete q;
q = NULL;
VertexTable[p].list = edp->link;
delete edp;
edp = VertexTable[p].list;
NumEdge--;
}
//删除顶点
NumVertex--;
//用最后一个覆盖删除的顶点
VertexTable[p].data = VertexTable[NumVertex].data;
VertexTable[p].list = VertexTable[NumVertex].list;
edp = VertexTable[p].list;
while(edp)
{
int destvalue = edp->destvalue;
s = VertexTable[destvalue].list;
while(s&&s->destvalue != NumVertex)
{
s = s ->link;
}
s->destvalue = p;
edp = edp->link;
}
}
~GraphLink()
{
Edge *p=NULL;
for(int i=0;i<NumVertex;++i)
{
p=VertexTable[i].list;
while(p)
{
VertexTable[i].list=p->link;
delete p;
p=VertexTable[i].list;
}
}
delete []VertexTable;
VertexTable=NULL;
}
private:
int MaxVertex;
int NumVertex;
int NumEdge;
Vertex *VertexTable;
};