数据结构与算法----4.1 用数组存储图 1、求一个顶点的出度2、求一个顶点的

[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);//插入弧
void CreateGraph(MGraph&G,char fn[]);//建立图
int  qiuru(MGraph&G,VexType &x);//顶点的入度
int  qiuchu(MGraph&G,VexType &x);//顶点的出度
void Show(MGraph &G);
int main()
{
	int count1=0;
	int count2=0;
	MGraph G;
	VexType fn[]="fn.txt";
	CreateGraph(G,fn);
	Show(G);VexType x='a';
	cout<<"顶点"<<x<<"的入度为："<<qiuru(G,x)<<endl;
	cout<<"顶点"<<x<<"的出度为："<<qiuchu(G,x)<<endl;


	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;
}
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;
}
int  qiuru(MGraph&G,VexType &x)
{
	int i,j;int count1=0;
	i=LocateVex(G,x);
	if(i==0)return -1;
	for(j=1;j<=G.vexnum;j++)
	{
		if(G.arcs[j][i].adj!=Infinity) count1++;
	}
	return count1;
}
int  qiuchu(MGraph&G,VexType &x)
{
	int i,j;int count2=0;
	i=LocateVex(G,x);
	if(i==0)return -1;
	for(j=1;j<=G.vexnum;j++)
	{
		if(G.arcs[i][j].adj!=Infinity) count2++;
	}
	return count2;
}

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