欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之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

例如下图

 数据结构之C++实现图(Graph)(无主函数)

存储矩阵为

数据结构之C++实现图(Graph)(无主函数)

代码如下:使用二维数组实现

#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;
};

邻接表存储:用数组存储顶点,用链表存储和顶点相关联的边。边值为当前顶点在数组中的下标

如图:

 数据结构之C++实现图(Graph)(无主函数)

用邻接表存储如下:

 数据结构之C++实现图(Graph)(无主函数)

 

代码如下所示:使用链表实现

各函数名同图邻接矩阵

#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;
};


相关标签: Graph

上一篇:

下一篇: