用Java实现邻接表表示的无向图完整代码示例
邻接表无向图的介绍
邻接表无向图是指通过邻接表表示的无向图。
上面的图G1包含了”A,B,C,D,E,F,G”共7个顶点,而且包含了”(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)”共7条边。
上图右边的矩阵是G1在内存中的邻接表示意图。每一个顶点都包含一条链表,该链表记录了”该顶点的邻接点的序号”。例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是”0,1,3”;而这”0,1,3”分别对应”A,B,D”的序号,”A,B,D”都是C的邻接点。就是通过这种方式记录图的信息的。
邻接表无向图的代码说明
1. 基本定义
public class ListUDG { // 邻接表中表对应的链表的顶点 private class ENode { int ivex; // 该边所指向的顶点的位置 ENode nextEdge; // 指向下一条弧的指针 } // 邻接表中表的顶点 private class VNode { char data; // 顶点信息 ENode firstEdge; // 指向第一条依附该顶点的弧 } ; private VNode[] mVexs; // 顶点数组 ... }
(01)ListUDG是邻接表对应的结构体。mVexs则是保存顶点信息的一维数组。
(02)VNode是邻接表顶点对应的结构体。data是顶点所包含的数据,而firstEdge是该顶点所包含链表的表头指针。
(03)ENode是邻接表顶点所包含的链表的节点对应的结构体。ivex是该节点所对应的顶点在vexs中的索引,而nextEdge是指向下一个节点的。
2.创建矩阵
这里介绍提供了两个创建矩阵的方法。一个是用已知数据,另一个则需要用户手动输入数据。
2.1创建图(用已提供的矩阵)
/* * 创建图(用已提供的矩阵) * * 参数说明: * vexs -- 顶点数组 * edges -- 边数组 */ public ListUDG(char[] vexs, char[][] edges) { // 初始化"顶点数"和"边数" int vlen = vexs.length; int elen = edges.length; // 初始化"顶点" 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; } // 初始化"边" for (int i = 0; i < elen; i++) { // 读取边的起始顶点和结束顶点 char c1 = edges[i][0]; char c2 = edges[i][1]; // 读取边的起始顶点和结束顶点 int p1 = getPosition(edges[i][0]); int p2 = getPosition(edges[i][1]); // 初始化node1 ENode node1 = new ENode(); node1.ivex = p2; // 将node1链接到"p1所在链表的末尾" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 ENode node2 = new ENode(); node2.ivex = p1; // 将node2链接到"p2所在链表的末尾" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); } }
该函数的作用是创建一个邻接表无向图。实际上,该方法创建的无向图,就是上面图G1。调用代码如下:
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 创建图(自己输入)
/* * 创建图(自己输入数据) */ public ListUDG() { // 输入"顶点数"和"边数" 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 ; } // 初始化"顶点" 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; } // 初始化"边" //mMatrix = new int[vlen][vlen]; for (int i = 0; i < elen; i++) { // 读取边的起始顶点和结束顶点 System.out.printf("edge(%d):", i); char c1 = readchar(); char c2 = readchar(); int p1 = getPosition(c1); int p2 = getPosition(c2); // 初始化node1 ENode node1 = new ENode(); node1.ivex = p2; // 将node1链接到"p1所在链表的末尾" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 ENode node2 = new ENode(); node2.ivex = p1; // 将node2链接到"p2所在链表的末尾" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); } }
该函数是读取用户的输入,将输入的数据转换成对应的无向图。
邻接表无向图的完整源码
import java.io.IOException; import java.util.Scanner; public class ListUDG { // 邻接表中表对应的链表的顶点 private class ENode { int ivex; // 该边所指向的顶点的位置 ENode nextEdge; // 指向下一条弧的指针 } // 邻接表中表的顶点 private class VNode { char data; // 顶点信息 ENode firstEdge; // 指向第一条依附该顶点的弧 } ; private VNode[] mVexs; // 顶点数组 /* * 创建图(自己输入数据) */ public ListUDG() { // 输入"顶点数"和"边数" 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 ; } // 初始化"顶点" 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; } // 初始化"边" //mMatrix = new int[vlen][vlen]; for (int i = 0; i < elen; i++) { // 读取边的起始顶点和结束顶点 System.out.printf("edge(%d):", i); char c1 = readchar(); char c2 = readchar(); int p1 = getPosition(c1); int p2 = getPosition(c2); // 初始化node1 ENode node1 = new ENode(); node1.ivex = p2; // 将node1链接到"p1所在链表的末尾" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 ENode node2 = new ENode(); node2.ivex = p1; // 将node2链接到"p2所在链表的末尾" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); } } /* * 创建图(用已提供的矩阵) * * 参数说明: * vexs -- 顶点数组 * edges -- 边数组 */ public ListUDG(char[] vexs, char[][] edges) { // 初始化"顶点数"和"边数" int vlen = vexs.length; int elen = edges.length; // 初始化"顶点" 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; } // 初始化"边" for (int i = 0; i < elen; i++) { // 读取边的起始顶点和结束顶点 char c1 = edges[i][0]; char c2 = edges[i][1]; // 读取边的起始顶点和结束顶点 int p1 = getPosition(edges[i][0]); int p2 = getPosition(edges[i][1]); // 初始化node1 ENode node1 = new ENode(); node1.ivex = p2; // 将node1链接到"p1所在链表的末尾" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 ENode node2 = new ENode(); node2.ivex = p1; // 将node2链接到"p2所在链表的末尾" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); } } /* * 将node节点链接到list的最后 */ private void linkLast(ENode list, ENode node) { ENode p = list; while(p.nextEdge!=null) p = p.nextEdge; p.nextEdge = node; } /* * 返回ch位置 */ private int getPosition(char ch) { for (int i=0; i<mVexs.length; i++) if(mVexs[i].data==ch) return i; return -1; } /* * 读取一个输入字符 */ 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; } /* * 读取一个输入字符 */ private int readint() { Scanner scanner = new Scanner(System.in); return scanner.nextint(); } /* * 打印矩阵队列图 */ 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; // 自定义"图"(输入矩阵队列) //pG = new ListUDG(); // 采用已有的"图" pG = new ListUDG(vexs, edges); pG.print(); // 打印图 } }
总结
以上就是本文关于邻接表无向图的Java语言实现完整源码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:
Java计算数学表达式代码详解
Java中可变长度参数代码详解
Java语言求解完美数代码分析
如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
推荐阅读
-
用Java实现邻接表表示的无向图完整代码示例
-
Grid++Report 锐浪报表开发常见问题解答集锦-报表设计 问:怎样在设计时打印预览报表? 答:为了及时查看报表的设计效果,Grid++Report 报表设计应用程序提供了四种查看视图:普通视图、页面视图、预览视图与查询视图。通过窗口下边的 Tab 按钮可以在四种视图中任意切换。在预览视图中查看报表的打印预览效果,在查询视图中查看报表的查询显示效果。如果在报表的记录集提供了数据源连接串与查询 SQL,在进入预览视图与查询视图时会利用数据源连接串与查询 SQL 从数据源中自动取数,否则 Grid++Report 将自动生成模拟数据进行模拟打印预览与查询显示。注意:在预览视图与查询视图中看到的报表运行结果有可能与在你程序中的最终运行结果有差异,因为在报表的生成过程中我们可以在程序中对报表的生成行为进行一定的控制。 问:怎样用 Grid++Report 设计交叉表? 答:Grid++Report 没有提供专门实现交叉表的功能,其它的报表构件提供的交叉表功能一般也比较死板和功能有限。利用 Grid++Report 的编程接口可以做出灵活多变,功能丰富的交叉表。示例程序 CrossTab 就是一个实现交叉表的例子程序,认真领会此例子程序,你就可以做出自己想要各种交叉表,并能提取一些共用代码,便于重复使用。 问:怎样设置整个报表的缺省字体? 答:设置报表主对象的字体属性,也就是设置了整个报表的缺省字体。如果改变报表主对象的字体属性,则没有专门的设置字体属性的子对象的字体属性也跟随改变。同样每个报表节与明细网格也有字体属性,他们的字体属性也就是其拥有的子对象的缺省字体。 问:怎样在打印时限制一页的输出行数? 答:设定明细网格的内容行的‘每页行数(RowsPerPage)’属性即可。另外要注意‘调节行高(AdjustRowHeight)’属性值:为真时根据页面的输出高度自动调整行的高度,使整个页面的输出区域充满。为假时按设计时的高度输出行。 问:怎样显示中文大写金额? 答:将对象的“格式(Format)”属性设为 “$$” 及可,可以设置格式的对象有:字段(IGRField)、参数(IGRParameter)、系统变量(IGRSystemVarBox)与综合文字框(IGRMemoBox),其中综合文字框是在报表式上设格式。 问:能否实现自定义纸张与票据打印? 答:Grid++Report 完全支持自定义纸张的打印,只要在报表设定时在页面设置中选定自定义纸张,并指定准确的纸张尺寸。当然要在最终输出时得道合适的打印结果,输出打印机必须支持自定义纸张打印。Windows2000/XP/2003 操作系统上可以在打印机上定义自定义纸张,也可以采用这种方式实现自定义纸张打印。 问:怎样实现 0 值不打印? 答:直接设置格式串就可以,在“数字格式”设置对话框中选定“0 不显示”,就会得到合适的格式串。也可以通过直接录入格式串来指定 0 不显示,但格式串必须符合 Grid++Report 的规定格式。另一种实现办法是在报表获取明细记录数据时,在 BeforePostRecord 事件中将值为零的字段设为空,调用字段的 Clear 方法将字段置为空。 问:怎样实现多栏报表? 答:在明细网格上设‘页栏数(PageColumnCount)’属性值大于 1 即可。通过 Grid++Report 的“页栏输出顺序”还可以指定多栏报表的输出顺序是“先从上到下”还是“先从左到右”。 问:如何实现票据套打? 答:Grid++Report 为实现票据套打做了很多专门的安排:报表设计器提供了页面设计模式,按照设定的纸张尺寸显示设计面板,如果将空白票据的扫描图设为设计背景图,在定位报表内容的输出位置会非常方便。报表部件可以设定打印类别,非套打输出的内容在套打打印模式下就不会输出。 问:Grid++Report 有没有横向分页功能? 答:回答是肯定的,在列的总宽度超过打印页面的输出宽度时,Grid++Report 可以另起新页输出剩余的列,如果左边存在锁定列,锁定列可以在后面的新页中重复输出,这样可以保证关键数据列在每一页都有输出。仔细体会 Grid++Report 提供的多种打印适应策略,选用最合适的方式。Grid++Report 的多种打印适应策略为开发动态报表提供了很好的支持。 问:怎样实现报表本页小计功能? 答:定义一个报表分组,将本分组定义为页分组,在本分组的分组头与分组尾上定义统计。页分组就是在每页产生一个分组项,在每页的上端与下端都会分别显示页分组的分组头与分组尾,页分组不用定义分组依据字段。 报表运行 问:怎样与数据库建立连接? 答:如果在设计报表时指定了数据集的数据源连接串与查询 SQL 语句,Grid++Report 采用拉模式直接从数据源取得报表数据,Grid++Report 利用 OLE DB 从数据源取数,OLE DB 提供了广泛的数据源操作能力。如果 Grid++Report 的数据来源采用推模式,即 Grid++Report 不直接与数据库建立连接,各种编程语言/平台都提供了很好的数据库连接方式,并且易于操作,应用程序在报表主对象(IGridppReport)的 FetchRecord 事件中将数据传入,例子程序提供了各种编程语言填入数据的通用方法,对C++Builder 和 Delphi 还进行了专门的包装,直接关联 TDataSet 对象也可以将 TDataSet 对象中的数据传给报表。 问:打印时能否对打印纸张进行自适应?支持表格的折行打印吗? 答:Grid++Report 在打印时采用多种适应策略,通过设置明细网格(IGRDetailGrid)的‘打印策略(PrintAdaptMethod)’属性指定打印策略。(1)丢弃:按设计时列的宽度输出,超出范围的内容不显示。(2)绕行:按设计时列的宽度输出,如果在当前行不能完整输出,则另起新行进行输出。(3)缩放适应:对所有列的输出宽度进行按比例地缩放,使总宽度等于页面的输出宽度。(4)缩小适应:如果列的总宽度小于页面的输出宽度,对所有列的输出宽度进行按比例地缩小,使总宽度等于页面的输出宽度。(5)横向分页:超范围的列在新页中输出。(6)横向分页并重复锁定列。 问:如何改变缺省打印预览窗口的窗口标题? 答:改变报表主对象的‘标题(Title)’属性即可。 问:利用集合对象的编程接口取子对象的接口引用,但不是自己期望的结果。 答:Grid++Report中所有集合对象的下标索引都是从 1 开始,另按对象的名称查找对象的接口引用时,名称字符是不区分大小写的。 问:怎样在运行时控制报表中各个对象的可见性?即怎样在运行时显示或隐藏对象? 答:在报表主对象(GridppReport)的 SectionFormat 事件中设定相应报表子对象的可见(Visible)属性即可。 问:报表主对象重新载入数据,设计器中为什么没有反映新载入的数据? 答:应调用 IGRDesigner 的 Reload 方法。 问:怎样实现不进入打印预览界面,直接将报表打印出来?