c++数据结构：图（邻接矩阵）

设计图常用的数据模型：

• 邻接矩阵（数组）
• 邻接表 （链表）
• 邻接多重表（链表）
• 十字链表（链表）

图的邻接矩阵表示法：

1. 用以个一维数组来存放节点
2. 用一个二维数组（矩阵）来存放节点之间的关系

有n个顶点，创建一个n*n的矩阵，矩阵的每一行对应每个顶点的关系，当两点有弧时，对应的点为1，没有的话则为0。 

邻接矩阵的优缺点：

• 优点：结构简单，易理解，易找顶点的边，方便获取节点的度
• 缺点：所需内存大，且不易添加和删除顶点
• 时间复杂度：O(n^2+e*n)
• 空间复杂度：O(n^2)

 

有向图的度：改行和该列所含1的个数

1. 出度为改行的：1的个数
2. 入度为该列的：1的个数 

无向图的度：就是该行所在的 1的个数 

网的话是把 0变为∞，把1变为权值

邻接矩阵的核心结构为：

class Adj_matrix
{
	int vexs[Max_Vertex_Num];//顶点向量
	ArcCell arcs[Max_Vertex_Num][Max_Vertex_Num];//邻接矩阵
	int vexnum;//顶点数量
	int arcnum;//弧的数量	
};

邻接矩阵的实现：（只是简单实现）

#define INFINITY INT_MAX //最大值∞
#define Max_Num 50//最多50个顶点
class Adj_matrix
{
private:
	char vexs[Max_Num];//顶点向量
	int arcs[Max_Num][Max_Num];//邻接矩阵
	int vexnum;//顶点数量
	int arcnum;//弧的数量	
public:
	int find_num(char a);//寻找顶点位置
	void add_UDN();//生成无向网
};

1.无向网的实现： 

int Adj_matrix::find_num(char a)寻找顶点位置
{
	for (int i = 0; i < vexnum; i++)
	{
		if (vexs[i] == a)//如果数组中查找到下标
			return i;//返回下标
	}
	return	-1;//没有则返回-1
}
void Adj_matrix::add_UDN()//生成无向网
{
	cin >> vexnum >> arcnum;//输入顶点数和弧的数量，顶点数<=50,弧的数量<1/2*50*49
	for (int i = 0; i < vexnum; i++)
	{
		char p;
		cin >> p;//输入顶点
		vexs[i] = p;//存储顶点
	}
	for (int i = 0; i < vexnum; i++)//初始化矩阵
	{
		for (int j = 0; j < vexnum; j++)
		{
			arcs[i][j] = INFINITY;//全部置为 无穷大
		}
	}
	for (int i = 0; i < arcnum; i++)//处理边的关系，存放权值
	{
		char n;
		char m;//用来存储顶点信息
		int  x;//保存权值
		cin >> n >> m >> x;//键盘输入顶点信息
		//寻找顶点在数组的位置
		arcs[find_num(n)][find_num(m)] = x;//放入权值
		arcs[find_num(m)][find_num(n)] = x;//放入权值
	}
}

2.有向网与无向网类似就不列举了

把无向网代码最后一行删掉就行

3.无向图的实现 

void Adj_matrix::add_DU()//生成无向图
{
	cin >> vexnum >> arcnum;//键盘输入顶点和弧的数量
	for (int i = 0; i < vexnum; i++)
	{
		cin >> vexs[i];//输入顶点
	}
	for (int i = 0; i < vexnum; i++)//初始化矩阵
	{
		for (int j = 0; j < vexnum; j++)
		{
			arcs[i][j] = 0;//全部初始化为0；
		}
	}
	for (int i = 0; i < arcnum; i++)//
	{
		char n;
		char m;//用来存储顶点信息
		cin >> n >>m;
		//寻找顶点在数组的位置
		arcs[find_num(n)][find_num(m)] = 1;//放入1
		arcs[find_num(m)][find_num(n)] = 1;//放入1
	}
}

4.有向图与无向图类似就不列举了

把无向图代码最后一行删掉就行