Introduction to undirected graphs of adjacent tables
An undirected graph of an adjacency table refers to an undirected graph represented by an adjacency table.
The above figure G1 contains 7 vertices of "A,B,C,D,E,F,G", and contains 7 edges of "(A,C), (A,D), (A,F), (B,C), (C,D), (E,G), (F,G)".
The matrix on the right of the figure above is the adjacency of G1 in memory indicating the intent. Each vertex contains a linked list that records the "sequence number of the adjacent points of the vertex". For example, the data of the nodes contained in the linked list contained in the second vertex (vertex C) are respectively "0, 1, 3"; and these "0, 1, 3" correspond to the sequence numbers of "A, B, D", and "A, B, D" are all adjacent points of C. This is how to record the information of the picture.
Code description of undirected graph of adjacency table
1. Basic definition
public class ListUDG {// The vertex that adjaces the table corresponding to the linked list private class ENode {int ivex;// The position of the vertex that the edge points to ENode nextEdge;// Pointer to the next arc}// The vertex that adjaces the table in the table private class VNode {char data;// Vertex information ENode firstEdge;// Pointer to the first arc that attaches to the vertex};private VNode[] mVexs;// Vertex array...}(01) ListUDG is the structure corresponding to the adjacency table. mVexs is a one-dimensional array that stores vertex information.
(02) VNode is the structure corresponding to the vertices of the adjacent table. data is the data contained in the vertex, and firstEdge is the header pointer of the linked list contained in the vertex.
(03)ENode is the structure corresponding to the nodes that are adjacent to the linked list contained in the vertices of the table. ivex is the index of the vertex corresponding to this node in vexs, while nextEdge points to the next node.
2. Create a matrix
Here are two methods to create a matrix. One uses known data, and the other requires the user to enter the data manually.
2.1 Create a graph (using the provided matrix)
/* * Create a graph (using the provided matrix) * * Parameter description: * vexs -- Vertex array* edges -- Edge array*/public ListUDG(char[] vexs, char[][] edges) {// Initialize "Vertex" and "Edge" int vlen = vexs.length;int elen = edges.length;// Initialize "Vexs" mVexs = new VNode[vlen];for (int i = 0; i < mVexs.length; i++) {mVexs[i] = new VNode();mVexs[i].data = vexs[i];mVexs[i].firstEdge = null;}// Initialize "edges" for (int i = 0; i < elen; i++) {// Read the starting vertex and ending vertex of the edge char c1 = edges[i][0];char c2 = edges[i][1];// Read the starting vertex and ending vertex of the edge int p1 = getPosition(edges[i][0]);int p2 = getPosition(edges[i][1]);// Initialize node1ENode node1 = new ENode();node1.ivex = p2;// Link node1 to "the end of the linked list where p1 is located" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1);// Initialize node2ENode node2 = new ENode();node2.ivex = p1;// Link node2 to "the end of the linked list where p2 is located" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2);}}The function is to create an undirected graph of an adjacency table. In fact, the undirected graph created by this method is Figure G1 above. The call code is as follows:
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};char[][] edges = new char[][]{ {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}};ListUDG pG;pG = new ListUDG(vexs, edges);2.2 Create a graph (enter yourself)
/* * Create a graph (enter the data yourself) */public ListUDG() {// Enter "Version Number" and "Edge Number" System.out.printf("input vertex number: ");int vlen = readint();System.out.printf("input edge number: ");int elen = readint();if (vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1))))) {System.out.printf("input error: invalid parameters!/n");return ;}// Initialize "Version" mVexs = new VNode[vlen];for (int i = 0; i < mVexs.length; i++) {System.out.printf("vertex(%d): ", i);mVexs[i] = new VNode();mVexs[i].data = readchar();mVexs[i].firstEdge = null;}// Initialize "edge"//mMatrix = new int[vlen][vlen];for (int i = 0; i < elen; i++) {// Read the starting and ending vertex of the edge System.out.printf("edge(%d):", i);char c1 = readchar();char c2 = readchar();int p1 = getPosition(c1);int p2 = getPosition(c2);// Initialize node1ENode node1 = new ENode();node1.ivex = p2;// Link node1 to "the end of the linked list where p1 is located" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1);// Initialize node2ENode node2 = new ENode();node2.ivex = p1;// Link node2 to "the end of the linked list where p2 is located" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2);}}This function reads the user's input and converts the input data into the corresponding undirected graph.
The complete source code of the undirected graph of the adjacency table
import java.io.IOException;import java.util.Scanner;public class ListUDG {// The vertex that is adjacent to the linked list corresponding to the table in the table private class ENode {int ivex;// The position of the vertex that the edge points to ENode nextEdge;// Pointer to the next arc}// The vertex that is adjacent to the table in the table private class VNode {char data;// Vertex information ENode firstEdge;// Pointer to the first arc that is attached to the vertex};private VNode[] mVexs;// Vertex array/* * Create a graph (input data by yourself) */public ListUDG() {// Enter "Vertex Number" and "Edge Number"System.out.printf("input vertex number: ");int vlen = readint();System.out.printf("input edge number: ");int elen = readint();if (vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1))))) {System.out.printf("input error: invalid parameters!/n");return ;}// Initialize "Vertex"mVexs = new VNode[vlen];for (int i = 0; i < mVexs.length; i++) {System.out.printf("vertex(%d): ", i);mVexs[i] = new VNode();mVexs[i].data = readchar();mVexs[i].firstEdge = null;}// Initialize "edge"//mMatrix = new int[vlen][vlen];for (int i = 0; i < elen; i++) {// Read the starting and ending vertex of the edge System.out.printf("edge(%d):", i);char c1 = readchar();char c2 = readchar();int p1 = getPosition(c1);int p2 = getPosition(c2);// Initialize node1ENode node1 = new ENode();node1.ivex = p2;// Link node1 to "the end of the linked list where p1 is located" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1);// Initialize node2ENode node2 = new ENode();node2.ivex = p1;// Link node2 to "the end of the linked list where p2 is located" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2);}}/* * Create a graph (using the provided matrix) * * Parameter description: * vexs -- Vertex array* edges -- Edge array*/public ListUDG(char[] vexs, char[][] edges) {// Initialize "vertex number" and "edge number" int vlen = vexs.length;int elen = edges.length;// Initialize "vertex" mVexs = new VNode[vlen];for (int i = 0; i < mVexs.length; i++) {mVexs[i] = new VNode();mVexs[i].data = vexs[i];mVexs[i].firstEdge = null;}// Initialize "edges" for (int i = 0; i < elen; i++) {// Read the starting vertex and ending vertex of the edge char c1 = edges[i][0];char c2 = edges[i][1];// Read the starting vertex and ending vertex of the edge int p1 = getPosition(edges[i][0]);int p2 = getPosition(edges[i][1]);// Initialize node1ENode node1 = new ENode();node1.ivex = p2;// Link node1 to "the end of the linked list where p1 is located" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1);// Initialize node2ENode node2 = new ENode();node2.ivex = p1;// Link node2 to "the end of the linked list where p2 is located" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2);}}/* * Link the node node to the last of the list*/private void linkLast(ENode list, ENode node) {ENode p = list;while(p.nextEdge!=null) p = p.nextEdge;p.nextEdge = node;}/* * Return the ch position*/private int getPosition(char ch) {for (int i=0; i<mVexs.length; i++) if(mVexs[i].data==ch) return i;return -1;}/* * Read an input character*/private char readchar() {char ch='0';do {try {ch = (char)System.in.read();}catch (IOException e) {e.printStackTrace();}}while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));return ch;}/* * Read an input character*/private int readint() {Scanner scanner = new Scanner(System.in);return scanner.nextint();}/* * Print matrix queue graph*/public void print() {System.out.printf("List Graph:/n");for (int i = 0; i < mVexs.length; i++) {System.out.printf("%d(%c): ", i, mVexs[i].data);ENode node = mVexs[i].firstEdge; while (node != null) {System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);node = node.nextEdge;}System.out.printf("/n");}}public static void main(String[] args) {char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};char[][] edges = new char[][]{ {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}};ListUDG pG;// Custom "graph" (input matrix queue)//pG = new ListUDG();// Use the existing "graph" pG = new ListUDG(vexs, edges);pG.print();// Print diagram}}Summarize
The above is all the content of this article about implementing the complete source code of the Java language of the adjacency table undirected graph. I hope it will be helpful to everyone. Interested friends can continue to refer to this site:
Detailed explanation of Java calculation mathematical expression code
Detailed explanation of variable length parameter code in Java
Java language solution to perfect number code analysis
If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!