Структуры данных Golang: графики

Go визуализация данных

В этой статье кратко представлены две реализации графов и их обходы BFS. Ссылаться на:golang-data-structure-graph

предисловие

Синькэн

В последнее время у меня было мало дел в школе, поэтому я открыл новую яму, пока помнил.algorithms, суммирует часто используемые структуры данных и алгоритмы. У каждого алгоритма есть файл README.md, который знакомит с процессом работы алгоритма, демонстрацией GIF, анализом сложности и применимыми сценариями; каждая структура данных знакомит с основными понятиями, операциями и сценариями применения.

Справочная литература

«Структура данных и анализ алгоритмов: описание языка C»

«Оптимальные решения для алгоритмов и структур данных»

картина

Структура данных графа является абстракцией структуры сетки, и в реальной жизни существует множество примеров, таких как сети маршрутов полетов, социальные сети и т. д. Основные понятия, такие как узлы, ребра, веса, направленность и ненаправленность, а также сильная и слабая связность графов, см. в главе 8 первой книги.

Для приведенного выше неориентированного графа есть два общих представления:

матрица смежности

Для ребра от узла u до узла v(u, v), можно выразить какA[u][v] = 1, 0, если не подключен напрямую. Матрица смежности, соответствующая рисунку выше, выглядит следующим образом:

Матрица на рисунке выше полностью описывает, как связан граф. Поскольку это неориентированный граф, матрица смежности относительно главной диагонали равнаСимметричный:A[u, v] = 1иметь в видуA[v, u] = 1, соответствующий реализации кода, представляет собой двумерный массив или структуру карты.

список смежности

Для каждого узла узлы, непосредственно связанные с ним, хранятся в структуре таблицы.Таблица смежности, соответствующая приведенному выше рисунку, выглядит следующим образом:

Стрелки на приведенном выше рисунке могут представлять ориентированный граф, который может быть реализован с использованием срезов или связанных списков для хранения связанных узлов.

Выберите структуру хранения

судя по рисункуплотностьВыберите структуру хранения, предполагая, что граф имеет N узлов и E ребер, если:

E << N^2представляет собой разреженный граф с несколькими кроссоверами

Использование списка смежности для хранения только подключенных узлов экономит место для хранения; использование матрицы смежности позволяет хранить большое количество узлов.0ценность, пустая трата места.

E ≈ N^2представляет собой плотный граф с множеством пересечений

Использование матрицы смежности будет очень удобно для запроса связности и меньшего расхода места для хранения. Список смежности найдет проблемы.

Реализация графика

Графики имеют 2 основные операции:AddNode()добавить узлы,AddEdge()Соедините узлы, чтобы сформировать ребра.

основное определение

type Node struct {
	value int
}

type Graph struct {
	nodes []*Node          // 节点集
	edges map[Node][]*Node // 邻接表表示的无向图
	lock  sync.RWMutex     // 保证线程安全
}

Реализация операции

// 增加节点
func (g *Graph) AddNode(n *Node) {
	g.lock.Lock()
	defer g.lock.Unlock()
	g.nodes = append(g.nodes, n)
}

// 增加边
func (g *Graph) AddEdge(u, v *Node) {
	g.lock.Lock()
	defer g.lock.Unlock()
	// 首次建立图
	if g.edges == nil {
		g.edges = make(map[Node][]*Node)
	}
	g.edges[*u] = append(g.edges[*u], v) // 建立 u->v 的边
	g.edges[*v] = append(g.edges[*v], u) // 由于是无向图，同时存在 v->u 的边
}

// 输出图
func (g *Graph) String() {
	g.lock.RLock()
	defer g.lock.RUnlock()
	str := ""
	for _, iNode := range g.nodes {
		str += iNode.String() + " -> "
		nexts := g.edges[*iNode]
		for _, next := range nexts {
			str += next.String() + " "
		}
		str += "\n"
	}
	fmt.Println(str)
}

// 输出节点
func (n *Node) String() string {
	return fmt.Sprintf("%v", n.value)
}

контрольная работа

package graph

import "testing"

