博客

邻接表

邻接矩阵的实现请看这里

是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为


邻接表


。

邻接表的处理方法是这样的：

• （1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。
• （2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。
  
  例如，下图就是一个无向图的邻接表的结构。

  

从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。

代码实现邻接表

（有向邻接表图）



基于C++

/**
 * C++: 邻接表图
 *
 * @author lph
 * 
 */

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

#define MAX 100
// 邻接表
class ListDG {
private: // 内部类
	// 邻接表中表对应的链表顶点
	class ENode {
	public:
		int ivex;			// 该边所指向的顶点的位置
		ENode* nextEdge;	// 指向下一条弧的指针
	};

	// 邻接表中表的顶点
	class VNode {
	public:
		char data;			//顶点信息
		ENode* firstEdge;	//指向第一条依赖该顶点的弧
	};

private: // 私有成员
	int mVexNum;			//图的顶点的数目
	int mEdgNum;			//图的边的数目
	VNode mVexs[MAX];		//用一维数组来存储邻接表的顶点

public:
	// 创建邻接表对应的图（自己输入）
	ListDG();
	// 创建邻接表对应的图（用已经提供的数据）
	ListDG(char vexs[], int vlen, char edges[][2], int elen);
	~ListDG();

	// 打印邻接表图
	void print();

private:
	// 读取一个输入字符
	char readChar();
	// 返回ch的位置
	int getPosition(char ch);
	// 将node节点链接到List的最后
	void linkLast(ENode* list, ENode* node);
};

/*
* 创建邻接表对应的图（自己输入）
*/
ListDG::ListDG() {
	char c1, c2;
	int v, e;
	int i, p1, p2;
	ENode* node1, * node2;

	// 输入顶点数和边数
	cout << "input vertex number: ";
	cin >> mVexNum;
	cout << "input edge number: ";
	cin >> mEdgNum;
	if (mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum - 1)))) {
		cout << "input error: invalid parameters! " << endl;
		return;
	}

	// 初始化邻接表的顶点
	for (i = 0; i < mVexNum; ++i) {
		cout << "vertex(" << i << "):";
		mVexs[i].data = readChar();
		mVexs[i].firstEdge = nullptr;
	}

	// 初始化邻接表的边
	for (i = 0; i < mEdgNum; ++i) {
		// 读取边的起始点和结束顶点
		cout << "edge(" << i << "):";
		c1 = readChar();
		c2 = readChar();

		p1 = getPosition(c1);
		p2 = getPosition(c2);
		// 初始化node1
		node1 = new ENode();
		node1->ivex = p2;
		// 将node1链接到p1所在链表的末尾
		if (mVexs[p1].firstEdge == nullptr)
			mVexs[p1].firstEdge = node1;
		else
			linkLast(mVexs[p1].firstEdge, node1);
	}
}

/*
	创建邻接表对应的图（用已经提供的数据）
*/
ListDG::ListDG(char vexs[], int vlen, char edges[][2], int elen) {
	char c1, c2;
	int i, p1, p2;
	ENode* node1, * node2;

	// 初始化顶点数和边数
	mVexNum = vlen;
	mEdgNum = elen;
	// 初始化"邻接表"的顶点
	for (i = 0; i < mVexNum; i++)
	{
		mVexs[i].data = vexs[i];
		mVexs[i].firstEdge = NULL;
	}
	// 初始化邻接表的边
	for (i = 0; i < mEdgNum; ++i) {
		// 读取边的起始顶点和结束顶点
		c1 = edges[i][0];
		c2 = edges[i][1];

		p1 = getPosition(c1);
		p2 = getPosition(c2);
		// 初始化node1
		node1 = new ENode();
		node1->ivex = p2;
		// 将node1链接到p1所在链表的末尾
		if (mVexs[p1].firstEdge == nullptr)
			mVexs[p1].firstEdge = node1;
		else
			linkLast(mVexs[p1].firstEdge, node1);
	}
}

/*
	析构函数
*/
ListDG::~ListDG() {
	
}
/*
	将node节点连接到List最后
*/ 
void ListDG::linkLast(ENode* list, ENode* node) {
	ENode* p = list;

	while (p->nextEdge)
		p = p->nextEdge;
	p->nextEdge = node;
}

