图-邻接矩阵.cpp

这个是有关数据结构中有关图的存储问题,包含了邻接表,和邻接巨阵的存储代码

#include<iostream>
using namespace std;

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

typedef int Status;
typedef int VRType;
typedef char InfoType;
typedef int VertexType;

typedef enum {DG, DN, UDG, UDN} GraphKind;
typedef struct ArcCell
{
	VRType adj;
	InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct 
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum, arcnum;
	GraphKind kind;
}MGraph;

Status CreateGraphUDG(MGraph &Ga)
{
	int i, j, n, e, k;
	int lasti[MAX_VERTEX_NUM], lastj[MAX_VERTEX_NUM], flag;
	cout << "请输入要建立的图的顶点数:n=";
	cin >> n;
	cout << endl;
	cout << "请输入要建立的图的边数:e=";
	cin >> e;
	cout << endl;
	Ga.vexnum = n;
	Ga.arcnum = e;
	for (i=1;i<=Ga.vexnum;i++)
	{
		for (j=1;j<=Ga.vexnum;j++)
		{
			Ga.arcs[i][j].adj = 0;
		}
	}
	for (k=1;k<=Ga.arcnum;k++)
	{
		cout << "请输入第" << k << "条边的起点:";
		cin >>i;
		cout << "请输入第" << k << "条边的终点:";
		cin >>j;
		for (int ks=k;ks>0;ks--)
		{
			if (lasti[ks]==i && lastj[ks]==j)
			{
				flag = 1;
			}
		}
		if (i>n || j>n || i==j)
		{
			flag = 1;
		}
		if (flag ==1)
		{
			cout << "您输入的数据有误！" << endl;
			k--;
			flag = 0;
			continue;
		}
		lasti[k] = i;
		lastj[k] = j;
		Ga.arcs[i][j].adj = 1;
		Ga.arcs[j][i].adj = 1;
		cout << endl;
	}
	return OK;
}

Status PrintGraphUDG(MGraph Ga)
{
	int i, j;
	for (i=1;i<=Ga.vexnum;i++)
	{
		for (j=1;j<=Ga.vexnum;j++)
		{
			cout << Ga.arcs[i][j].adj << "  ";
		}
		cout << endl;
	}
	for (i=1;i<=Ga.vexnum;i++)
	{
		int k=0;
		for (j=1;j<=Ga.vexnum;j++)
		{
			if(Ga.arcs[i][j].adj)
			{
				++k;
				cout << "V" << i << "--" << "V" << j << " ";
			}
		}
		cout << "V" << i << "的度为:" << k <<" ";
		cout << endl;
	}
	return OK;
}

Status CreateGraphDG(MGraph &Ga)
{
	int i, j, n, e, k;
	cout << "请输入要建立的有向图的顶点数:n=";
	cin >> n;
	cout << endl;
	cout << "请输入要建立的有向图的边数:e=";
	cin >> e;
	cout << endl;
	Ga.vexnum = n;
	Ga.arcnum = e;
	for (i=1;i<=Ga.vexnum;i++)
	{
		for (j=1;j<=Ga.vexnum;j++)
		{
			Ga.arcs[i][j].adj = 0;
		}
	}
	for (k=1;k<=Ga.arcnum;k++)
	{
		cout << "请输入第" << k << "条边的起点:";
		cin >>i;
		cout << "请输入第" << k << "条边的终点:";
		cin >>j;
		if (i>n || j>n || i==j)
		{
			cout << "您输入的数据有误！" << endl;
			k--;
			continue;
		}
		Ga.arcs[i][j].adj = 1;
		cout << endl;
	}
	return OK;
}

Status PrintGraphDG(MGraph Ga)
{
	int i, j;
	for (i=1;i<=Ga.vexnum;i++)
	{
		for (j=1;j<=Ga.vexnum;j++)
		{
			cout << Ga.arcs[i][j].adj << "  ";
		}
		cout << endl;
	}
	for (i=1;i<=Ga.vexnum;i++)
	{
		int k1, k2;
		k1 = k2 =0 ;
		for (j=1;j<=Ga.vexnum;j++)
		{
			if (Ga.arcs[i][j].adj)
			{
				++k1;
				cout<<"V"<<i<<"->"<<"V"<<j<<" ";
			}
			if (Ga.arcs[j][i].adj)
			{
				++k2;
			}
		}
		cout << "V" << i << "的出度为:" << k1 << " ";
		cout << "V" << i << "的入度为:" << k2 << " ";
		cout << endl;
	}
	return OK;
}

void main(void)
{
	MGraph Ga;
	int select;
	do
	{
		cout << "***********图程序功能选择菜单***********\n";
		cout << "*          1.无向图的建立              *\n";
		cout << "*          2.无向图的输出              *\n";
		cout << "*          3.有向图的建立              *\n";
		cout << "*          4.有向图的输出              *\n";
	    cout << "*          0.退出程序!                 *\n";
		cout << "****************************************\n";
		
		cout << endl << "请输入您的选择：" << endl;
		cin >> select;
		switch (select)
		{
		case 1:
			if (CreateGraphUDG(Ga)==ERROR)
			{
				cout << endl<<"创建有向图失败!" << endl;
			}
			else 
			{
				cout << endl << "有向图创建成功!" << endl;
			}
	    	break;
		case 2:
				PrintGraphUDG(Ga);
				break;
		case 3:
			if (CreateGraphDG(Ga)==ERROR) 
			{
				cout << endl << "创建失败!" << endl;
			}
			else 
			{
				cout << endl << "无向图创建成功!" << endl;
			}
			break;
		case 4:
			PrintGraphDG(Ga);
			break;
		case 0:
			cout << "操作结束，退出程序!" << endl;
			break;
		default:
			cout << "输入的数字是无效的!\n" << endl;
			break;
		}
        cout << endl << endl;
	}while (select!=0);
}