邻接表有向图(三)之 Java详解

时间:2022-08-11 04:21:23

前面分别介绍了邻接表有向图的C和C++实现,本文通过Java实现邻接表有向图。

目录
1. 邻接表有向图的介绍
2. 邻接表有向图的代码说明
3. 邻接表有向图的完整源码

转载请注明出处:http://www.cnblogs.com/skywang12345/

更多内容:数据结构与算法系列 目录

邻接表有向图的介绍

邻接表有向图是指通过邻接表表示的有向图。

邻接表有向图(三)之 Java详解

上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9条边。

上图右边的矩阵是G2在内存中的邻接表示意图。每一个顶点都包含一条链表,该链表记录了"该顶点所对应的出边的另一个顶点的序号"。例如,第1个顶点(顶点B)包含的链表所包含的节点的数据分别是"2,4,5";而这"2,4,5"分别对应"C,E,F"的序号,"C,E,F"都属于B的出边的另一个顶点。

邻接表有向图的代码说明

1. 基本定义

public class ListDG {
// 邻接表中表对应的链表的顶点
private class ENode {
int ivex; // 该边所指向的顶点的位置
ENode nextEdge; // 指向下一条弧的指针
} // 邻接表中表的顶点
private class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
}; private VNode[] mVexs; // 顶点数组 ...
}

(01) ListDG是邻接表对应的结构体。 mVexs则是保存顶点信息的一维数组。
(02) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据,而firstEdge是该顶点所包含链表的表头指针。
(03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引,而nextEdge是指向下一个节点的。

2. 创建矩阵

这里介绍提供了两个创建矩阵的方法。一个是用已知数据,另一个则需要用户手动输入数据

2.1 创建图(用已提供的矩阵)

/*
* 创建图(用已提供的矩阵)
*
* 参数说明:
* vexs -- 顶点数组
* edges -- 边数组
*/
public ListDG(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);
}
}

该函数的作用是创建一个邻接表有向图。实际上,该方法创建的有向图,就是上面的图G2。该函数的调用方法如下:

    char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char[][] edges = new char[][]{
{'A', 'B'},
{'B', 'C'},
{'B', 'E'},
{'B', 'F'},
{'C', 'E'},
{'D', 'C'},
{'E', 'B'},
{'E', 'D'},
{'F', 'G'}};
ListDG pG; pG = new ListDG(vexs, edges);

2.2 创建图(自己输入)

/*
* 创建图(自己输入数据)
*/
public ListDG() { // 输入"顶点数"和"边数"
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);
}
}

邻接表有向图的完整源码

点击查看:源代码

