邻接表创建

    邻接矩阵是个不错的图储存结构，但我们发现，对于边数相对顶点较少的图，这种结构是存在对储存空间的极大浪费的（关于邻接矩阵的相关知识在这里：邻接矩阵的创建），因此我们要考虑另外一种存储结构方式。

    我们在学习线性表时就注意到顺序存储结构预先分配空间会导致空间浪费的问题，于是我们引出了链式存储结构，所以我们也可以通过链式存储来储存图的边和弧解决空间浪费的问题。

    我们可以将顶点存入数组，再将顶点的邻接点进行链式存储，这种数组与链表相结合的储存方式称为邻接表。

    无向图邻接表的图示：

 有向图邻接表图示：

 ps：以上图均来自大话数据结构

知道了最后实现出来的图像我们便可以很轻松的编写程序了

    1.边表结点的结构

//边表结点
struct EdgeNode
{
	//邻结点域储存顶点的下标
	int adjvex;
	//权值
	InfoType m_info;
	//指向下一个边表结点的指针
	EdgeNode* next;
};

    2.顶点表结点结构

struct VertexNode
{
	//顶点
	VetexType vetex;
	//指向边表的头指针
	EdgeNode* FirstEdge;
};

    3.邻接表结构体

//邻接表
struct GraphAdiList
{
	//顶点数组
	VertexNode Adjext[MAXSIZE];
	//顶点个数，边条数
	int numVertex, numEdges;
};

    4.创建邻接表

//创建邻接表
void CreaterADGraph(GraphAdiList& G)
{
	int m, n,info;
	cout << "请输入顶点个数和边条数" << endl;
	cin >> G.numVertex >> G.numEdges;
	//初始化顶点表
	for (int i = 0; i < G.numVertex; i++)
	{
		cout << "请输入第" << i + 1 << "个顶点" << endl;
		//初始化顶点表中的两个属性
		cin >> G.Adjext[i].vetex;
		G.Adjext[i].FirstEdge = NULL;
	}
	//创建边表
	for (int k = 0; k < G.numEdges; k++)
	{
		EdgeNode* p;
		p = new EdgeNode;
		cout << "请输入边（vm,vn）上的顶点序号（m，n）和权值" << endl;
		cin >> m >> n>>info;
		//初始化创建的边表结点p
		p->adjvex = n-1;
		p->m_info = info;
		//将边表结点p按头插法插入邻接表
		p->next = G.Adjext[m - 1].FirstEdge;
		G.Adjext[m - 1].FirstEdge = p;
		//由于该图是无向图所以还要考虑（n，m）的情况
		p = new EdgeNode;
		p->adjvex = m - 1;
		p->m_info = info;
		p->next = G.Adjext[n - 1].FirstEdge;
		G.Adjext[n - 1].FirstEdge = p;
	}
	cout << "邻接表创建完成" << endl;
}

   我们创建邻接表默认创建的是无向图的邻接表，所以一条边要进行两次储存，创建两个边表的结点。

    5,输出检验邻接表是否创建成功

/查找边的权值（用来检验邻接表是否创建成功）
void Find_ADGraph(GraphAdiList& G)
{
	//用来遍历边表
	EdgeNode* p;
	int m, n;
	cout << "请输入边（vm,vn）上的顶点序号（m，n）" << endl;
	cin >> m >> n;
	p = G.Adjext[m - 1].FirstEdge;
	while (p)
	{
		if (p->adjvex == n - 1)
		{
			cout << "边" << G.Adjext[m - 1].vetex << "," << G.Adjext[p->adjvex].vetex << "的权值为：" << p->m_info << endl;
			return;
		}
		p = p->next;
	}
	cout << "没有这条边" << endl;

}

   调试的过程及其结果：