Basic concepts of graphs:
Definition : A graph (Graph) is composed of a finite non [empty set] is composed of a finite non [empty set] of vertices and a set of edges between vertices, usually expressed as: G(V,E), where G represents a graph, and V(vertex) is a graph in G The set of vertices, E(edge) is the set of edges in the graph G.
Classification : 1. Classification according to whether there is a direction: directed graph and undirected graph.
An undirected graph consists of vertices and edges, while a directed graph consists of vertices and arcs. An arc has two parts: the head and the tail.

If there is an edge between any two vertices, it is called a complete graph; a directed graph is called a directed complete graph.

If there are no repeated edges or edges from vertices to itself, it is called a simple graph. Mathematical representation: undirected graphs are represented by (), and directed graphs are represented by <>.

Graphs with weights and graphs without weights.
The relationship between the vertices and edges of the graph:
Degree of a vertex: It is the number of edges associated with a vertex. In a directed graph, it is divided into outdegree: the edge with the direction away from the vertex; indegree: the edge with the direction pointing to the vertex. The degree of a directed graph is the sum of the indegree and outdegree.
Path length: The number of edges or arcs on the path.
Connectivity:
In an undirected graph, if there is a path from one vertex to any other vertex, the graph is said to be connected. A directed graph with this property is called a strongly connected graph.
If the undirected graph formed by removing all the directed edges of a directed graph is called the basic graph of the directed graph, also called the basic graph.
A directed graph is not strongly connected, but its base graph is connected, so it is called weakly connected.
Diagram representation:
 Adjacency matrix: use a vertex array to store vertices, and use an edge array to store whether there is an edge between vertices.
a[i, j] = 1 (i , j ) belongs to Edge, otherwise equals 0. That is, 0 means there is no edge, and 1 means there is an edge.
The representation of the weighted adjacency matrix:
a[i, j] = weight : if Vi is not equal to Vj && (Vi, Vj) or < Vi, Vj > belongs to Edges
= ∞ : if Vi is not equal to Vj && (Vi, Vj) or
= 0 : Vi = Vj
 Adjacency list:
The ith vertex information in the vertex table stores the data value data of the vertex and a head pointer adj of the linked list. The first edge node of the edge linked list corresponding to the node Vi can be found through adj. At the boundary point, the node saves dest: indicating the vertex number of another node on the edge; it also has a pointer link, pointing to the next edge node, if it is a graph with weights, then add another cost to the boundary point, The weight node used to hold this edge.
 Adjacent multilist and crosslinked list representation (brief introduction):
