摘要 图与树一样都属于非线性结构,又有点类似于广义表。图中各结点之间都可能具有逻辑关系,结点之间的关系是任意的,因此它是一种比线性表和树更为复杂的数据结构。图在科研和生活中有着非常广泛的应用,如生活中的最短路径问题,以及搜索引擎中深度和广度搜索问题。本文主要介绍图的存储结构定义,以及使用邻接矩阵表示的图的最短路径问题。

图的相关术语

  • 图:由有穷、非空点集合和边的集合组成,简称G(V,E)
  • 有向图与无向图:图中的边用弧表示,用弧连接的两个顶点有弧头和弧尾之分,这种图为有向图,连接顶点的边没有方向之分,该图称为无向图。
  • 有向完全图与无向完全图:有向图每两个顶点之间都有两条反向的弧相连表示两顶点互通,弧的数目为n(n-1),改图为有向完全图;无向图中每两个顶点之间都有一条边相连,表示两顶点连通,边的数目为n(n-1)/2,该图为无向完全图。
  • 稠密图与稀疏图:图中边的数目很多的图为稠密图;图中边的数目相对顶点较少的图为稀疏图。
  • 出度与入度:对于有向图,出度表示,以该顶点为弧尾的并与该顶点相连的弧的数目;入度表示,以该顶点为弧头的并与该顶点相连的弧的数目。
  • 环与简单路径:图中有一条路径,其中第一个顶点与最后一个顶点相同,该路径为环;路径序列中不存在重复顶点的称为简单路径。
  • 连通图与强连通图:无向图中任意两个顶点都有路径相通,则称该图是连通的;有向图中任意两个顶点之间都有路径相通,则称该有向图为强连通图。
  • 连通分量与强连通分量:分别针对无向图与有向图而言,无向图中的极大连通子图为连通分量;有向图中的极大强连通子图为强连通分量。
  • 生成树:一个连通图的生成树是一个极小连通子图,它包含图中全部顶点,但只有n-1条边。
    网:带权的图。

图的存储结构

下面这幅图是本文介绍图的存储及最短路径所使用的图,实际上它是有向网。

graph

邻接矩阵

邻接矩阵是一个二维数组,对于无向图是对称矩阵,矩阵中用0表示i,j两点之间没有边,1表示i,j两点之间有边。以上面的有向网为例,则邻接矩阵中,存储的不再是0或1而是两点边的权值,如果没有边则赋值为无穷大。

除了二维数组保存边的权值外,图中还需要维护一个整型变量保存顶点个数,以及Vertex类型的数组,Vertex类型保存顶点信息,主要是顶点编号以及顶点名称。

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
class SeqGraph{
public static final int INFINITY = Integer.MAX_VALUE;

private class Vertex{

private int vIndex;
private char data;

public Vertex(){

}

public Vertex(int vIndex, char data){
this.vIndex = vIndex;
this.data = data;
}
}

private int vexNum = 0;
private Vertex vex[] = null;
private int adj[][] = null;

public SeqGraph(){

}

public SeqGraph(int vexNum){
this.vexNum = vexNum;
this.vex = new Vertex[vexNum];
this.adj = new int[vexNum][vexNum];
}
}

构造邻接矩阵,分为初始化邻接矩阵和静态构造两步,这里也可以手动输入边相连的顶点编号以及权值,来建立邻接矩阵。静态构造的示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void initAdj(){
for(int i=0; i<vexNum; i++){
for(int j=0; j<vexNum; j++){
adj[i][j] = INFINITY;
}
}
}

public void staticCreate(){
for(int i=0; i<vexNum; i++){
vex[i] = new Vertex(i, (char)('A'+i));
}
adj[0][1] = 5;
adj[0][3] = 7;
adj[1][2] = 4;
adj[2][0] = 8;
adj[2][5] = 9;
adj[3][2] = 5;
adj[3][5] = 6;
adj[4][3] = 5;
adj[5][0] = 3;
adj[5][4] = 1;
}

然后在构造函数里面依次调用上述两个函数,这里静态构造的邻接矩阵是根据上面的有向网的形态构造的,试着输出看一下,其中,对于无穷大的数据,我们输出0来表示。

1
2
3
4
5
6
7
8
9
10
11
12
public void printGraph(){
for(int i=0; i<vexNum; i++){
for(int j=0; j<vexNum; j++){
if(adj[i][j] == INFINITY){
System.out.print(0+" ");
}else{
System.out.print(adj[i][j]+" ");
}
}
System.out.println();
}
}

0 5 0 7 0 0
0 0 4 0 0 0
8 0 0 0 0 9
0 0 5 0 0 6
0 0 0 5 0 0
3 0 0 0 1 0

邻接表

邻接表,相当于链表,我们为每一个顶点维护一个单链表,保存以该顶点为出度的弧相连所有其它顶点。

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
class LinkGraph{
private class Vertex{
private int vIndex;
private char data;
private Vertex next;

public Vertex(){

}

public Vertex(int vIndex, char data, Vertex next){
this.vIndex = vIndex;
this.data = data;
this.next = next;
}
}


private int vexNum = 0;
private Vertex vex[] = null;

public LinkGraph(){

}

public LinkGraph(int vexNum){
this.vexNum = vexNum;
this.vex = new Vertex[vexNum];
}
}

