Data Structure - Graph

The concept of Graphs
Graph is a set of vertices connected by edges.
Edges can have weights, that is, each edge can be assigned either positive or negative.
Edges are divided into Directed Edge and Undirected Edge.
The degree of a vertex connects the number of edges of that vertex.

Graph representation

For the figure above, there are two main representations:

  • Adjaccency List
    The advantage of adjacency tables is that they save space and only store the actual edges.
    The disadvantage is that when you focus on the degree of vertices, you may have to traverse a list of chains.
    The implementation illustration is as follows:

    Java implementation code:
/**
 * Adjacency Table Implementation of Directed Weighted Graph
 */
public class LinkGraph {

    //vertex
    private class Vertex {
        char data;          //Name of vertex (value)
        Node firstEdge;     //The first adjacent point of a vertex
    }

    //Information about the adjacent points of a vertex
    private class Node {
        int index;       //Represents the ordinal number of this Node in the vertex array
        int weight;      //The weight of the vertex on the edge of this adjacent point
        Node nextNode;   //Next Adjacent Point of Point
    }

    //edge
    static class Edge {
        char start;        //The vertex name (value) of the starting point
        char end;          //The vertex name (value) of the focus
        int weight;        //Edge weight

        public Edge(char start, char end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }

    private Vertex[] vertexNameList;    //Array of all vertex names

    public LinkGraph(char[] vert, Edge[] edge){
        //Read in vertices and initialize
        vertexNameList = new Vertex[vert.length];
        parent = new int[vert.length];

        for (int i = 0; i < vert.length; i++) {
            vertexNameList[i] = new Vertex();
            vertexNameList[i].data = vert[i];   //Vertex Name
            vertexNameList[i].firstEdge = null; //No adjacent points, of course no side
        }

        //Initialize Edges
        for (int i = 0; i < edge.length; i++) {
            char start = edge[i].start;
            char end = edge[i].end;

            //Get the ordinal of the vertex
            int startRank = getPosition(start);
            int endRank = getPosition(end);

            //1.endRank is the adjacent point of startRank, linking endRank to a list of chains headed with startRank
            Node endRankNode = new Node();
            endRankNode.index = endRank;
            endRankNode.weight = edge[i].weight;
            linkedLast(startRank,endRankNode);
        }
    }
	
    //A tail interpolation method that connects a vertex to the tail of a list of chains
    private void linkedLast(int index, Node node) {
        if(vertexNameList[index].firstEdge == null)
            vertexNameList[index].firstEdge = node;
        else{
            Node tmp = vertexNameList[index].firstEdge;
            while(tmp.nextNode != null){
                tmp = tmp.nextNode;
            }
            tmp.nextNode = node;
        }
    }

    //Gets the ordinal number of a vertex in an array
    private int getPosition(char v) {
        for (int i = 0; i < vertexNameList.length; i++) {
            if(vertexNameList[i].data == v) return i;
        }
        //Returns -1 if no such vertex exists
        return -1;
    }

    public static void main(String[] args) {
        char[] vexs = {'A', 'B', 'C', 'D', 'E'};   //vertex
        Edge[] edges = {                           //edge
                // Right of Start and End
                new Edge('A', 'B', 5.6),
                new Edge('A', 'C', 1.0),
                new Edge('A', 'D', 4.2),
                new Edge('B', 'C', 2.7),
                new Edge('C', 'A',  1.0),
                new Edge('C', 'B',  2.7),
                new Edge('E', 'B',  -3.0)
        };
        LinkGraph graph = new LinkGraph(vexs,edges);
    }
  • Adjacency Matrix
    The advantage of adjacency matrix is that edges can be added and deleted quickly, and edges can be quickly determined between two points.
    The disadvantage is that, for example, fewer edges between vertices wastes space because it is an n*n matrix.
    The implementation illustration is as follows:

    Java implementation code:
/**
 * Implementation of adjacency matrix
 */
public class MatrixGraph {

    private char[] vertex;     //Set of vertex names

    private int[][] edges;     //Adjacency matrix, storing edges

    private int numOfEdges;     //Number of Edges

    public MatrixGraph(int n){
        edges = new int[n][n];
        vertex = new char[n];
    }

    //Number of vertices
    public int getNumOfVertexs(){
        return vertex.length;
    }

    //Number of Edges
    public int getNumOfEdges(){
        return numOfEdges;
    }

    //Gets the weight from the vertex of ordinal v1 to the vertex of ordinal v2
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    //Insert an edge
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        numOfEdges++;
    }

    //Gets the subscript of the vertex array for the first adjacent point of a vertex subscript v
    public int getFirstNeighbor(int v){
        for (int i = 0; i < vertex.length; i++) {
            if(edges[v][i] != 0)
                return i;
        }
        return -1;
    }