邻接表有向图(三)之 Java详解的更多相关文章

  1. 邻接表无向图&lpar;三&rpar;之 Java详解

    前面分别介绍了邻接表无向图的C和C++实现,本文通过Java实现邻接表无向图. 目录 1. 邻接表无向图的介绍 2. 邻接表无向图的代码说明 3. 邻接表无向图的完整源码 转载请注明出处:http:/ ...

  2. 邻接表有向图&lpar;二&rpar;之 C&plus;&plus;详解

    本章是通过C++实现邻接表有向图. 目录 1. 邻接表有向图的介绍 2. 邻接表有向图的代码说明 3. 邻接表有向图的完整源码 转载请注明出处:http://www.cnblogs.com/skywa ...

  3. 邻接矩阵有向图&lpar;三&rpar;之 Java详解

    前面分别介绍了邻接矩阵有向图的C和C++实现,本文通过Java实现邻接矩阵有向图. 目录 1. 邻接矩阵有向图的介绍 2. 邻接矩阵有向图的代码说明 3. 邻接矩阵有向图的完整源码 转载请注明出处:h ...

  4. Floyd算法&lpar;三&rpar;之 Java详解

    前面分别通过C和C++实现了弗洛伊德算法,本文介绍弗洛伊德算法的Java实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3. 弗洛伊德算法的代码说明 4. 弗洛伊德算法的源码 转载请注明 ...

  5. Prim算法&lpar;三&rpar;之 Java详解

    前面分别通过C和C++实现了普里姆,本文介绍普里姆的Java实现. 目录 1. 普里姆算法介绍 2. 普里姆算法图解 3. 普里姆算法的代码说明 4. 普里姆算法的源码 转载请注明出处:http:// ...

  6. Kruskal算法&lpar;三&rpar;之 Java详解

    前面分别通过C和C++实现了克鲁斯卡尔,本文介绍克鲁斯卡尔的Java实现. 目录 1. 最小生成树 2. 克鲁斯卡尔算法介绍 3. 克鲁斯卡尔算法图解 4. 克鲁斯卡尔算法分析 5. 克鲁斯卡尔算法的 ...

  7. 拓扑排序&lpar;三&rpar;之 Java详解

    前面分别介绍了拓扑排序的C和C++实现,本文通过Java实现拓扑排序. 目录 1. 拓扑排序介绍 2. 拓扑排序的算法图解 3. 拓扑排序的代码说明 4. 拓扑排序的完整源码和测试程序 转载请注明出处 ...

  8. 邻接表无向图&lpar;二&rpar;之 C&plus;&plus;详解

    本章是通过C++实现邻接表无向图. 目录 1. 邻接表无向图的介绍 2. 邻接表无向图的代码说明 3. 邻接表无向图的完整源码 转载请注明出处:http://www.cnblogs.com/skywa ...

  9. 邻接矩阵无向图&lpar;三&rpar;之 Java详解

    前面分别介绍了邻接矩阵无向图的C和C++实现,本文通过Java实现邻接矩阵无向图. 目录 1. 邻接矩阵无向图的介绍 2. 邻接矩阵无向图的代码说明 3. 邻接矩阵无向图的完整源码 转载请注明出处:h ...

随机推荐

  1. Windows 10 下mysql 安装后无法启动问题

    安装过程: 1. 官网下载5.15.7, http://dev.mysql.com/downloads/, 选择开源社区版:MySQL Community Server (GPL) 2. 我解压后放在 ...

  2. 关于checkbox最保险和最模棱两可的方法

    最保险的方法: 判断是否是选中的checkbox $('input:checked').length>0 要使checkbox呈现选中状态,最保险的方法,调用input.click()方法 最模 ...

  3. Android之多线程断点下载

    本文主要包含多线程下载的一些简单demo,包括三部分 java实现 android实现 XUtils开源库实现 注意下载添加网络权限与SD卡读写权限 java实现多线程下载 public class ...

  4. 【题解】【BST】【Leetcode】Unique Binary Search Trees

    Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For examp ...

  5. BZOJ 2038 &lbrack;2009国家集训队&rsqb;小Z的袜子 莫队

    2038: [2009国家集训队]小Z的袜子(hose) 题目连接: http://www.lydsy.com/JudgeOnline/problem.php?id=2038 Descriptionw ...

  6. VC杂记

    获得Combobox的状态:向ComboBox发送CB_GETDROPPEDSTATE消息. 格式化字串:char buff[10] ; sprintf(buff,"1+1=%d" ...

  7. Redis中的value包含中文显示的问题?

    linux 系统 redis不识别中文  如何显示中文 在Redis中存储的value值是中文“马拉斯加”Shell下get获取后展示的结果为:\xc2\xed\xc0\xad\xcb\xb9\xbc ...

  8. 【Ztree】前台展示多级菜单,后台配置方法

    第一步.前台HTML页面. <%@ Page Language="C#" AutoEventWireup="true" CodeBehind=" ...

  9. 探究JVM和GC

    1.Java堆中各代分布: 图1:Java堆中各代分布 Young:主要是用来存放新生的对象. Old:主要存放应用程序中生命周期长的内存对象. Permanent:是指内存的永久保存区域,主要存放C ...

  10. cannot update the cursor rep&comma;since it is read-only

    操作DBF文件,开发机器读写都OK,但部署到服务器上后报:cannot update the cursor rep,since it is read-only 网上寻找解决方案英文答案比较多,也没有给 ...