学步园

对于图的一种表示方式，我觉得邻接矩阵是非常易于理解的一种结构，使用一个一维数组来存放各个顶点，用一个二维数组的下标来表示相应的顶点数组中的顶点，用二维数组的值来表示是否存在指向的关系。对于网，其值则可以表示相应的权值。

header.h

#include<iostream>
#include<iomanip>
using namespace std;
const  int MaxVertexNum=20;
class MGraph
{
public:
	MGraph();
	~MGraph();
	int locateVex(int u);
	MGraph & InsertVex(int v);
	MGraph & DeleteVex(int v);
	MGraph & InsertArc(int v,int w);
	MGraph & DeleteArc(int v,int w);
	void DisPlay();
private:
	int vexs[MaxVertexNum];
	int arcs[MaxVertexNum][MaxVertexNum];
	int vexnum;
	int arcnum;
};

header.cpp

#include"header.h"
int MGraph::locateVex(int u)
{
	for(int i=0;i<vexnum;i++)
		if(u==vexs[i])
			return i;
	return -1;
}
MGraph::MGraph()
{
	int i,j;
	int v1,v2;
	cout<<"------请输入有向图的顶点个数和弧的个数：";
	cin>>vexnum>>arcnum;
	cout<<"------请输入各个顶点:    ";
	for(i=0;i<vexnum;i++)
			cin>>vexs[i];
	for(i=0;i<vexnum;i++)
	{
		for(j=0;j<vexnum;j++)
			arcs[i][j]=0;
	}
	for(i=0;i<arcnum;i++)
	{
		cout<<"-------请输入一条弧的起点和终点：";
		cin>>v1>>v2;
		int m=locateVex(v1);
		int n=locateVex(v2);
		arcs[m][n]=1;
	}
}//此处暂时以有向图为例，其他各个图可以此类推。
MGraph & MGraph::InsertVex(int v)
{
	if(vexnum>=MaxVertexNum)
	{
		cout<<"out  of  range！";
		exit(-1);
	}
	if(locateVex(v)>=0)
	{
		cout<<"顶点已存在！";
		exit(-1);
	}
	vexs[vexnum]=v;
	for(int i=0;i<=vexnum;i++)
	{
		arcs[vexnum][i]=0;
		arcs[i][vexnum]=0;
	}
	vexnum++;
	return *this;
}
MGraph &  MGraph::DeleteVex(int v)
{
	int delpos,vrtype=0,i,j;
	delpos=locateVex(v);
	if(delpos<0)
	{
		cout<<"顶点不存在！";
		exit(1);
	}
	for(i=0;i<vexnum;i++)
		if(arcs[i][delpos]!=vrtype)
			arcnum--;
	for(j=0;j<vexnum;j++)
		if(arcs[delpos][j]!=vrtype)
			arcnum--;
	for(i=delpos+1;i<vexnum;i++)
		vexs[i-1]=vexs[i];
	for(i=0;i<vexnum;i++)
		for(j=delpos+1;j<vexnum;j++)
			arcs[i][j-1]=arcs[i][j];
	for(i=0;i<vexnum;i++)
		for(j=delpos+1;j<vexnum;j++)
			arcs[j-1][i]=arcs[j][i];
	vexnum--;
	return *this;
}
MGraph & MGraph::InsertArc(int v,int w)
{
	int v1,w1;
	v1=locateVex(v);
	w1=locateVex(w);
	if(v1<0||w1<0)
	{
		cout<<"顶点不存在！";
		exit(1);
	}
	arcnum++;
	arcs[v1][w1]=1;
	return *this;
}
MGraph & MGraph::DeleteArc(int v,int w)
{
	int v1,w1;
	v1=locateVex(v);
	w1=locateVex(w);
	if(v1<0||w1<0)
	{
		cout<<"弧不存在！";
		exit(1);
	}
	arcs[v1][w1]=0;
	arcnum--;
	return *this;
}
void MGraph::DisPlay()
{
	int i,j;
	cout<<vexnum<<"个顶点"<<arcnum<<"条弧的有向图"<<endl;
	cout<<"顶点为";
	for(i=0;i<vexnum;i++)
		cout<<vexs[i]<<"  ";
	cout<<"邻接矩阵为："<<endl;
	for(i=0;i<vexnum;i++)
	{
		for(j=0;j<vexnum;j++)
			cout<<setw(5)<<arcs[i][j]<<"\t";
		cout<<endl;
	}
}
MGraph::~MGraph()
{
	vexnum=0;
	arcnum=0;
}

main.cpp

#include"header.h"
int main()
{
	MGraph mg;
	mg.DisPlay();
	int k1=9;
	mg.InsertVex(k1);
	int k2=10;
	mg.InsertVex(k2);
	mg.DisPlay();
	mg.InsertArc(k1,k2);
	mg.DisPlay();
	mg.DeleteVex(k1);
	mg.DeleteVex(k2);
	mg.DisPlay();
	system("pause");
	return 0;
}