# The basic concept and storage structure of graph

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.

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

2. 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 <>.

3. 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 out-degree: the edge with the direction away from the vertex; in-degree: the edge with the direction pointing to the vertex. The degree of a directed graph is the sum of the in-degree and out-degree.

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:

1. 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 is not of Edges

= 0 : Vi = Vj

The i-th 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.

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

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.

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
// 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) {
}

// 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){
}
}

// insert a new node and return its position
public  int  insertVertex (T 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 ++){
}
for(j = temp.length; j < temp.length * 2; j ++){
}
}
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
}
}
for(int i = x + 1; i < len; i ++){
for(int j = 0; j < x; j ++){
}
}
for(int i = x + 1; i < len; i ++){
for(int j = i + 1; j < len; 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 ){
}
}

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)};
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: