我是靠谱客的博主 俊秀白羊,这篇文章主要介绍Java数据结构之图的领接矩阵详解,现在分享给大家,希望可以做个参考。

1.图的领接矩阵(Adjacency Matrix)存储结构

图的领接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一位数组存储图中顶点信息,一个二维数组(称为领接矩阵)存储图中的边或弧的信息。

举例

无向图

无向图的领接矩阵的第i行或第i列的非零元素个数正好是第i个顶点的度。

有向图

有向图的领接矩阵的第i行的非零元素个数正好是第i个顶点的出度,第i列的非零元素个数正好是第i个顶点的入度。

带权值的网图

2.图的接口类

3.图的类型,用枚举类表示

复制代码
1
2
3
public enum GraphKind { UDG,DG,UDN,DN;//无向图、有向图、无向网、有向网 }

4.图的领接矩阵描述

对于一个具有n个顶点的图G,可以将图G的领接矩阵存储在一个二维数组中.

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package Graph; /* 图的领接矩阵描述类 */ import java.util.Scanner; public class MyGraph implements IGraph { public final static int INFINITY = Integer.MAX_VALUE; private GraphKind kind; //图的标志 private int vexNum, arcNum; //图当前顶点和边数 private Object[] vexs; //顶点 private int[][] arcs; //邻接矩阵 public MyGraph() { //空参构造 this(null, 0, 0, null, null); } public MyGraph(GraphKind kind, int vexNum, int arcNum, Object[] vexs, int[][] arcs) { // 实参构造 this.kind = kind; this.vexNum = vexNum; this.arcNum = arcNum; this.vexs = vexs; this.arcs = arcs; } @Override public void createGraph() { //创建新图 Scanner sc = new Scanner(System.in); System.out.println("请输入图的类型:"); 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() { //创建无向图 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] = 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("第" + v + "个顶点不存在!"); return vexs[v]; <0v<vexNum } @Override public int locateVex(Object vex) { //顶点定位法 for (int v = 0; v < vexNum; v++) if (vexs[v].equals(vex)) return v; return 0; } @Override public int firstAdjVex(int v) throws Exception { //查找第一个领接点 if (v < 0 && v >= vexNum) throw new Exception("第" + v + "个顶点不存在!"); for (int j = 0; j < vexNum; j++) if (arcs[v][j] != 0 && arcs[v][j] < INFINITY) return j; return -1; } @Override public int nextAdjvex(int v, int w) { //查找下一个领接点 return 0; } public GraphKind getKind(){ //返回图标类型 return kind; } public int[][] getArcs() { //返回邻接矩阵的值 return arcs; } //返回顶点 public Object[] getVexs() { return vexs; } }

测试类

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) throws Exception { MyGraph M=new MyGraph(); //创建图空间 M.createGraph(); System.out.println("创建无向网的顶点个数为:"+M.getVexNum()); System.out.println("创建无向网的边个数为:"+M.getArcNum()); System.out.println("请输入要查找顶点的值:"); Scanner sc=new Scanner(System.in); Object top=sc.next(); System.out.println("要查找顶点"+top+"的值为:"+ M.locateVex(top)); System.out.println("请输入要查找顶点的索引:"); int x= sc.nextInt(); System.out.println("要查找位置"+x+"处的顶点值为:"+M.getVex(x) ); System.out.println("请输入邻接点的顶点的位置:"); int n= sc.nextInt(); System.out.println("要查找位置"+n+"处的顶点值为:"+M.firstAdjVex(n) ); } }

结果

以上就是Java数据结构之图的领接矩阵详解的详细内容,更多关于Java数据结构资料请关注靠谱客其它相关文章!

最后

以上就是俊秀白羊最近收集整理的关于Java数据结构之图的领接矩阵详解的全部内容,更多相关Java数据结构之图内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(139)

评论列表共有 0 条评论

立即
投稿
返回
顶部