邻接矩阵表示图

邻接矩阵适合表示稠密图：

#define MAXINT 32767   //表示极大值
#define MVNum 100 //邻接矩阵的最大顶点数
typedef char VerTexType; //假设顶点的数据类型为char型
typedef int ArcType; //假设边的权值类型为int型

//定义一个邻接矩阵图
typedef struct
{
	VerTexType vexs[MVNum]; //顶点数组用来存储每个顶点
	ArcType arcs[MVNum][MVNum]; //n*n阶矩阵（即二维数组）用来表示边
	int vexnum, arcnum; //顶点和边用来表示图的属性
}AMGraph;


//求顶点在顶点数组中的位置
int LocatVex(AMGraph&G,ArcType v)
{
	int i = 0;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.vexs[i] == v)
		{
			return i;
		}
	}
	return -1;
}


//创建无向网
//【算法思想】
//(1)先输入总的顶点数和边数
//(2)依次将顶点的信息存入顶点表中
//(3)初始化邻接矩阵，使每个权值初始化为极大值
//(4)构造邻接矩阵

void CreatUDN(AMGraph& G)
{
	//先输入顶点数和边数
	cin >> G.vexnum;
	cin >> G.arcnum;
	//将顶点存入到顶点数组中
	for (int i = 0; i < G.vexnum; i++)
	{
		cin >> G.vexs[i];
	}
	//建立邻接矩阵，即先初始化，后赋值
	//初始化
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = MAXINT;
		}
	}
	//构造邻接矩阵
	for (int k = 0; k < G.arcnum; k++)
	{
		//输入一条边依附的顶点极其权值
		VerTexType v1, v2;
		ArcType w;
		cin >> v1 >> v2>>w;
		//求顶点v1,v2在顶点数组中的位置
		int i = LocatVex(G, v1);
		int j = LocatVex(G, v2);
		//为关联v1,v2的边赋权值
		G.arcs[i][j] = w;
		G.arcs[j][i] = w;
	}
}