其中的顶点类型与以上邻接矩阵稍有区别的是,每一个顶点都包含下一个出度顶点的信息。以手动输入来动态创建邻接表,如下所示:

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
public void create(){
Scanner sc = new Scanner(System.in);
System.out.println("please input the every arc of graph with \"tIndex hIndex\"");
System.out.println("input 0 0 for end!");

int i = 0;
int j = 0;

while (((i = sc.nextInt()) != 0) && ((j = sc.nextInt()) != 0)){
int tIndex = i-1;
int hIndex = j-1;

Vertex hVertex = new Vertex(hIndex, (char)('A'+hIndex), null);

if(vex[tIndex] == null){
vex[tIndex] = new Vertex(tIndex, (char)('A'+tIndex), hVertex);
}
else{
Vertex pVertex = vex[tIndex];
while((pVertex.next != null) && (pVertex.next.vIndex < hVertex.vIndex)){
pVertex = pVertex.next;
}
hVertex.next = pVertex.next;
pVertex.next = hVertex;
}
}
}

依次输入如下信息:

1 2
1 4
2 3
3 1
3 6
4 3
5 4
6 5
6 1
0 0

用如下函数输出邻接表表示的图的信息:

1
2
3
4
5
6
7
8
9
10
public void printGraph(){
for(int i=0; i<vexNum; i++){
Vertex vertex = vex[i];
while(vertex != null){
System.out.print(vertex.data + "--->");
vertex = vertex.next;
}
System.out.println();
}
}

输出信息如下图所示:

linkgraph

十字链表

邻接表只包含了出度信息,为了寻找入度信息,必须遍历整个表,耗费的时间是相当可观的。为了解决寻找入度信息困难的问题,我们可以额外建立一个逆连接表。

十字链表则可以看成是邻接表和逆邻接表的结合体。顶点信息中除了保存下一个出度信息外,还要保存下一个入度信息。十字链表的结构定义如下:

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
class CrossGraph{

private class Vertex{
private int vIndex;
private char data;
private Vertex nextOut;
private Vertex nextIn;

public Vertex(){

}

public Vertex(int vIndex, char data, Vertex nextOut, Vertex nextIn){
this.vIndex = vIndex;
this.data = data;
this.nextOut = nextOut;
this.nextIn = nextIn;
}
}

private int vexNum = 0;
private Vertex inVex[] = null;
private Vertex outVex[] = null;

public CrossGraph(){

}

public CrossGraph(int vexNum){
this.vexNum = vexNum;
this.inVex = new Vertex[vexNum];
this.outVex = new Vertex[vexNum];
}
}

与邻接表类似,通过手动输入方式建立十字链表的函数如下:

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
public void create(){
Scanner sc = new Scanner(System.in);
System.out.println("please input the every arc of graph with \"tIndex hIndex\"");
System.out.println("input 0 0 for end!");

int i = 0;
int j = 0;

while (((i = sc.nextInt()) != 0) && ((j = sc.nextInt()) != 0)){
int tIndex = i-1;
int hIndex = j-1;

Vertex hVertex = new Vertex(hIndex, (char)(hIndex+'A'), null, null);
Vertex tVertex = new Vertex(tIndex, (char)(tIndex+'A'), null, null);
hVertex.nextIn = tVertex;
tVertex.nextOut = hVertex;

if(this.outVex[tIndex] == null){
outVex[tIndex] = tVertex;
}else{
Vertex pVertex = outVex[tIndex];
while((pVertex.nextOut != null) && (pVertex.nextOut.vIndex < hVertex.vIndex)){
pVertex = pVertex.nextOut;
}
hVertex.nextOut = pVertex.nextOut;
pVertex.nextOut = hVertex;
}

if(this.inVex[hIndex] == null){
inVex[hIndex] = hVertex;
}else{
Vertex pVertex = inVex[hIndex];
while((pVertex.nextIn != null) && (pVertex.nextIn.vIndex < tVertex.vIndex)){
pVertex = pVertex.nextIn;
}
tVertex.nextIn = pVertex.nextIn;
pVertex.nextIn = tVertex;
}
}
}

输入与建立邻接表时一样的数据,输出十字链表的数据如下图所示:

crossgraph

显然邻接表和十字链表都是有利于有向图的存储结构,与十字链表对应的无向图的存储结构为邻接多重表,这里就不再介绍了。

图的遍历

图的遍历分为深度优先遍历和广度优先遍历。深度优先遍历类似于树的先序遍历,而广度优先遍历则类似于树的层序遍历。

深度优先遍历:选择图中某个顶点,依次遍历该顶点的第一个邻接点,然后再依次遍历该邻接点的第一个邻接点,直到图中所有顶点都遍历完为止。

广度优先遍历:选择图中某个顶点,依次遍历该顶点的所有邻接顶点,并保证先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直到图中所有顶点遍历完毕。

