ListDG

本文我们用Java实现邻接表有向图的创建。

一. 邻接表有向图介绍

邻接表底层使用了一个数组+链表来存储图,数组用于存储图的顶点,链表存储两个顶点之间的关系。如下图所示
title

二.代码说明

1. 基本定义

这里定义还是和之前一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ListDG {

private VNode[] vNodes;

// 边节点
public class ENode{
// 边的索引
int index;
// 边的下一条边
ENode next;
}

// 顶点
public class VNode{
// 顶点存储的值
char data;
// 顶底相连的第一条边
ENode firstEdge;
}
}

2. 算法实现

这边只需要把创建边的方法稍作改动就可以了。

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
public ListDG(char[] vertexs, char[][] edges){

int v1 = vertexs.length;
vNodes = new VNode[v1];

// 创建顶点
for (int i = 0; i < vertexs.length; i++) {
VNode vNode = new VNode();
vNode.data = vertexs[i];
vNode.firstEdge = null;
vNodes[i] = vNode;
}

// 创建边
for (int i = 0; i < edges.length; i++) {

// 获取两条边对应的下标
int p1 = getPos(edges[i][0]);
int p2 = getPos(edges[i][1]);

ENode node1 = new ENode();
node1.index = p2;
if(vNodes[p1].firstEdge == null)
vNodes[p1].firstEdge = node1;
else
linkLast(vNodes[p1].firstEdge, node1);

}


}

方便大家学习,提供了源代码