前面分别介绍了邻接表有向图的C和C++实现,本文通过Java实现邻接表有向图。
目录
1. 邻接表有向图的介绍
2. 邻接表有向图的代码说明
3. 邻接表有向图的完整源码转载请注明出处:http://www.cnblogs.com/skywang12345/
更多内容:数据结构与算法系列 目录
邻接表有向图的介绍
邻接表有向图是指通过邻接表表示的有向图。
上面的图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详解的更多相关文章
-
邻接表无向图(三)之 Java详解
前面分别介绍了邻接表无向图的C和C++实现,本文通过Java实现邻接表无向图. 目录 1. 邻接表无向图的介绍 2. 邻接表无向图的代码说明 3. 邻接表无向图的完整源码 转载请注明出处:http:/ ...
-
邻接表有向图(二)之 C++详解
本章是通过C++实现邻接表有向图. 目录 1. 邻接表有向图的介绍 2. 邻接表有向图的代码说明 3. 邻接表有向图的完整源码 转载请注明出处:http://www.cnblogs.com/skywa ...
-
邻接矩阵有向图(三)之 Java详解
前面分别介绍了邻接矩阵有向图的C和C++实现,本文通过Java实现邻接矩阵有向图. 目录 1. 邻接矩阵有向图的介绍 2. 邻接矩阵有向图的代码说明 3. 邻接矩阵有向图的完整源码 转载请注明出处:h ...
-
Floyd算法(三)之 Java详解
前面分别通过C和C++实现了弗洛伊德算法,本文介绍弗洛伊德算法的Java实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3. 弗洛伊德算法的代码说明 4. 弗洛伊德算法的源码 转载请注明 ...
-
Prim算法(三)之 Java详解
前面分别通过C和C++实现了普里姆,本文介绍普里姆的Java实现. 目录 1. 普里姆算法介绍 2. 普里姆算法图解 3. 普里姆算法的代码说明 4. 普里姆算法的源码 转载请注明出处:http:// ...
-
Kruskal算法(三)之 Java详解
前面分别通过C和C++实现了克鲁斯卡尔,本文介绍克鲁斯卡尔的Java实现. 目录 1. 最小生成树 2. 克鲁斯卡尔算法介绍 3. 克鲁斯卡尔算法图解 4. 克鲁斯卡尔算法分析 5. 克鲁斯卡尔算法的 ...
-
拓扑排序(三)之 Java详解
前面分别介绍了拓扑排序的C和C++实现,本文通过Java实现拓扑排序. 目录 1. 拓扑排序介绍 2. 拓扑排序的算法图解 3. 拓扑排序的代码说明 4. 拓扑排序的完整源码和测试程序 转载请注明出处 ...
-
邻接表无向图(二)之 C++详解
本章是通过C++实现邻接表无向图. 目录 1. 邻接表无向图的介绍 2. 邻接表无向图的代码说明 3. 邻接表无向图的完整源码 转载请注明出处:http://www.cnblogs.com/skywa ...
-
邻接矩阵无向图(三)之 Java详解
前面分别介绍了邻接矩阵无向图的C和C++实现,本文通过Java实现邻接矩阵无向图. 目录 1. 邻接矩阵无向图的介绍 2. 邻接矩阵无向图的代码说明 3. 邻接矩阵无向图的完整源码 转载请注明出处:h ...
随机推荐
-
Windows 10 下mysql 安装后无法启动问题
安装过程: 1. 官网下载5.15.7, http://dev.mysql.com/downloads/, 选择开源社区版:MySQL Community Server (GPL) 2. 我解压后放在 ...
-
关于checkbox最保险和最模棱两可的方法
最保险的方法: 判断是否是选中的checkbox $('input:checked').length>0 要使checkbox呈现选中状态,最保险的方法,调用input.click()方法 最模 ...
-
Android之多线程断点下载
本文主要包含多线程下载的一些简单demo,包括三部分 java实现 android实现 XUtils开源库实现 注意下载添加网络权限与SD卡读写权限 java实现多线程下载 public class ...
-
【题解】【BST】【Leetcode】Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For examp ...
-
BZOJ 2038 [2009国家集训队]小Z的袜子 莫队
2038: [2009国家集训队]小Z的袜子(hose) 题目连接: http://www.lydsy.com/JudgeOnline/problem.php?id=2038 Descriptionw ...
-
VC杂记
获得Combobox的状态:向ComboBox发送CB_GETDROPPEDSTATE消息. 格式化字串:char buff[10] ; sprintf(buff,"1+1=%d" ...
-
Redis中的value包含中文显示的问题?
linux 系统 redis不识别中文 如何显示中文 在Redis中存储的value值是中文“马拉斯加”Shell下get获取后展示的结果为:\xc2\xed\xc0\xad\xcb\xb9\xbc ...
-
【Ztree】前台展示多级菜单,后台配置方法
第一步.前台HTML页面. <%@ Page Language="C#" AutoEventWireup="true" CodeBehind=" ...
-
探究JVM和GC
1.Java堆中各代分布: 图1:Java堆中各代分布 Young:主要是用来存放新生的对象. Old:主要存放应用程序中生命周期长的内存对象. Permanent:是指内存的永久保存区域,主要存放C ...
-
cannot update the cursor rep,since it is read-only
操作DBF文件,开发机器读写都OK,但部署到服务器上后报:cannot update the cursor rep,since it is read-only 网上寻找解决方案英文答案比较多,也没有给 ...