数据结构与算法----4.2 用数组存储图：1、插入一个顶点2、删除一条弧3、删

[c++]代码库

#include <iostream>
#include <fstream>
using namespace std;
const int Infinity=-1;
typedef char VexType;
struct VexCell//顶点的信息
{
	VexType data;//顶点数据
	bool visited;//是否被访问过
};
struct ArcCell//弧的信息(结构体)
{
	int adj;     
};
const MVN=21;
struct MGraph
{
	VexCell vexs[MVN];//顶点数组
	ArcCell arcs[MVN][MVN];//邻接矩阵
	int kind,vexnum,arcnum;//类型，顶点数，弧数
};
int LocateVex(MGraph &G,VexType v);//查找顶点
bool InsertVex(MGraph &G,VexType u);//插入顶点
bool InsertArc(MGraph &G,VexType u,VexType v,int w=1);//插入弧
bool DeleteArc(MGraph &G,VexType u,VexType v);//删除弧
bool DeleteVex(MGraph &G,VexType v);//删除顶点
void CreateGraph(MGraph&G,char fn[]);//建立图
void Show(MGraph &G);
int main()
{
	
	int count1=0;
	int count2=0;
	MGraph G;
	char fn[]="fn.txt";
	CreateGraph(G,fn);
	Show(G);
	VexType x='s',y='a',z='b',f='a';
	cout<<"插入顶点:"<<x<<endl;
	InsertVex(G,x);
	Show(G);
	cout<<"删除弧的两个顶点:"<<y<<z<<endl;
	DeleteArc(G,y,z);
	Show(G);
	cout<<"要删除的顶点："<<z<<endl;
	DeleteVex(G,f);
	Show(G);
	return 0;
}

bool InsertVex(MGraph&G,VexType u)
{
	int i;
	if(G.vexnum+1>MVN)return false;
	i=LocateVex(G,u);
	if(i>0)return false;
	G.vexnum++;
	G.vexs[G.vexnum].data=u;
	for(i=1;i<=G.vexnum;i++)
		G.arcs[i][G.vexnum].adj=G.arcs[G.vexnum][i].adj=Infinity;
	return true;
}
bool InsertArc(MGraph&G,VexType u,VexType v,int w)
{
	int i,j;
	i=LocateVex(G,u);if(i==0)return false;
	j=LocateVex(G,v);
	if(j==0||j==i||G.arcs[i][j].adj!=Infinity)return false;
	G.arcs[i][j].adj=w;
	G.arcnum++;
	if(G.kind>=3)
	{
		G.arcs[j][i].adj=w;
	    G.arcnum++;
	}
	return true;
}
int LocateVex(MGraph&G,VexType v)
{
	int i;
	for(i=G.vexnum;i>0&&G.vexs[i].data!=v;i--);
	return i;
}
bool DeleteArc(MGraph& G,VexType u,VexType v)
{
	int i,j;
	i=LocateVex(G,u);if(i==0)return false;
	j=LocateVex(G,v);
	if(j==0||G.arcs[i][j].adj==Infinity)return false;
	G.arcs[i][j].adj=Infinity;
	G.arcnum--;
	if(G.kind>=3)
	{
		G.arcs[j][i].adj=Infinity;G.arcnum--;
	}
	return true;
}
bool DeleteVex(MGraph &G,VexType v)
{
	int i,j;
	j=LocateVex(G,v);
	G.vexs[j]=G.vexs[G.vexnum];
	for(i=1;i<=G.vexnum;i++)
	{
		if(G.arcs[i][j].adj!=Infinity)G.arcnum--;
		if(G.arcs[j][i].adj!=Infinity)G.arcnum--;
	}
	if(j<G.vexnum)
	{
		for(i=1;i<=G.vexnum;i++)
			G.arcs[i][j]=G.arcs[i][G.vexnum];
		for(i=1;i<=G.vexnum;i++)
			G.arcs[j][i]=G.arcs[i][G.vexnum];
	}
	G.vexnum--;
	return true;
}
void CreateGraph(MGraph&G,char fn[])
{
	int i,j,w;VexType u,v;ifstream f;
	f.open(fn);f>>G.kind;i=0;
	while(true)
	{
		f>>u;if(u=='#')break; i++;G.vexs[i].data=u;
	}
	G.vexnum=i;
	for(i=1;i<=G.vexnum;i++)
		for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=Infinity;
	G.arcnum=0;
	while(true)//边
	{
		f>>u>>v;if(u=='#'||v=='#')break;
		if(G.kind==1||G.kind==3)
			w=1;
		else f>>w;
		InsertArc(G,u,v,w);
	}
	f.close();
}
void Show(MGraph &G)
{
	int i=1,j=1;
	cout<<"所有顶点为：";
	for(i;i<=G.vexnum;i++)
		cout<<G.vexs[i].data<<" ";
	cout<<endl<<"所有弧为：";
	if(G.kind==1)
	{
		for(i=1;i<=G.vexnum;i++)
			for(j=1;j<= G.vexnum;j++)
				if(G.arcs[i][j].adj==1)
					cout<<"<"<<G.vexs[i].data<<","<<G.vexs[j].data<<"> ";
	}
	else
	{
		for(i=1;i<=G.vexnum;i++)
			for(j=1;j<i;j++)
				if(G.arcs[i][j].adj==1)
					cout<<"("<<G.vexs[i].data<<","<<G.vexs[j].data<<") ";
	}
	cout << endl;
}

//fn.txt
1
a b c #
a b
b c
a c
# #