/*
	返回ch的位置
*/
int ListDG::getPosition(char ch) {
	int i;
	for (i = 0; i < mVexNum; ++i) 
		if (mVexs[i].data == ch)
			return i;
		return -1; // 失败返回-1
	
}

/*
	读取一个输入字符
*/
char ListDG::readChar() {
	char ch;
	do {
		cin >> ch;
	} while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));
	return ch;
}

/*
	打印邻接表图
*/
void ListDG::print() {
	int i, j;
	ENode* node;
	cout << "List Graph: " << endl;
	for (i = 0; i < mVexNum; ++i) {
		cout << i << "(" << mVexs[i].data << "):";
		node = mVexs[i].firstEdge;
		while (node != nullptr) {
			cout << node->ivex << "(" << mVexs[node->ivex].data << ") ";
			node = node->nextEdge;
		}
		cout << endl;
	}
}
int main() {
	char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
	char edges[][2] = {
		{'A', 'B'},
		{'B', 'C'},
		{'B', 'E'},
		{'B', 'F'},
		{'C', 'E'},
		{'D', 'C'},
		{'E', 'B'},
		{'E', 'D'},
		{'F', 'G'} 
	};
	int vlen = sizeof(vexs) / sizeof(vexs[0]);
	int elen = sizeof(edges) / sizeof(edges[0]);
	ListDG* pG;

	// 自定义图（输入矩阵队列）
	// pG = new ListDG();
	// 采用已经有的图
	pG = new ListDG(vexs, vlen, edges, elen);

	pG->print();
	return 0;
	
}

用已经有的数据运行代码后的结果


（有向邻接表图）


为：

用自己手动输入数据的结果


（有向邻接表图）


：

邻接表的实现（

无向邻接表图

）

：

/*
	C++: 邻接表表示的"无向图(List Undirected Graph)"
	@author lph
	
*/
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

