In linear tables, there is only a simple context between elements, with an element having one and only one immediate precursor and one immediate successor. In a tree structure, there is a one-to-many hierarchy between elements. An element has at most one parent, but can have multiple children.
Compared to linear tables and trees, graph structures are more complex and are used to represent many-to-many relationships between elements. Just like relationships, Tom can have many friends, And Tom’s friends are likely to be Tom’s friends.
The following is a typical diagram structure.
1. Review of mathematical knowledge
Before we get to the structure of the graph, it’s worth reviewing high school math.
1. ∈ refers to “belong to”, indicating the relationship between elements and sets. If set A={A,b,c}, then element A ∈A is read as “A belongs to A”. Conversely, element D ∉A, read “D does not belong to A”.
2. Relationships between sets. For two sets A and B, if any element of set A belongs to B, then set A is A subset of set B, called A⊆B (or B⊇A) and pronounced “A in B” (or “B in A”). When A is not A subset of B, it is called A⊈B (or B⊉A).
For example, A={1,2}, B={1,2,3}, then A⊆B.
A true subset: if A⊆B and A≠B, A is A true subset of B and is termed A_⫋_B.
Empty set: A set that does not contain any elements, called ø.
3. Summation symbol ∑.The sigma notation stands for sum, pronounced sigma.
2. Definition of graph
A Graph is composed of the finite non-empty set of vertices and the set of edges between vertices, which is usually expressed as G(V,E). G represents a Graph, where V is the set of vertices in Graph G and E is the set of edges in Graph G.
A graph consists of vertices and edges. A linear table with no elements is called an “empty table”, and a tree with no nodes is called an “empty tree”. A graph does not have an “empty graph”.
In a graph, any two vertices can have a relationship. The logical relationship between vertices is called Edge, and the Edge set can be empty.
1. Undirected graphs and directed graphs
If an edge between vertices A and B has no direction, the edge is called an “undirected edge”, denoted by an unordered pair (A,B). If all edges in A graph are undirected, the graph is called an “undirected graph”.
If the edge between vertices A and B has A direction, it is called A “directed edge”, also called an “arc”, represented by an ordered pair
, with A called “arc tail” and B called “arc head”. A graph is called a “directed graph” if all its edges are directed.
,b>
Undirected edges are represented by “()” and directed edges by “<>”.
2. Simple figure
A graph is called a “simple graph” if there are no edges from vertices to themselves and the same edges do not occur repeatedly.
Obviously, neither of the following is a simple graph.
3. Complete graph
A graph is called a “complete graph” if there are edges between any two vertices. In addition, according to the division of directed graph and undirected graph, the complete graph is subdivided into directed complete graph and undirected complete graph.
Characteristic: An undirected complete graph with n vertices, with n(n-1)/2 edges. A directed complete graph with n vertices and n(n-1) edges.
4. Sparse and dense graphs
A graph with very few edges or arcs is called”Thin figure“, conversely, a graph with many edges or arcs is called”Dense figure“. Whether a graph is sparse or dense is relative, and there is no clear rule.
5. Weight and Network
If an edge or arc in a graph has a number associated with it, this number is called weight. Weight can indicate the distance or cost between vertices. This weighted graph is also called a net.
The following network represents the distance between the four first-tier cities in China. The weights in the figure represent the distance between cities.
6. Subgraph
Suppose I have two graphs, G=(V,E), G=(V,E) if V⊆ V and E"⊆E" is called graph GIs the “of graph G.subgraph“.
7. Adjacent points and degrees
Assuming an undirected graph G=(V,E), if edges (A,B)∈E, vertices A and B are called “Adjacent points” to each other.
The number of edges associated with vertex A is called the Degree of the vertex and is denoted as TD(A).
For A directed graph G=(V,E), if arc <A,B>∈E, then vertex A is adjacent to vertex B, and vertex B is adjacent to vertex A. The number of arcs starting with vertex A is called the”The degree of“, remember toID(A). The number of arcs terminating vertex A is called the”The degree of“, remember toOD(A). The degree of vertex A is equal to the degree in plus the degree out.
8. Paths and loops
Assuming that the undirected graph G=(V,E), from vertex A to vertex B,The pathIs a sequence of vertices. There are multiple paths between two vertices. Four paths from vertex B to vertex D are listed below.
The length of a path is the number of edges or arcs along the path.
The path from the first vertex to the last vertex is called a loop, also known as a loop. A path in a sequence where vertices do not repeat is called a “simple path”, and a path where vertices do not repeat except the first and last vertex is called a “simple loop” or a “simple loop”.
The paths marked red in the following two diagrams form loops. Except for vertex B, A, C and D do not occur repeatedly in the left diagram, so it is A simple loop. In the diagram on the right, vertex C is repeated except for vertex B, so it is not a simple loop.
9. Connected graphs and connected components
In undirected graph G, A and B are called if there is A path from vertex A to vertex Bconnected. If any two vertices in a graph are connected, the graph is called”Connected graph“.
- Let’s start with a subgraph.
- If the subgraph is connected.
- The connected subgraph contains a maximum number of vertices.
- A connected subgraph with a maximum number of vertices contains all edges attached to those vertices.
>, from V to VAnd there are paths from V ‘to V, then the graph is called”Strongly connected graph“. The extremely strongly connected subgraph of a directed graph is called the”Strongly connected component“.
The graph on the left below has A path from A to D, but not from D to A, so it is not strongly connected. Although there is no arc <A,C> in the figure on the right, there is also A path from A to C through A>B>C, which is A strongly connected graph. In addition, the right graph is the extremely strongly connected subgraph of the left graph, that is, the right graph is the strongly connected component of the left graph.
10. Spanning trees and forests
A “spanning tree” of a connected graph is an extremely small connected subgraph that contains all n vertices of the graph but only enough n-1 edges to form the tree.
If you iterate over a connected graph, the combination of edges and vertices that you pass through can be thought of as a spanning tree.
A spanning tree in a connected graph must meet the following two conditions:
- Contains all vertices in a connected graph.
- There is only one path between any two vertices.
Thus, a connected graph has the property that the number of vertices = the number of edges +1.
A directed graph is a tree if just one vertex has an input of 0 and all the other vertices have an input of 1. The vertices with an entry degree of 0 are actually directed root nodes, while the other vertices with an entry degree of 1 mean that the non-root nodes of the tree have only one parent.
Spanning trees correspond to connected graphs and spanning forests correspond to disconnected graphs.
For an unconnected graph, it can be decomposed into multiple connected components, and each connected component corresponds to N (n>0) spanning trees. Therefore, the set composed of multiple spanning trees corresponding to an unconnected graph is called”Generate the forest“.
3. Realization of graph
The concept of graph is introduced, more. Let’s look at how to implement diagrams in the Java language.
The structure of graph is complicated and cannot be represented simply by array. For multiple linked lists, if the degree of the vertices is very different, it is bound to lead to a large number of pointer field space waste problem, here we introduce five ways of graph representation.
3.1 Adjacency matrix
First of all, vertices and edges are two different things and should be stored separately. Vertices are of no size or order, so arrays are appropriate for storage. Edges or arcs represent relationships between vertices, which you can’t do with a one-dimensional array, so you can use a two-dimensional array.
Adjacency matrix: A graph is represented by two arrays, one for vertices and two for edges or arcs. For an undirected graph, a two-dimensional array stores 0 for infinity and 1 for edge. For a directed graph, a two-dimensional array needs to distinguish the direction of rows and columns, again storing 0 for infinity and 1 for edge. For the net, since edges or arcs have weights, it is absolutely impossible to store a value ∞ on behalf of infinity, and the specific weight is stored as value.
As shown below, one-dimensional and two-dimensional arrays are used to represent the left figure on the right. How do I determine if there are edges between vertices? You just have to judge a two-dimensional arrayarr[i][j]The value is 1. How do I count the degree of vertices? Just take the sum of the ith row or column in a two-dimensional array.
// Adjacency matrix
public class MatrixGraph<E> {
private E[] vertex;
private int[][] edges;
public MatrixGraph(E[] vertex, int[][] edges) {
this.vertex = vertex;
this.edges = edges;
}
public void show(a) {
System.out.println("Set of vertices :");
StringJoiner joiner = new StringJoiner(","."["."]");
for (E e : vertex) {
joiner.add(e.toString());
}
System.out.println(joiner.toString());
System.out.println("Degree of fixed point :");
for (int i = 0; i < vertex.length; i++) {
int degree = 0;
for (int j = 0; j < edges[i].length; j++) {
degree += edges[i][j];
}
System.out.println(vertex[i] + ":" + degree);
}
System.out.println("Set of edges :");
for (int i = 0; i < edges.length; i++) {
for (int j = 0; j < edges[i].length; j++) {
if (edges[i][j] == 1) {
System.out.println("(" + vertex[i] + "," + vertex[j] + ")"); }}}}public static void main(String[] args) {
new MatrixGraph<Character>(new Character[]{'A'.'B'.'C'.'D'},
new int[] [] {{0.1.1.1},
{1.0.1.0},
{1.1.0.1},
{1.0.1.0} }).show(); }}Copy the codeConsole output:
Set of vertices: [A,B,C,D] degree of fixed point: A:3
B:2
C:3
D:2A collection of: (A, B) (A, C) (A, D) (B, A) (B, C) (C, A) (C, B) (C, D) (D (A) (D, C)Copy the code[Advantages] Simple code implementation, high efficiency.
[Disadvantages] For the graph with N vertices, the representation of adjacency matrix requires a one-dimensional array with length N and a two-dimensional array with length N*N. For sparse graph, it will waste a lot of memory space.
3.2 adjacency table
In order to solve the problem of adjacency matrix wasting space, hence the “adjacency list” notation.
Adjacency list: Still use arrays to store vertices, use linked lists to store edge information, and use a one-way linked list to connect multiple edges of the same vertex.
To determine if there are edges between vertices, just walk through the linked list. Count the degree of vertices by traversing the linked list.
For an undirected graph, the structure is as follows: to represent a net, add Weight to the edge.
As follows, adjacency list method is used to represent the left figure.
For digraph is more tricky, generally use vertices as arc tail to store linked list, so it is very convenient to count the vertices out, if you want to count the vertices in, you must traverse the whole graph. Another solution is to create an inverse adjacency list with the vertex as the arc head at the same time, which is easy to count the degree of entry, but maintain two linked lists.
【 implementation 】(undirected graph)
/ / adjacency list
public class AdjacencyListGraph<E> {
private int size;
private Vertex<E>[] table;
public AdjacencyListGraph(a) {
this.table = new Vertex[16];
}
// Add vertices
public Vertex<E> add(E e) {
Vertex<E> vertex = new Vertex<>(e, null);
table[size++] = vertex;
return vertex;
}
public void show(a) {
System.out.println("Set of vertices :");
StringJoiner joiner = new StringJoiner(","."["."]");
for (int i = 0; i < size; i++) {
joiner.add(table[i].data.toString());
}
System.out.println(joiner.toString());
System.out.println("Degree of fixed point :");
for (int i = 0; i < size; i++) {
int degree = 0;
Edge edge = table[i].firstEdge;
while(edge ! =null) {
degree++;
edge = edge.next;
}
System.out.println(table[i].data + ":" + degree);
}
System.out.println("Set of edges :");
for (int i = 0; i < size; i++) {
Vertex<E> vertex = table[i];
Edge edge = vertex.firstEdge;
while(edge ! =null) {
System.out.println("(" + vertex.data + "," + table[edge.index].data + ")"); edge = edge.next; }}}/ / add edge
public void addEdge(Vertex<E> vertex, int index) {
Edge newEdge = new Edge(index, null);
Edge edge = vertex.firstEdge;
if (edge == null) {
vertex.firstEdge = newEdge;
} else {
/ / end plug
while(edge.next ! =null) { edge = edge.next; } edge.next = newEdge; }}public static class Vertex<E> {
private E data;
private Edge firstEdge;
public Vertex(E data, Edge firstEdge) {
this.data = data;
this.firstEdge = firstEdge; }}private static class Edge {
private int index;
private Edge next;
public Edge(int index, Edge next) {
this.index = index;
this.next = next; }}public static void main(String[] args) {
AdjacencyListGraph<String> graph = new AdjacencyListGraph<>();
// Set the vertex
Vertex<String> A = graph.add("A");
Vertex<String> B = graph.add("B");
Vertex<String> C = graph.add("C");
Vertex<String> D = graph.add("D");
/ / set the edge
graph.addEdge(A, 1);
graph.addEdge(A, 2);
graph.addEdge(A, 3);
graph.addEdge(B, 0);
graph.addEdge(B, 2);
graph.addEdge(C, 0);
graph.addEdge(C, 1);
graph.addEdge(C, 3);
graph.addEdge(D, 0);
graph.addEdge(D, 2); graph.show(); }}Copy the code[Advantage] It solves the problem of wasting space on sparse graph.
[Disadvantages] Not very friendly to digraphs.
3.3 Cross linked list
Adjacency lists are defective for directed graphs. The adjacency list is concerned with the out degree, and to know the in degree we must traverse the whole graph. The inverse adjacency list is concerned with the in degree, and to know the out degree we must traverse the whole graph. Is it possible to combine an adjacency list with an inverse adjacency list? Yes, this is a “cross linked list”.
Cross lists: Use arrays to store vertices and double lists to store directed edges, structured as follows:DataStoring data,firstInPointer to the edge header,firstOutOut-edge header pointer.tailVexArc tail subscript,headVexArc head subscript,headLinkThe next incoming edge table pointer,tailLinkNext outbound table pointer.
As follows, use a cross linked list to represent the graph on the left:
// cross linked list method
public class OrthogonalListGraph<E> {
private int size;
private Vertex<E>[] table;
public OrthogonalListGraph(a) {
this.table = new Vertex[16];
}
// Add vertices
public Vertex<E> addVertex(E e) {
return table[size++] = new Vertex<>(e, null.null);
}
// Add the join edge
public void addInEdge(Vertex<E> vertex, int tailIndex, int headIndex) {
Edge inEdge = vertex.firstIn;
if (inEdge == null) {
vertex.firstIn = new Edge(tailIndex, headIndex, null.null);
} else {
while(inEdge.headLink ! =null) {
inEdge = inEdge.headLink;
}
inEdge.headLink = new Edge(tailIndex, headIndex, null.null); }}// Add an outgoing edge
public void addOutEdge(Vertex<E> vertex, int tailIndex, int headIndex) {
Edge outEdge = vertex.firstOut;
if (outEdge == null) {
vertex.firstOut = new Edge(tailIndex, headIndex, null.null);
} else {
while(outEdge.tailLink ! =null) {
outEdge = outEdge.tailLink;
}
outEdge.tailLink = new Edge(tailIndex, headIndex, null.null); }}public void show(a) {
System.out.println("Set of vertices :");
StringJoiner joiner = new StringJoiner(","."["."]");
for (int i = 0; i < size; i++) {
joiner.add(table[i].data.toString());
}
System.out.println(joiner.toString());
System.out.println("Vertex output :");
for (int i = 0; i < size; i++) {
int degree = 0;
Edge edge = table[i].firstOut;
while(edge ! =null) {
degree++;
edge = edge.tailLink;
}
System.out.println(table[i].data + ":" + degree);
}
System.out.println("Vertex entry :");
for (int i = 0; i < size; i++) {
int degree = 0;
Edge edge = table[i].firstIn;
while(edge ! =null) {
degree++;
edge = edge.headLink;
}
System.out.println(table[i].data + ":" + degree);
}
System.out.println("Set of edges :");
Set<String> set = new HashSet<>();
for (int i = 0; i < size; i++) {
Vertex<E> vertex = table[i];
Edge edge = vertex.firstIn;
while(edge ! =null) {
set.add(String.format("<%s,%s>", table[edge.tailIndex].data, table[edge.headIndex].data));
edge = edge.headLink;
}
edge = vertex.firstOut;
while(edge ! =null) {
set.add(String.format("<%s,%s>", table[edge.tailIndex].data, table[edge.headIndex].data));
edge = edge.tailLink;
}
}
set.stream().forEach(System.out::println);
}
private static class Vertex<E> {
private E data;
private Edge firstIn;// Add a pointer to the edge header
private Edge firstOut;// Outhead pointer
public Vertex(E data, Edge firstIn, Edge firstOut) {
this.data = data;
this.firstIn = firstIn;
this.firstOut = firstOut; }}private static class Edge {
private int tailIndex;// arc tail vertex subscript
private int headIndex;// subscript the vertex of the arc
private Edge headLink;// Add a pointer to the edge table
private Edge tailLink;// Out of the table pointer
public Edge(int tailIndex, int headIndex, Edge headLink, Edge tailLink) {
this.tailIndex = tailIndex;
this.headIndex = headIndex;
this.headLink = headLink;
this.tailLink = tailLink; }}public static void main(String[] args) {
OrthogonalListGraph<String> graph = new OrthogonalListGraph<>();
Vertex<String> A = graph.addVertex("A");
Vertex<String> B = graph.addVertex("B");
Vertex<String> C = graph.addVertex("C");
graph.addOutEdge(A, 0.1);
graph.addOutEdge(A, 0.2);
graph.addInEdge(B, 0.1);
graph.addOutEdge(B, 1.2);
graph.addInEdge(C, 0.2);
graph.addInEdge(C, 1.2); graph.show(); }}Copy the codeConsole output:
Set of vertices: [A,B,C]2
B:1
C:0Vertex entry: A:0
B:1
C:2Set of edges: <A,B> <A,C> <B,C>Copy the code3.4 Adjacency multiple list
For undirected graphs, adjacency lists focus on vertices, and it is convenient to determine whether there are relationships between vertices, or to count the degree of vertices. However, once you want to operate on an edge, such as deleting an edge, marking an edge, it is very troublesome.
As follows, to remove edges (A,D), you need to remove two nodes from the list on the right.
Adjacency multiple list: Vertices and edges are structured as follows, edges inivexandjvexThese are the indices of the two vertices attached to this edge,ilinkIt’s pointing attached to the vertexivexThe next side of theta,jlinkThe point is attached to the vertexjvexThe next side of theta.
As shown below, the right side uses an adjacency multiple list to represent the left figure.
3.5 Number of edge sets
Two one-dimensional arrays are used, one for vertex information and one for edge information. The edge structure is as follows,beginThe starting index of the memory edge,endThe end index of the memory edge,weightStore weights.
As shown below, the number of edge sets is used to represent the left directed graph.
The edge-set group is concerned with the set of edges and is suitable for processing the edges in turn. If you want to determine the degree of vertices, you have to go through the whole graph, which is not very efficient.
4. To summarize
Graphs are a very useful data structure. They are much more complex than linear tables and trees, and they have many concepts, but fortunately there are rules to follow and you don’t have to memorize them. The introduction diagram uses the set knowledge of high school, and also reviews mathematics. This paper introduces many definitions and concepts of graph, as well as five realization modes of graph. Different realization modes have different characteristics and need flexible application.