邻接表表示无向图

邻接表适合表示稀疏图

#define MVNum 100 //最大顶点数为100
typedef char VerTexType;  //图的顶点类型

//邻接表的边结点表示
typedef struct ArcNode
{
	int adjvex;  //表示边结点在顶点数组中的位置
	struct ArcNode* nextarc; //指向下一条边的指针
	//int weight;  //权重信息,视情况加或不加
}ArcNode;

//邻接表的顶点结点表示
typedef struct VNode
{
	VerTexType data;  //邻接表的顶点
	struct ArcNode* firstarc;  //顶点结点指向的第一条边
}VNode,Adjust[MVNum];

//邻接表的表示
typedef struct
{
	Adjust vertices; //顶点数组
	int vexnum, arcnum; //表的属性信息
}ALGraph;  //用邻接表来表示的图，adjust+list+graph


//求边结点在顶点数组中的位置
int LocateVex(ALGraph& G, VerTexType v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.vertices[i].data == v)
		{
			return i;
		}
	}
	return -1;
}



//采用邻接表表示法来创建无向图
void CreatUDG(ALGraph& G)
{
	//输入总的顶点数，边数
	cin >> G.vexnum >> G.arcnum;
	for (int i = 0; i < G.vexnum; i++)
	{
		//输入各顶点信息
		cin >> G.vertices[i].data;
		//顶点结点的指针域置0
		G.vertices[i].firstarc = NULL;
	}
	//以上邻接表的初始化完成
	//下面开始构造邻接表
	for (int k = 0; k < G.arcnum; k++)
	{
		//输入与边关联的两个顶点,并找到边结点所表示的顶点在顶点数组中的位置
		VerTexType v1, v2;
		cin >> v1, v2;
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);
		//生成新的结点p1,并与顶点v2相接
		ArcNode* p1 = new ArcNode;
		p1->adjvex = i; //p1在顶点数组中位置为i
		//头插法将新的边结点插入到表中
		p1->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p1;
		//由对称关系，生成新结点p2，并与顶点v1相接
		ArcNode* p2 = new ArcNode;
		p2->adjvex = j;
		p2->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p2;
	}
}