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

  1. Adjacency list:

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.

  1. Adjacent multi-list and cross-linked 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 cross-linked 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!

Leave a Comment

Your email address will not be published. Required fields are marked *