ThinkerQAQ

NOTE

2.13 graph

Graph basics, representations, traversal, and implementations.

Data Structures & AlgorithmsCreated Updated 1 min readhistorical

This is a historical learning note and may contain outdated or incomplete understanding.

1. What Is a Graph

  • Consists of edges and vertices

2. Graph Categories

Directed Undirected
Weighted Directed weighted graph Undirected weighted graph
Unweighted Directed unweighted graph Undirected unweighted graph

3. Graph Representation

3.1. Adjacency Matrix

  • Use a two-dimensional array to store relationships between vertices: 1 if two vertices are adjacent, 0 if they are not

3.2. Adjacency List

  • Link edges starting from the same vertex in a singly linked list

4. Graph Traversal

4.1. Depth-First

  • Tree vs graph
    • The difference is that a graph needs to record whether each node has been visited

4.2. Breadth-First

  • Tree vs graph
    • The difference is that a graph needs to record whether each node has been visited

5. Implementation

5.1. API

type IGraph interface {
	// Print all elements
	String() string
	// Number of vertices
	V() int
	// Number of edges
	E() int
	// Whether there is an edge between x and y
	HasEdge(x int, y int) bool
	// Get all vertices adjacent to vertex v
	Adj(v int) []int
	// Get the degree of the specified vertex, i.e. the number of adjacent vertices
	Degree(v int) int
	// Depth-first traversal
	Dfs() []int
	// Breadth-first traversal
	Bfs() []int
}

5.2. Adjacency Matrix


// Adjacency-matrix representation
// Space complexity: O(V²)
type AdjMatrix struct {
	// Number of vertices
	v int
	// Number of edges
	e int
	// Store the graph in a two-dimensional array
	adj [][]int
}

// Time complexity: O(E)
func NewAdjMatrix(edges []int) *AdjMatrix {
	v := edges[0]
	e := edges[1]
	adjMatrix := &AdjMatrix{v: v, e: e}

	adj := make([][]int, v, v)
	for i := 0; i < len(adj); i++ {
		adj[i] = make([]int, v, v)
	}
	for i := 2; i < len(edges); i += 2 {
		a := edges[i]
		b := edges[i+1]
		adjMatrix.validateVertex(a)
		adjMatrix.validateVertex(b)

		adj[a][b] = 1
		adj[b][a] = 1
	}
	adjMatrix.adj = adj
	return adjMatrix
}

func (a *AdjMatrix) V() int {
	return a.v
}

func (a *AdjMatrix) E() int {
	return a.e

}

func (a *AdjMatrix) String() string {
	s := fmt.Sprintf("v=%v, e=%v, adj={\n", a.v, a.e)
	for i := 0; i < a.v; i++ {
		for j := 0; j < a.v; j++ {
			s += fmt.Sprintf("%d ", a.adj[i][j])
		}
		s += "\n"
	}
	s += "}"
	return s
}

// Get the vertices adjacent to the specified vertex
// Time complexity: O(V)
func (a *AdjMatrix) Adj(v int) []int {
	a.validateVertex(v)
	res := make([]int, 0)

	for i := 0; i < a.v; i++ {
		if a.adj[v][i] == 1 {
			res = append(res, i)
		}
	}

	return res
}

// Time complexity: O(1)
func (a *AdjMatrix) HasEdge(x int, y int) bool {
	a.validateVertex(x)
	a.validateVertex(y)

	return a.adj[x][y] == 1
}

func (a *AdjMatrix) Dfs() []int {
	res := make([]int, 0)
	visited := make([]bool, a.v, a.v)

	for i := 0; i < a.V(); i++ {
		if !visited[i] {
			a.dfs(i, &res, visited)
		}
	}

	//for i := a.V()-1; i >= 0; i-- {
	//	if !visited[i] {
	//		a.dfs(i, &res, visited)
	//	}
	//}

	return res
}

func (a *AdjMatrix) dfs(v int, res *[]int, visited []bool) {
	visited[v] = true
	*res = append(*res, v)

	for _, adj := range a.Adj(v) {
		if !visited[adj] {
			a.dfs(adj, res, visited)
		}
	}
}

func (a *AdjMatrix) Degree(v int) int {
	return len(a.Adj(v))
}

func (a *AdjMatrix) validateVertex(v int) {
	if v < 0 || v >= a.v {
		panic(fmt.Sprintf("V: %v invalid", v))
	}
}

func (a *AdjMatrix) Bfs() []int {
	res := make([]int, 0)
	visited := make([]bool, a.v, a.v)

	for i := 0; i < a.V(); i++ {
		if !visited[i] {
			a.bfs(i, &res, visited)
		}
	}

	return res
}

func (a *AdjMatrix) bfs(v int, res *[]int, visited []bool) {
	queue := make([]int, 0)
	queue = append(queue, v)
	visited[v] = true
	for len(queue) > 0 {
		removed := queue[0]
		queue = queue[1:]

		*res = append(*res, removed)

		for _, w := range a.Adj(removed) {
			if !visited[w] {
				queue = append(queue, w)
				visited[w] = true
			}
		}

	}
}

5.1.1. Test

func TestAdjMatrix(t *testing.T) {
	adjMatrix := NewAdjMatrix([]int{
		7, 9,
		0, 1,
		0, 3,
		1, 2,
		1, 6,
		2, 3,
		2, 5,
		3, 4,
		4, 5,
		5, 6})
	fmt.Println(adjMatrix)
	fmt.Println(adjMatrix.Dfs())
	fmt.Println(adjMatrix.Bfs())
}

5.2. Adjacency List


// Adjacency-list representation
// Space complexity: O(V+E)
type AdjList struct {
	// Number of vertices
	v int
	// Number of edges
	e int
	// Store the graph in an array of linked lists
	adj []*list.List
}

// Time complexity: O(V+E)
func NewAdjList(edges []int) *AdjList {
	v := edges[0]
	e := edges[1]

	adjList := &AdjList{v: v, e: e}
	adj := make([]*list.List, v, v)
	for i := 0; i < len(adj); i++ {
		adj[i] = list.New()
	}
	for i := 2; i < len(edges); i += 2 {
		a := edges[i]
		b := edges[i+1]
		adjList.validateVertex(a)
		adjList.validateVertex(b)

		adj[a].PushBack(b)
		adj[b].PushBack(a)
	}

	adjList.adj = adj
	return adjList
}

func (a *AdjList) V() int {
	return a.v
}

func (a *AdjList) E() int {
	return a.e
}

func (a *AdjList) String() string {
	s := fmt.Sprintf("v=%v, e=%v, adj={\n", a.v, a.e)
	for i := 0; i < a.v; i++ {
		lst := a.adj[i]
		for element := lst.Front(); element != nil; element = element.Next() {
			s += fmt.Sprintf("%d ", element.Value)
		}
		s += "\n"
	}
	s += "}"
	return s
}

// Get the vertices adjacent to the specified vertex
// Time complexity: O(degree(V))
func (a *AdjList) Adj(v int) []int {
	a.validateVertex(v)

	res := make([]int, 0)

	lst := a.adj[v]
	for element := lst.Front(); element != nil; element = element.Next() {
		res = append(res, element.Value.(int))
	}

	return res
}

// Time complexity: O(degree(V))
func (a *AdjList) HasEdge(x int, y int) bool {
	a.validateVertex(x)
	a.validateVertex(y)

	lst := a.adj[x]
	for element := lst.Front(); element != nil; element = element.Next() {
		if element.Value.(int) == y {
			return true
		}
	}

	return false
}

func (a *AdjList) Dfs() []int {
	res := make([]int, 0)
	visited := make([]bool, a.v, a.v)

	for i := 0; i < a.V(); i++ {
		if !visited[i] {
			a.dfs(i, &res, visited)
		}
	}

	return res
}

func (a *AdjList) dfs(v int, res *[]int, visited []bool) {
	visited[v] = true
	*res = append(*res, v)

	for _, adj := range a.Adj(v) {
		if !visited[adj] {
			a.dfs(adj, res, visited)
		}
	}
}

func (a *AdjList) Degree(v int) int {
	return a.adj[v].Len()
}

func (a *AdjList) validateVertex(v int) {
	if v < 0 || v >= a.v {
		panic(fmt.Sprintf("V: %v invalid", v))
	}
}

func (a *AdjList) Bfs() []int {
	res := make([]int, 0)
	visited := make([]bool, a.v, a.v)

	for i := 0; i < a.V(); i++ {
		if !visited[i] {
			a.bfs(i, &res, visited)
		}
	}

	return res
}

func (a *AdjList) bfs(v int, res *[]int, visited []bool) {
	queue := make([]int, 0)
	queue = append(queue, v)
	visited[v] = true
	for len(queue) > 0 {
		removed := queue[0]
		queue = queue[1:]

		*res = append(*res, removed)

		lst := a.adj[removed]
		for element := lst.Front(); element != nil; element = element.Next() {
			if !visited[element.Value.(int)] {
				queue = append(queue, element.Value.(int))
				visited[element.Value.(int)] = true
			}
		}
	}
}

5.2.1. Test

func TestAdjList(t *testing.T) {
	adjList := NewAdjList([]int{
		7, 9,
		0, 1,
		0, 3,
		1, 2,
		1, 6,
		2, 3,
		2, 5,
		3, 4,
		4, 5,
		5, 6})
	fmt.Println(adjList)
	fmt.Println(adjList.Dfs())
	fmt.Println(adjList.Bfs())


}

6. References

Discussion

Sign in with GitHub to comment. Discussions are stored as GitHub Issues.View on GitHub