Undirected adjacency multilist:
Edge nodes: vertex1 and vertex2 are vertex domains, indicating the two nodes attached to the edge, path1, path2 represent linked list pointers, pointing to the next edge attached to vertex1 and vertex2.
mark : mark the field, whether it has been processed. 0: not processed; 1: processed  vertex1  vertex2  path1  path2 
vertex node:
data: store vertex related information  firstout: pointer field, pointing to the first edge of the attachment 
Directed crosslinked list:
Edge nodes: vertex1 and vertex2 are vertex domains, representing the start and end vertex numbers of the directed edge, respectively, path1, path2 represent linked list pointers, path1 points to the next edge with the same start vertex, path2 points to the same edge as the edge The next edge with the same terminal vertex.
Adjacency matrix implementation with weights:
Graph interface:
public interface GGraph<T> { //final keyword: Modifies classes, variables, and methods, indicating that they cannot be modified, overridden and inherited public static final int MAX_WEIGHT = 999999 ; // Symbolizes infinity int vertex_Number () ; // the number of nodes T getElement ( int i ) ; // the associated value of the vertex int getWeight ( int i, int j) ; // returns the weight of the <Vi, Vj> edge int insertVertex (T x) ; // insert the node value of element value x, return the vertex number void insertEdge ( int i, int j, int weight) ; // Insert an edge with weight <Vi, Vj> void removeVertex ( int i) ; // remove vertex Vi and its associated edges void removeEdge ( int i, int j) ; // remove <Vi, Vj> int getNextNeighbor ( int i, int j) ; //Return the next adjacent node number of Vi after Vj }
Classes with weighted edges:
public class Edge implements Comparable<Edge>{ public int begin, end, weight; public Edge(int begin, int end, int weight){ this.begin = begin; this.end = end; this.weight = weight; } public String toString(){ return "[" + begin + "," + end + "," + weight + "]"; } @Override public int compareTo (Edge o) { if ( this .begin != o.begin){ return this .begin  o.begin; //If the starting point is different, return the difference of the starting point, otherwise return the difference of the ending point } return this.end  o.end; } }
Implement the insertion, deletion, etc. of the adjacency matrix:
public class AdjMatrixGraph<T>{ // Stores the vertex collection of the graph protected ArrayList<T> vertexList; // The adjacency matrix of the graph protected int [][] adjMatrix; // The maximum value is set private final int MAX_WEIGHT = 9999999 ; // Initialization of graph public AdjMatrixGraph ( int size) { size = size > 10 ? 10 : size; // define collection and matrix size this .vertexList = new ArrayList<T>(size); this .adjMatrix = new int [size][size]; // initialize matrix for ( int i = 0 ; i < size; i + +){ for ( int j = 0 ; j < size; j ++){ // own and own weights are 0 adjMatrix[i][j] = (i == j) ? 0 : MAX_WEIGHT; } } } //Construct graph from vertex set and edge set public AdjMatrixGraph(T[] vertices, Edge [] edges){ this(vertices.length); if(vertices == null){ return; } for(int i = 0; i < vertices.length; i ++){ insertVertex(vertices[i]); } if(edges != null){ for(int j = 0; j < edges.length; j ++){ insertEdge(edges[j]); } } } //return the number of vertices public int vertex_Number () { return this .vertexList.size(); } //Return the data element value of vertex Vi, if invalid, return null public T getElement ( int i) { return this .vertexList.get(i); } // return the weight of the <Vi, Vj> edge public int getWeight ( int i, int j) { return adjMatrix[i][j]; } // Insert edge and its weight public void insertEdge (Edge edge) { this .insertEdge(edge.begin, edge.end, edge.weight); } public void insertEdge(int i, int j, int weight) { int len = this.vertex_Number(); if(i >= 0 && i < len && j >= 0 && j < len  i != j && this.adjMatrix[i][j] == MAX_WEIGHT){ this.adjMatrix[i][j] = weight; } } // insert a new node and return its position public int insertVertex (T vertex) { this .vertexList.add(vertex); // extend if ( this .vertex_Number() > this .adjMatrix.length){ //copy element int temp[][] = adjMatrix, i, j; this.adjMatrix = new int[temp.length * 2][temp.length * 2]; for(i = 0; i < temp.length; i ++){ for(j = 0; j < temp.length; j ++){ this.adjMatrix[i][j] = temp[i][j]; } for(j = temp.length; j < temp.length * 2; j ++){ this.adjMatrix[i][j] = MAX_WEIGHT; } } for(i = temp.length; i < temp.length * 2; i ++){ for(j = 0; j < temp.length * 2; j ++){ this.adjMatrix[i][j] = (i == j) ? 0 : MAX_WEIGHT; } } } return this.vertexList.size()  1; } // remove the node and its corresponding matrix is also changing public void removeVertex ( int x) { int len = this .vertex_Number(); if (x < 0  x > len){ System.out.println("error!"); return; } this .vertexList.remove(x); //remove a row and a column about it for ( int i = 0 ; i < x; i ++){ for ( int j = x + 1 ; j < len; j + +){ // Shift left one place this .adjMatrix[i][j  1 ] = this .adjMatrix[i][j]; } } for(int i = x + 1; i < len; i ++){ for(int j = 0; j < x; j ++){ this.adjMatrix[i  1][j] = this.adjMatrix[i][j]; } } for(int i = x + 1; i < len; i ++){ for(int j = i + 1; j < len; j ++){ this.adjMatrix[i  1][j  1] = this.adjMatrix[i][j]; } } } //Remove the edge and make it invalid public void removeEdge ( int i, int j) { if (i >= 0 && i < vertex_Number() && j >= 0 && j < vertex_Number() && i != j ){ this .adjMatrix[i][j] = MAX_WEIGHT; } } public String toString(){ String str = "Vertex collection:" + this .vertexList.toString() + "\n Adjacency matrix is:\n" ; int len = this .vertex_Number(); for(int i = 0; i < len; i ++){ for(int j = 0; j < len; j ++){ str += this.adjMatrix[i][j] == MAX_WEIGHT ? " ∞" : " " + this.adjMatrix[i][j]; } str += "\n"; } return str; } }
Test code:
public class Test { public static void main(String[] args) { String [] vertices = {"A", "B", "C", "D", "E"}; Edge [] edges = {new Edge(0, 1, 5), new Edge(0, 3, 2), new Edge(1, 0, 5), new Edge(1, 2, 7), new Edge(1, 3, 6), new Edge(2, 1, 7), new Edge(2, 3, 8), new Edge(2, 4, 3), new Edge(3, 0, 2), new Edge(3, 1, 6), new Edge(3, 2, 8), new Edge(3, 4, 9), new Edge(4, 2, 3), new Edge(4, 3, 9)}; AdjMatrixGraph<String> graph = new AdjMatrixGraph<>(vertices, edges); System.out.println(graph.toString()); int i = graph.insertVertex("F"); graph.insertEdge(0, i, 20); graph.insertEdge(i, 0, 20); graph.removeVertex(2); graph.removeEdge(2, 3); graph.removeEdge(3, 2); System.out.println(graph.toString()); } }
Test screenshot:
The content of the article is limited, this article is written here. Suggestions are welcome, thank you!