func TestAdd(t *testing.T) {

	g := Graph{}
	n1, n2, n3, n4, n5 := Node{1}, Node{2}, Node{3}, Node{4}, Node{5}

	g.AddNode(&n1)
	g.AddNode(&n2)
	g.AddNode(&n3)
	g.AddNode(&n4)
	g.AddNode(&n5)

	g.AddEdge(&n1, &n2)
	g.AddEdge(&n1, &n5)
	g.AddEdge(&n2, &n3)
	g.AddEdge(&n2, &n4)
	g.AddEdge(&n2, &n5)
	g.AddEdge(&n3, &n4)
	g.AddEdge(&n4, &n5)

	g.String()
}

Тест прошел успешно: используйте список смежности для представления неориентированного графа выше

BFS: поиск в ширину

BFS (поиск в ширину): поиск в ширину, ширина относится к началу с узлапересекать в разных направленияхокружающие узлы. Начиная с узла, посещайте все его соседние узлы, а затем, начиная с этих узлов, посещайте их непосещенные соседние узлы... пока все узлы не будут посещены.

Немного похоже на обход древовидного порядка, но граф существуетпетляВ случае посещенные узлы могут быть посещены снова, поэтому необходима вспомогательная очередь для хранения соседних посещенных узлов.

процесс обхода

  1. выбрать узел в очередь
  2. Удаление узла из очереди
    1. Если очередь пуста, это означает, что обход завершен и возвращается напрямую
    2. узлаВсе непосещенные соседние узлыпоставить в очередь
  3. Выполнить обратный вызов (может быть сравнение эквивалентности для поиска)
  4. Повторите шаг 2

Код

package graph

import "sync"

type NodeQueue struct {
	nodes []Node
	lock  sync.RWMutex
}

// 实现 BFS 遍历
func (g *Graph) BFS(f func(node *Node)) {
	g.lock.RLock()
	defer g.lock.RUnlock()

	// 初始化队列
	q := NewNodeQueue()
	// 取图的第一个节点入队列
	head := g.nodes[0]
	q.Enqueue(*head)
	// 标识节点是否已经被访问过
	visited := make(map[*Node]bool)
	visited[head] = true
	// 遍历所有节点直到队列为空
	for {
		if q.IsEmpty() {
			break
		}
		node := q.Dequeue()
		visited[node] = true
		nexts := g.edges[*node]
		// 将所有未访问过的邻接节点入队列
		for _, next := range nexts {
			// 如果节点已被访问过
			if visited[next] {
				continue
			}
			q.Enqueue(*next)
			visited[next] = true
		}
		// 对每个正在遍历的节点执行回调
		if f != nil {
			f(node)
		}
	}
}

// 生成节点队列
func NewNodeQueue() *NodeQueue {
	q := NodeQueue{}
	q.lock.Lock()
	defer q.lock.Unlock()
	q.nodes = []Node{}
	return &q
}

// 入队列
func (q *NodeQueue) Enqueue(n Node) {
	q.lock.Lock()
	defer q.lock.Unlock()
	q.nodes = append(q.nodes, n)
}

// 出队列
func (q *NodeQueue) Dequeue() *Node {
	q.lock.Lock()
	defer q.lock.Unlock()
	node := q.nodes[0]
	q.nodes = q.nodes[1:]
	return &node
}

// 判空
func (q *NodeQueue) IsEmpty() bool {
	q.lock.RLock()
	defer q.lock.RUnlock()
	return len(q.nodes) == 0
}

контрольная работа

func TestBFS(t *testing.T)  {
	g.BFS(func(node *Node) {
		fmt.Printf("[Current Traverse Node]: %v\n", node)
	})
}

тест прошел успешно:

  • Сначала посетите узел 1, затем посетите 2 и 5 смежности 1, в это время 1, 2 и 5 помечаются как посещенные.
  • Затем пройдите непосещенные соседние узлы узла 2: 3, 4

  • На данный момент все узлы были посещены, и очередь пуста. конец обхода

Анализ сложности

временная сложность

Для графа из N узлов, E ребер узлы и каждое ребро проходятся один раз. Временная сложностьO(N + E)

космическая сложность

Для расходящихся графов вспомогательная очередь будет содержать не более N узлов. Сложность пространстваO(N)

Суммировать

На самом деле существует два типа обхода графа: BFS и DFS, первый использует вспомогательные очереди для временного хранения узлов, а второй использует рекурсивные вызовы стека. Оба имеют свои преимущества и недостатки.Например, BFS может контролировать длину очереди, в отличие от DFS, в которой нелегко контролировать размер стека.DFS подходит для предварительного обхода графов и деревьев, и будет изучаться в главе о деревьях.

Категории