更多优质内容
请关注公众号

算法小白的入门日记(十七)图的表示方法——邻接表和邻接矩阵-张柏沛IT博客

正文内容

算法小白的入门日记(十七)图的表示方法——邻接表和邻接矩阵

栏目:算法专题 系列:算法小白的入门日记 发布时间:2022-01-17 19:57 浏览量:2081
本系列文章目录
展开/收起

图的定义

图是多个顶点(为和树区分,这里不叫节点,而叫顶点)通过多条边连接而成的网状结构,顶点之间呈多对多的关系(树节点之间则是呈一对多关系)。

树和图相比,树的节点之间是一对多的关系,并且存在父与子的层级关系;图的顶点之间是多对多的关系,并且所有顶点都是平等的。

 

 

在图中,最基本的单元是顶点(vertex),相当于树中的节点。顶点之间的关联关系,被称为边(edge)。图的种类繁多,包括无向图、有向图、带权图等。

 

图的表示

图在内存中的存储方式多种多样,最主要包括:邻接矩阵、邻接表、逆邻接表和十字链表。

 

邻接矩阵是一个 n*n二维矩阵arr,对于拥有n个顶点的图,包含的连接数量(边的数量)最多为 n*(n-1)。

为什么连接数量为 n*(n-1)却需要n*n大小的矩阵呢?因为 n*(n-1)是每个顶点和其他顶点的关系,arr还描绘了每个顶点和自己的关系。

图中顶点0和顶点1之间有边关联,那么矩阵中的元素arr[0][1]与arr[1][0]的值就是1;顶点1和顶点2之间没有边关联,那么矩阵中的元素arr[1][2]与arr[2][1]的值就是0。

矩阵从左上到右下的一条对角线描述的就是顶点自己与自己的关联,其上的元素值必然是0,因为任何一个顶点与它自身是没有连接的。

 

对于一个无向图,如果 1 和 2有关联,则arr[1][2] 和 arr[2][1]都为1。对于一个有向图,如果 1 指向 2,但2不指向1,则arr[1][2]为1,arr[2][1]为0.

对于一个带权图,arr[i][j]的值就是权重,权重为0表示没有连接。

 

邻接矩阵的优点是快速查找两个节点的关系,时间复杂度O(1);但占用大量空间,空间复杂度是O(n^2)。

 

领接表是一个数组arr,在逻辑上arr的每个下标存储着每个顶点对应的相邻顶点(对于拥有n个顶点的图,arr的长度就为n,arr[i]存储着 i 这个节点的所有相邻节点)。在物理上,arr[i]可以用一个链表或数组存储 i 这个节点的相邻节点。

 

邻接表默认存储有向图,如果要存储一个无向图,则需要消耗多一倍的空间。例如 1 -> 2,对于有向图而言,arr[1]内需要包含2,但arr[2]不用包含1;但对于无向图而言,邻接表将其理解为双向,因此arr[1]内需要包含2,arr[2]内也需要包含1。

 

邻接表的优点是节省空间,空间复杂度O(n),缺点是查找两个顶点是否相连较慢,时间复杂度为O(n)。而且对于有向图而言,邻接表可以以O(n)复杂度找到某个顶点所指向的相邻顶点,但要找到所有指向本顶点的其他顶点则需要遍历整个邻接表,复杂度为O(n^2)。

 

为了满足“找到所有指向本顶点的其他顶点”这个需求,描述一个图不仅需要维护邻接表,还需要维护逆邻接表。

 

逆邻接表 rarr 的结构和邻接表一模一样,只是rarr[i]存储的是指向 i 自己这个顶点的所有顶点。

 

因此,一个图 = 邻接表 + 逆邻接表,如果没有“找到所有指向本顶点的其他顶点”这个需求,则只维护邻接表即可。

 

十字链表相当于邻接表和邻接链表的结合,其物理上也是使用一个数组arr表示,但 arr[i]应该保存一个对象,该对象保存两个数组(或者两个链表)分别用来表示 i 这个顶点指向的相邻顶点,和 i 被哪些顶点指向。

 

下面是以邻接表实现的图

// 有向图节点
type GNode struct{
	Val int
	Neibors []*GNode		// 某节点的相邻节点
}

func (gnode *GNode) init(val int) GNode{
	return GNode{Val: val, Neibors: make([]*GNode, 0)}
}

// 以邻接表方式表示的图
type Graph struct{
	Pos map[*GNode]struct{}	// 存储图的所有节点
}

// 将n1连向n2节点(有向)
func (graph *Graph) connect(n1, n2 *GNode) bool{
	if _, ok := graph.Pos[n1]; !ok{
		return false	// n1不在graph中则返回false
	}

	if _, ok := graph.Pos[n2]; !ok{
		graph.Pos[n2] = struct{}{}    // 将n2节点假如到 Graph 中
	}

	n1.Neibors = append(n1.Neibors, n2)
	return true
}

 

 

 

 

最小生成树算法

最小生成树算法的作用是将一个图的多余边去除,使得图中所有顶点满足连通性的同时,边的权重总和最小,此时这个取出多余边的图我们称为最小连通子图,最小连通子图没有回路,因此是一个树形结构,又称为最小生成树。

如果我们将每条边看成是一个顶点到达另一个顶点的成本,最小生成树算法的目的是将整个图所有节点连通的成本最小化。而最短路径算法则是算出任意两个节点连通的最小成本。

 

例如一个图原本的样子是这样

 

变成最小生成树后是这样

 

最小生成树算法采用贪心算法

1、创建一个“已连通集合(已触达顶点集合)”用于存放已经遍历过并且加入到生成树的顶点。创建一个一维数组arr表示最小生成树,顶点 i 的父节点为 arr[i]。生成树arr有一个虚拟根节点 -1。

2、从图中任意选择一个顶点A加入到“已连通集合”,节点A作为 arr 的下标0,arr[0] = -1,即顶点A的父节点是虚拟节点 -1。

3、从“已连通集合”中选择一个from节点,要求from节点和from的未访问过的相邻节点to节点的距离最小。将to顶点加入到“已连通集合”和最小生成树中。

4、重复上述过程,直到原图的所有顶点都加入到“已连通集合”和最小生成树中。

 

所生成的最小生成树的边的条数 = 总顶点数 - 1 = n - 1

 

代码实现如下:

// 最小生成树算法
func buildMinTree(g [][]int) []int{
	num := len(g)		// 顶点数
	minTree := make([]int, num)
	visited := make(map[int]struct{})	// 已连通集合

	curVext := 0	// 当前遍历到的,即将放入集合内的顶点
	minTree[curVext] = -1		// 将 0 号节点放入集合中
	visited[curVext] = struct{}{}

	for len(visited) < num{
		minWeight := math.MaxInt32		// 已连通集合的某节点 和 未连通的某节点 之间最小距离
		var from, to int
		for nextFromVext, _ := range(visited){	// 从已连通集合中选择一个from节点
			for nextToVext:=0; nextToVext<num; nextToVext++{	// 从所有from节点的相邻节点选择一个未访问的且距离最小的to节点作为下一个生成树节点
				if _, ok := visited[nextToVext]; !ok && g[nextFromVext][nextToVext] < minWeight{ // nextFromVext 到 nextToVext的距离小于 minWeight 既说明 这两个顶点是相邻的(因为他们的距离 比 MaxInt 小),又说明本nextToVext顶点比上一次的nextToVext顶点离 nextfromVext顶点近
					from = nextFromVext
					to = nextToVext
					minWeight = g[nextFromVext][nextToVext]
				}
			}
		}

		visited[to] = struct{}{}
		minTree[to] = from
	}
	return minTree
}


// 测试用例(用的是最短路径那个例子)
func TestBuildMinTree(t *testing.T) {
	m := math.MaxInt32
	matrix := [][]int{
		{0,5,2,m,m,m,m},
		{5,0,m,1,6,m,m},
		{2,m,0,6,m,8,m},
		{m,1,6,0,1,2,m},
		{m,6,m,1,0,m,7},
		{m,m,8,2,m,0,3},
		{m,m,m,m,7,3,0},
	}
	fmt.Println(buildMinTree(matrix))    // [-1 0 0 1 3 3 5]
}

 




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(十七)图的表示方法——邻接表和邻接矩阵

热门推荐
推荐新闻