跳至主要内容

import Tabs from '@theme/Tabs'; import TabItem from '@theme/TabItem';

[DS] Graph

A graph is made up of vertices/nodes and edges/lines that connect those vertices.

A graph may be undirected (meaning that there is no distinction between the two vertices associated with each bidirectional edge) or directed (meaning that its edges are directed from one vertex to another but not necessarily in the other direction).

UNDIRECTED/UNWEIGHTED

DIRECTED/UNWEIGHTED

A graph may be weighted (by assigning a weight to each edge, which represent numerical values associated with that connection) or unweighted (either all edges have unit weight 1 or all edges have the same constant weight).

UNDIRECTED/WEIGHTED

DIRECTED/WEIGHTED

Definition​

Simple graphs​

In a simple graph, there is no (self-)loop edge (an edge that connects a vertex with itself) and no multiple/parallel edges (edges between the same pair of vertices). In another word: There can only be up to one edge between a pair of distinct vertices.

The number of edges E in a simple graph can only range from 0 to O(V2).

Graph algorithms on simple graphs are easier than on non-simple graphs.

connected graph​

An undirected graph G is called connected if there is a path between every pair of distinct vertices of G.

SCC

In a directed graph, we define the concept of Strongly Connected Component (SCC). In the currently displayed directed graph, we have {0}, {1, 2, 3}, and {4, 5, 6, 7} as its three SCCs.

acyclic graph​

A cycle is a path that starts and ends with the same vertex.

An acyclic graph is a graph that contains no cycle.

In an undirected graph, each of its undirected edge causes a trivial cycle although we usually will not classify it as a cycle.

DAG

A directed graph that is also acyclic has a special name: Directed Acyclic Graph (DAG), as shown above.

Special Graph​

Tree​

Complete Graph​

Bipartite Graph​

Directed Acyclic Graph (DAG)​

less frequently used​

  • Planar Graph
  • Line Graph
  • Star Graph
  • Wheel Graph

Data Structure​

Adjacency Matrix (AM)​

Adjacency Matrix (AM) is a square matrix where the entry AM[i][j] shows the edge's weight from vertex i to vertex j. For unweighted graphs, we can set a unit weight = 1 for all edge weights. An 'x' means that that vertex does not exist (deleted).

type AM struct {
  matrix   [][]int
  edgeList []Edge
}

Adjacency List (AL)​

Adjacency List (AL) is an array of V lists, one for each vertex (usually in increasing vertex number) where for each vertex i, AL[i] stores the list of i's neighbors. For weighted graphs, we can store pairs of (neighbor vertex number, weight of this edge) instead.

type AL struct {
  list  [][]int
  edges int
}

Edge List (EL)​

Edge List (EL) is a collection of edges with both connecting vertices and their weights. Usually, these edges are sorted by increasing weight, e.g., part of Kruskal's algorithm for Minimum Spanning Tree (MST) problem. However in this visualization, we sort the edges based on increasing first vertex number and if ties, by increasing second vertex number. Note that Bidirectional edges in undirected/directed graph are listed once/twice, respectively.

type EL struct {
  edgeList []Edge
  vertex   []int
}