为了在遍历过程中区分顶点是否已被访问,需要设置一个访问标志数组visited[],大小为顶点数目,初始化为所有顶点都未被访问,下面以邻接矩阵表示的有向网的结构,分别以深度优先遍历和广度优先遍历方式访问该图。

显然深度遍历图是一个递归的过程,我们先用递归实现,后用栈来模拟实现递归深度遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void DFS(int i){
visited[i] = true;
System.out.print(vex[i].data+"--->");
for(int j=0; j<vexNum; j++){
if(!visited[j] && adj[i][j] != INFINITY){
DFS(j);
}
}
}

public void DFSTraverse(int i){
this.initVisit();
for(int i=0; i<vexNum; i++){
if(!visited[i]){
DFS(i);
}
}
}

下面用栈来模拟递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void nonRecDFSTraverse(){
this.initVisit();
Stack<Integer> stack = new Stack<Integer>();
int i=0, j;
while(!visited[i] || stack.size() > 0){
while(!visited[i]){
visited[i] = true;
System.out.print(vex[i].data+"--->");
stack.push(i);
j = 0;
while(j < vexNum){
if(adj[i][j] != INFINITY && !visited[j]){
i = j;
break;
}
j++;
}
}
if(stack.size() >0){
i = stack.pop();
}
}
}

广度优先遍历,由于要保证先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,因此队列是很好的结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void BFSTraverse(){
this.initVisit();
LinkedList<Integer> queue = new LinkedList<Integer>();
for (int i=0; i<vexNum; i++) {
if(!visited[i]){
visited[i] = true;
System.out.print(vex[i].data+"--->");
queue.add(i);
while(queue.size() > 0){
i = queue.poll();
for(int j=0; j<vexNum; j++) {
if(adj[i][j] != INFINITY && !visited[j]){
visited[j] = true;
System.out.print(vex[j].data+"--->");
queue.add(j);
}
}
}
}
}
}

最短路径问题

以有向网为例,来讨论最短路径问题,其中分为单源最短路径和所有顶点对之间的最短路径问题,其中Dijkstra算法和Floyd算法是最为典型的代表。

Dijkstra算法目的是为解决单源最短路径,即求图中某一顶点到图中其它顶点间的最短路径,Dijkstra算法利用贪心策略,求解最短路径,其中每次求解,都是求当前路径最短的顶点,然后利用该顶点去更新其它顶点最短路径,因此属于最短路径长度递增的顺序,求得所有顶点最短路径。

参数说明:Dijkstra算法需要维护一个已求得最短路径的顶点集合以及到每个顶点的最短路径的长度数组。每求得一个顶点的最短路径,就将该顶点加入已求得最短路径的顶点集合。

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
public int[] dijkstraShortestPath(int v0){
boolean s[] = new boolean[vexNum];
int dist[] = new int[vexNum];

for(int i=0; i<vexNum; i++){
s[i] = false;
dist[i] = adj[v0][i];
}

s[v0] = true;
dist[v0] = 0;

for(int j=1; j<vexNum; j++){
int u = 0;
int minDist = INFINITY;
for(int k=0; k<vexNum; k++){
if(s[k] == false && (dist[k] < minDist)){
u = k;
minDist = dist[k];
}
}

s[u] = true;
dist[u] = minDist;

for(int w=0; w<vexNum; w++){
int midDist = (adj[u][w] == INFINITY ? INFINITY : dist[u]+adj[u][w]);
if(s[w] == false && dist[w] > midDist){
dist[w] = midDist;
}
}
}
return dist;
}

Floyd算法解决图中所有顶点对之间的最短路径,其求解策略属于动态规划的范畴,即当前状态下,D(i,j,k)为结点vi到vj的以结点vk为中间结点的最短路径长度。那么

  • 若最短路径经过结点vk,则D(i,j,k)=D(i,j,k-1)+D(k,j,k-1);
  • 若最短路径不经过结点vk,则D(i,j,k) = D(i,j,k-1).

所以求vi到vj的最短路径可以表示为

$$D(i,j,k)=min(D(i,k,k-1)+D(k,j,k-1),D(i,j,k-1))$$

Floyd算法为求得所有顶点之间的最短路径,需要经过N次更新,N为顶点数目。Floyd算法实现需要设置二维数组,保存每对顶点之间的最短路径长度,初始化即为邻接矩阵,下面是Floyd算法的实现代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[][] floydShortestPath(){
int dist[][] = new int[vexNum][vexNum];
for(int i=0; i<vexNum; i++){
for(int j=0; j<vexNum; j++){
dist[i][j] = adj[i][j];
}
}

for(int k=0; k<vexNum; k++){
for(int i=0; i<vexNum; i++){
for(int j=0; j<vexNum; j++){
int midDist = ((dist[i][k] == INFINITY || dist[k][j] == INFINITY) ? INFINITY : (dist[i][k] + dist[k][j]));
if(dist[i][j] > midDist){
dist[i][j] = midDist;
}
}
}
}
return dist;
}

Floyd算法的时间复杂度为O(n^3),Dijkstra算法主要是求单源最短路径,也可以对Dijkstra循环调用N次已求得所有顶点对之间的最短路径,因此,二者求出所有顶点的最短路径的时间复杂度都为O(n^3)。