a.txt

求出图的入度和出度 并求出图中回路长度为3的回路条数

#include<iostream.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM  20//最大顶点个数 

typedef struct ArcCell
{
	int adj;//VRType是顶点关系类型。对无权图，用1或0表示两结点相邻否
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
	char vexs[MAX_VERTEX_NUM];//顶点向量
	AdjMatrix arcs;//邻接矩阵
	int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;

int LocateVex(MGraph&G,char&c)
//确定顶点c在G中的位置
{
	for(int i=1;i<=G.vexnum;i++)
		if(G.vexs[i]==c)//若c和数组中的某个元素相同,说则c在数组中
			return i;//返回顶点在图中的位置
		return 0;
}

int CreatUDG(MGraph&G)//采用数组（邻接矩阵）表示法，构造无向图G
{
	char v1,v2;
	cout<<"请输入该图中结点的总数和弧的总数：";
	cin>>G.vexnum>>G.arcnum;//输入当前顶点数和弧数
	cout<<"请输入各结点的名称：";
	for(int i=0;i<G.vexnum;i++)
	{
		cin>>G.vexs[i];//构造顶点向量
	}
	for(i=0;i<G.vexnum;i++)
	{
		for(int j=0;j<G.vexnum;j++)
		{
			G.arcs[i][j].adj=0;
		}
	}
	
    for(int k=0;k<G.arcnum;k++)
	{
		cout<<"请输入第"<<k+1<<"条有向边依附的结点："<<endl;
		cin>>v1>>v2;
		int a=LocateVex(G,v1);
		int b=LocateVex(G,v2);
		G.arcs[a][b].adj=1;
	}
	cout<<"有向图构造成功！"<<endl;
	return 1;
}

void Count(MGraph&G)    //求图的入度与出度
{
	int i,j,k;
	for(i=0;i<G.vexnum;i++)
	{
		int deg_in=0,deg_out=0;
		cout<<"顶点"<<G.vexs[i]<<"的入度为:";
		for(j=0;j<G.vexnum;j++)
		{
			deg_in+=G.arcs[j][i].adj;
		}
		cout<<deg_in<<endl;
		//deg_in=0;

		cout<<"顶点"<<G.vexs[i]<<"的出度为:";
		for(k=0;k<G.vexnum;k++)
		{
			deg_out+=G.arcs[i][k].adj;
		}
		cout<<deg_out<<endl;
		//deg_out=0;
	}
	cout<<endl;
}
	

int Print(MGraph G)//将图的矩阵输出
{
	cout<<"该图的矩阵表示如下："<<endl;
	for(int i=0;i<G.vexnum;i++)
	{
		for(int j=0;j<G.vexnum;j++)
		{
			cout<<G.arcs[i][j].adj<<" ";
		}
		cout<<endl;
	}
	return 1;
}

int HuiLu(MGraph&G)
{
	int m=0;
	for(int i=0;i<G.vexnum;i++)
	{
		for(int j=0;j<G.vexnum;j++)
		{
			for(int k=0;k<G.vexnum;k++)
			{
				G.arcs[i][j].adj=G.arcs[i][k].adj*G.arcs[k][j].adj;
                G.arcs[i][j].adj=G.arcs[i][k].adj*G.arcs[k][j].adj;
			}
		m+=G.arcs[i][j].adj;	
		}
	}
	cout<<"长度为3的回路条数为："<<m<<endl;
	return 1;
}
	
void main()
{
	MGraph G;
	CreatUDG(G);
	Print(G);
	Count(G);
	HuiLu(G);
}