    //Gets the next adjacent point of V1 from the previous adjacent point subscript v2 of vertex subscript v1
    public int getNextNeighbor(int v1,int v2){
        for (int i = v2+1; i < vertex.length; i++) {
            if(edges[v1][i] != 0)
                return i;
        }
        return -1;
    }
}

Traversal algorithm of graph (based on adjacency table)

  1. Depth first traversal (DFS: Depth First Search)
    The process of depth-first algorithm is simply to start from the starting point, find a deepest path, and then go back to the previous node and continue to find the deepest path (each node can only visit once).
    Java implementation code:
    //Depth First Search (DFS) traversal graph starting from the first vertex
    public void DFS(){
        boolean[] visited = new boolean[vertexNameList.length];  //Whether the vertex has been traversed, defaulting to false
        int[] path = new int[vertexNameList.length];             //The order in which the vertices appear during traversal, recording their subscripts in order
        int index = 0;                                           //Index of path[]

        /**
         * MyStack:Represents the data structure - stack; FIFO
         * Basic operation of stack:
         * 1) push(Object o): Element stacking
         * 2) Object pop(): Returns the top element of the stack and removes it from the stack.
         * 3) Object peek(): Returns the top element of the stack without deleting it.
         */
        MyStack stack = new MyStack(vertexNameList.length);

        for (int i = 0; i < visited.length; i++)
        {
            //Use the stack's LIFO feature to find the deepest path first
            stack.push(i);

            if(!visited[i])
            {
                visited[i] = true;                                     //The vertex of subscript i is traversed
                path[index++] = i;                                     //The first traversed vertex whose subscript is i

                while(!stack.isEmpty())
                {
                    int v = getUnVisitedVertex(stack.peek(),visited);
                    //If there are no adjacent points to visit, go out of the stack and go back
                    if(v == -1) stack.pop();
                    else
                    {
                        path[index++] = v;   //Access Contiguity Order
                        visited[v] = true;   //Adjacency point v has been visited
                        stack.push(v);       //Push
                    }

                }
            }
            else
            {
                stack.pop();
            }
        }

        //Print DFS Path
        System.out.println("DFS Route:");
        for (int i = 0; i < path.length; i++) {
            System.out.print(vertexNameList[path[i]].data + " ");
        }

    }

    //Returns the sequence number of an adjacent point whose vertex has not been visited
    private int getUnVisitedVertex(Integer v, boolean[] visited) {
        Node tmp = vertexNameList[v].firstEdge;

        //If there is an adjacent point and the adjacent point has not been traversed, the adjacent point subscript is returned.
        while(tmp != null){
            if(!visited[tmp.index]) return tmp.index;
            tmp = tmp.nextNode;
        }
        //There are no unreached adjacent points
        return -1;
    }

Stack in and out stack order:

  1. Width preferred traversal (BFS: Breadth First Search)
    The breadth-first algorithm starts with the starting point, finds all the adjacent points of this point, and then, starting with its first adjacent point, continues to find the widest path (each node can only visit once).
    Java implementation code:
    //Width first search, traverse from the first vertex
    public void BFS(){
        boolean[] visited = new boolean[vertexNameList.length];  //Whether the vertex has been traversed, defaulting to false
        int[] path = new int[vertexNameList.length];             //The order in which the vertices appear during traversal, recording their subscripts in order
        int index = 0;                                           //Index of path[]

        /**
         * MyQueue:Represents a data structure - a queue; FIFO
         * Basic operation of queue:
         * 1) enqueue(T t): Element Entry
         * 2)  T dequeue(): The element queues and deletes it from the queue.
         * 3)     T peek(): Returns the queue header element without deleting it.
         */
        MyQueue<Integer> queue = new MyQueue<Integer>(vertexNameList.length);

        for (int i = 0; i < visited.length; i++)
        {
            //Find the broadest route first using the first-in-first-out feature of the queue
            queue.enqueue(i);

            if(!visited[i])
            {
                visited[i] = true;                                     //The vertex of subscript i is traversed
                path[index++] = i;                                     //The first traversed vertex whose subscript is i

                while(!queue.isEmpty())
                {
                    int v = getUnVisitedVertex(queue.peek(),visited);
                    //If no adjacent points are visited, queue
                    if(v == -1) queue.dequeue();
                    else
                    {
                        path[index++] = v;
                        visited[v] = true;
                        queue.enqueue(v);
                    }
                }
            }
            else
            {
                queue.dequeue();
            }

        }


        //Print BFS Path
        System.out.println("BFS Route:");
        for (int i = 0; i < path.length; i++) {
            System.out.print(vertexNameList[path[i]].data + " ");
        }
    }

Queue in and out queue order:

Tags: Programming Java

Posted on Sun, 08 Sep 2019 09:49:43 -0700 by surfnjunkie