Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "the example analysis of the leading matrix of Java data structure diagram". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. The Adjacency Matrix storage structure of graphs

The Adjacency Matrix of the graph is stored in two arrays to represent the graph. An one-digit array stores vertex information in the graph, and a two-dimensional array (called a tie matrix) stores information about edges or arcs in the graph.

Give an example

Undirected graph

The number of non-zero elements in row I or column I of the leading matrix of an undirected graph is exactly the degree of the first vertex.

Directed graph

The number of non-zero elements in row I of the leading matrix of a digraph is exactly the degree of the first vertex, and the number of non-zero elements in column I is exactly the degree of the first vertex.

Network graph with weight

two。 Interface class of a graph

3. The type of graph, using enumerated classes to represent public enum GraphKind {UDG,DG,UDN,DN;// undirected graph, directed graph, undirected network, directed network} 4. The description of the connection matrix of a graph

For a graph G with n vertices, the connection matrix of graph G can be stored in a two-dimensional array.

The leading matrix of the package Graph;/* graph describes the class * / import java.util.Scanner; public class MyGraph implements IGraph {public final static int INFINITY = Integer.MAX_VALUE; private GraphKind kind; / / the flag private int vexNum of the graph, the current number of vertices and edges of the arcNum; / / graph private Object [] vexs; / / vertex private int [] [] arcs / / adjacency matrix public MyGraph () {/ / empty parameter construction this (null, 0,0, null, null);} public MyGraph (GraphKind kind, int vexNum, int arcNum, Object [] vexs, int [] arcs) {/ / argument construction this.kind = kind; this.vexNum = vexNum; this.arcNum = arcNum This.vexs = vexs; this.arcs = arcs;} @ Override public void createGraph () {/ / create a new graph Scanner sc = new Scanner (System.in); System.out.println ("Please enter the type of graph:"); GraphKind kind = GraphKind.valueOf (sc.next ()) Switch (kind) {case UDG: createUDG (); return; case DG: createDG (); return; case UDN: createUDG (); return; case DN: createDN () Return;}} private void createUDG () {/ / create an undirected graph Scanner sc = new Scanner (System.in); System.out.println ("Please enter the number of vertices and edges of the graph:"); vexNum = sc.nextInt (); arcNum = sc.nextInt (); vexs = new Object [vexNum] System.out.println ("enter each vertex of the graph separately"); for (int v = 0; v)

< vexNum; v++) //构造顶点函数 vexs[v] = sc.next(); arcs = new int[vexNum][vexNum]; for (int v = 0; v < vexNum; v++) for (int u = 0; u < vexNum; u++) arcs[v][u] = INFINITY; //初始化领接矩阵 System.out.println("请输入各个边的两个顶点及其权值："); for (int k = 0; k < arcNum; k++) { int v = locateVex(sc.next()); int u = locateVex(sc.next()); arcs[v][u] = arcs[v][u] = sc.nextInt(); } } private void createDG() { //创建有向图 } ; private void createUDN() { //创建无向网 } private void createDN() { //创建有向网 Scanner sc = new Scanner(System.in); System.out.println("请输入图的顶点数、图的边数："); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new Object[vexNum]; System.out.println("请分别输入图的各个顶点"); for (int v = 0; v < vexNum; v++) //构造顶点函数 vexs[v] = sc.next(); arcs = new int[vexNum][vexNum]; for (int v = 0; v < vexNum; v++) for (int u = 0; u < vexNum; u++) arcs[v][u] = INFINITY; //初始化领接矩阵 System.out.println("请输入各个边的两个顶点及其权值："); for (int k = 0; k < arcNum; k++) { int v = locateVex(sc.next()); int u = locateVex(sc.next()); arcs[v][u] = sc.nextInt(); } } @Override public int getVexNum() { return vexNum; //返回顶点数 } @Override public int getArcNum() { return arcNum; //返回边数 } @Override //返回v的第一个领接点，若v没有领接点返回-1; public Object getVex(int v) throws Exception { if (v < 0 && v >

= vexNum) throw new Exception ("Vertex" + v + "does not exist!") ; return vexs [v]

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.