图的定义：图是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为：G = (V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

无向边：若顶点V_i到V_j的边没有方向，则称这条边为无向边，用无序偶对 (V_i, V_j) 来表示。
有向边：若从顶点Vi 到V_j的边有方向，则称这条边为有向边，用有序偶对 <V_{i ，}V_j>来表示。

注意: < V_{i ，}V_j >和< V_j ，V_i >是两条不同的有向边。

无向图: 如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。
有向图: 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图.

回忆一下，隐马尔科夫模型的状态序列是带有依赖方向的，其构成的是概率有向图模型。而条件随机场的状态序列是没有依赖方向的，其构成的是概率无向图模型。

无向完全图：在无向图中，如果任意两个顶点之间存在无方向的边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。
有向完全图：在有向图中，如果任意两个顶点之间都存在有方向的边，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条边。注意：方向不同代表两个不同的边。

权: 图的边具有与它相关的数，这种与图的边的数叫做权。
网：带权的图通常称为网。

贝叶斯网络：有向图网络，马尔科夫网络：无向图网络。说明这些图的边都是带有权值的，这些权值代表结点相互的依赖程度。

1. 邻接矩阵

图的存储结构主要分为邻接矩阵、邻接表两种方式。其中邻接矩阵使用两个数组来分别存储图的顶点和边。

有了这个矩阵，我们就很容易获得图中的一些信息：

我们要判断任意两个顶点是否有边无边非常容易;
我们要知道某个顶点和有多少条边，只需要计算顶点 vi 在邻接矩阵中第i行的元素之和;
求顶点 vi 的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是临接点。

template<class VertexType>
class MyGraph {
public:
	template<class MatrixType>
	MyGraph(int numVex, int numEdges, VertexType* vexes, MatrixType edges);
public:
	VertexType* pVertexes; //顶点数组
	int** pEdges; //邻接矩阵，边集
	int mNumVertexes; //顶点数
	int mNumEdges; //边数
};

//初始化邻接矩阵
template<class VertexType> template<class MatrixType>
MyGraph<VertexType>::MyGraph(int numVex, int numEdges, VertexType* vexes, MatrixType edges)
{
	this->mNumEdges = numEdges;
	this->mNumVertexes = numVex;

	//创建并初始化顶点数组
	this->pVertexes = new VertexType[numVex];
	for (int i = 0; i < numVex; ++i) {
		this->pVertexes[i] = vexes[i];
	}
	//创建并初始化邻接矩阵
	this->pEdges = new int* [this->mNumVertexes];
	for (int i = 0; i < this->mNumVertexes; ++i) {
		this->pEdges[i] = new int[this->mNumVertexes];
	}
	for (int i = 0; i < this->mNumVertexes; ++i) {
		for (int j = 0; j < this->mNumVertexes; ++j) {
			this->pEdges[i][j] = edges[i][j];
		}
	}
}

2. 邻接表

我们使用数组来存储顶点，链表来存储边，我们把这种数组与链表相结合的存储方法称为邻接表(Adjacency List)。

邻接矩阵是不错的一种图存储结构，但是我们发现对边数相对顶点较少的图，这种结构对存储空间极大浪费。这是因为大部分结点之间没有边，我们仍然需要给其分配空间。

因此我们考虑另外一种存储结构方式。顺序存储结构就存在分配内存可能造成存储空间浪费的问题，于是引出了链式存储结构。同样的，我们可以考虑对边或者弧使用链式存储的方式来避免空间浪费问题。

图中顶点用一个一维数组存储，当然，顶点也可以使用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
图中每个顶点 vi 的所有邻接点构造一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点 vi 做为弧尾的出边表。

//边表节点
class EdgeNode {
public:
	int mAdjvex; //邻接点域，表示连接的是那个顶点
	int mWeight; //权值
	EdgeNode* pNext; //指向边表中下一个节点
};

//顶点节点
template<class VertexType>
class VertexNode {
public:
	EdgeNode* pFirstEdge; //指向边表的第一个节点
	VertexType mVertexData; //顶点数据
};

//邻接表
template<class VertexType>
class AdjacencyList {
public:
	template<class MatrixType>
	AdjacencyList(int numVex, int numEdges, VertexType* vexes, MatrixType edges);
public:
	VertexNode<VertexType>* pVertexes; //指向顶点数组
	int mNumVetexes; //顶点数
	int mNumEdges; //边数
};

template<class VertexType> template<class MatrixType>
AdjacencyList<VertexType>::AdjacencyList(int numVex, int numEdges, VertexType* vexes, MatrixType edges)
{
	this->mNumVetexes = numVex;
	this->mNumEdges = numEdges;

	//创建并初始化顶点数组
	this->pVertexes = new VertexNode<VertexType>[this->mNumVetexes];
	for (int i = 0; i < this->mNumVetexes; ++i) {
		this->pVertexes[i].mVertexData = vexes[i];
		this->pVertexes[i].pFirstEdge = NULL;
	}

	//初始化边集
	for (int i = 0; i < this->mNumVetexes; ++i) {
		for (int j = 0; j < this->mNumVetexes; ++j) {

			//说明顶点i 和顶点j之间有边
			if (edges[i][j] > 0 && edges[i][j] < INT_MAX) {

				//创建新边节点
				EdgeNode* pNode = new EdgeNode;
				pNode->mAdjvex = j; //邻接点
				pNode->mWeight = edges[i][j]; //权值
				pNode->pNext = this->pVertexes[i].pFirstEdge;
				this->pVertexes[i].pFirstEdge = pNode;

			}

		}
	}
}

图的存储（Graph）

1. 邻接矩阵

2. 邻接表

文章目录