constexpr auto MAX = 100;
// 邻接表;
class ListUDG {
private:
	// 内部类
	// 邻接表中表对应的链表的顶点
	class ENode {
	public:
		int ivex;		// 该边所指向的顶点的位置
		ENode* nextEdge;// 指向下一条弧的指针
	};
	// 邻接表中表对应的顶点
	class VNode {
	public:
		char data;		// 顶点信息
		ENode* firstEdge;// 指向第一条依赖该顶点的弧
	};
private:
	int mVexNum;		// 图的顶点个数
	int mEdgNum;		// 图的边的数目
	VNode mVexs[MAX];  // 一维数组存储图的顶点，也就是邻接表第一列的顶点
public:
	// 创建邻接表对应的图（自己输入）
	ListUDG();
	// 创建邻接表对应的图（用已经提供的数据）
	ListUDG(char vexs[], int vlen, char edges[][2], int elen);
	// 析构函数
	~ListUDG();
	// 打印邻接表图
	void print();
private:
	// 读取一个输入字符
	char readChar();
	// 返回ch的位置
	int getPosition(char ch);
	// 将node节点链接到list的最后
	void linkLast(ENode* list, ENode* node);
};
/*
	创建邻接表对应的图（自己输入）
*/
ListUDG::ListUDG() {
	char c1, c2;
	// int v, e;
	int i, p1, p2;
	ENode* node1, * node2;
	// 输入顶点数和边数
	cout << "input vertex number: ";
	cin >> mVexNum;
	cout << "input edge number: ";
	cin >> mEdgNum;
	if (mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum - 1)))) {
	cout << "input error: invalid parameters!" << endl;
	return;
}
	// 初始化邻接表的顶点
	for (i = 0; i < mVexNum; ++i) {
		cout << "vertex(" << i << "):";
		mVexs[i].data = readChar(); // 如果mVexs在之前用的是VNode* mVexs[MAX],那么这里需要用指针mVexs[i]->data
		mVexs[i].firstEdge = nullptr;
	}
	// 初始化邻接表的边
	for (i = 0; i < mEdgNum; ++i) {
		// 读取边的起点和结束顶点
		cout << "edge(" << i << "):";
		c1 = readChar();
		c2 = readChar();

		p1 = getPosition(c1);
		p2 = getPosition(c2);
		// 初始化node1
		node1 = new ENode();
		node1->ivex = p2;
		// 将node1链接到p1所在链表的末尾
		if (mVexs[p1].firstEdge == nullptr)
			mVexs[p1].firstEdge = node1;
		else
			linkLast(mVexs[p1].firstEdge, node1);
		// 初始化node2
		node2 = new ENode();
		node2->ivex = p1;
		// 将node2链接到p2所在链表的末尾
		if (mVexs[p2].firstEdge == nullptr)
			mVexs[p2].firstEdge = node2;
		else
			linkLast(mVexs[p2].firstEdge, node2);
	}
}
/*
	创建邻接表对应的图(用已提供的数据)
*/
ListUDG::ListUDG(char vexs[], int vlen, char edges[][2], int elen) {
	char c1, c2;
	int i, p1, p2;
	ENode* node1, * node2;
	// 初始化顶点数和边数
	mVexNum = vlen;
	mEdgNum = elen;
	// 初始化邻接表的顶点
	for (i = 0; i < mVexNum; ++i) {
		mVexs[i].data = vexs[i];
		mVexs[i].firstEdge = nullptr;
	}
	// 初始化邻接表的边
	for (i = 0; i < mEdgNum; ++i) {
		// 读取边的起始顶点和结束顶点
		c1 = edges[i][0];
		c2 = edges[i][1];

		p1 = getPosition(c1);
		p2 = getPosition(c2);
		// 初始化node1
		node1 = new ENode();
		node1->ivex = p2;
		// 将node1链接到p1所在的末尾
		if (mVexs[p1].firstEdge == nullptr)
			mVexs[p1].firstEdge = node1;
		else
			linkLast(mVexs[p1].firstEdge, node1);
		// 初始化node2
		node2 = new ENode();
		node2->ivex = p1;
		// 将node2链接到p2所在链表的末尾
		if (mVexs[p2].firstEdge == nullptr)
			mVexs[p2].firstEdge = node2;
		else
			linkLast(mVexs[p2].firstEdge, node2);
	}
}
/*
	析构函数
*/
ListUDG::~ListUDG() {

}
/*
	将node节点连接到list最后
*/
void ListUDG::linkLast(ENode* list, ENode* node) {
	ENode* p = list;
	while (p->nextEdge)
		p = p->nextEdge;
	p->nextEdge = node;
}
/*
	返回ch的位置
*/
int ListUDG::getPosition(char ch) {
	int i;
	for (i = 0; i < mVexNum; ++i) 
		if (mVexs[i].data == ch)
			return i;
	return -1;
}
/*
	读取一个输入字符
*/
char ListUDG::readChar() {
	char ch;
	do {
		cin >> ch;
	} while  (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));
	return ch;
}

/*
	打印邻接表图
*/
void ListUDG::print() {
	int i, j;
	ENode* node;
	cout << "List Graph:" << endl;
	for (i = 0; i < mVexNum; ++i) {
		cout << i << "(" << mVexs[i].data << ")";
		node = mVexs[i].firstEdge;
		while (node != nullptr) {
			cout << node->ivex << "(" << mVexs[node->ivex].data << ")";
			node = node->nextEdge;
		}
		cout << endl;
	}
}
int main(){
	char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
	char edges[][2] = {
		{'A', 'C'},
		{'A', 'D'},
		{'A', 'F'},
		{'B', 'C'},
		{'C', 'D'},
		{'E', 'G'},
		{'F', 'G'} };
	int vlen = sizeof(vexs) / sizeof(vexs[0]);
	int elen = sizeof(edges) / sizeof(edges[0]);
	ListUDG* pG;

	// 自定义"图"(输入矩阵队列)
	//pG = new ListUDG();
	// 采用已有的"图"
	pG = new ListUDG(vexs, vlen, edges, elen);

	pG->print();   // 打印图
	
	return 0;
}

打印已提供邻接表

（无向邻接表图）

数据的结果：

打印自己输入的邻接表

（无向邻接表图）

的数据：

邻接矩阵的实现请看这里