基本概念

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

线性表中我们把数据元素叫元素,树中将数据元素叫结点,在图中的数据元素,我们则称之为顶点(Vertex)。

图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的


无向边(Edge):若顶点V1到V2之间的边没有方向,则称这条边为无向边。(V1,V2)=(V2,V1)。

无向图(Undirected graphs):图中任意两个顶点之间的边都是无向边。

有向边:若从顶点V1到V2的边有方向,则称这条边为有向边,也称弧(Arc)。用<V1,V2>表示,V1为弧尾(Tail),V2为弧头(Head)。<V1,V2> ≠ <V2,V1>。

有向图(Directed graphs):图中任意两个顶点之间的边都是有向边。

注意:无向边用“()”,而有向边用“< >”表示。

权(Weight):与图的边或弧相关的数。

网(Network):带权的图。如下图,此图的权就是两地的距离。

在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。下面两个就不是简单图。

在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n×(n-1)/2条边

在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n×(n-1)条边。


顶点v的:与v相关联的边的数目;

顶点v的出度:以v为起点有向边数;

顶点v的入度:以v为终点有向边数。


在无向图G中,如果从顶点v到顶点v’有路径,则称v和v’是连通的。如果对于图中任意两个顶点Vi、Vj∈E,Vi和Vj都是连通的,则称G是连通图(Connected Graph)。无向图中的极大连通子图称为连通分量

在有向图G中,如果对于每一对Vi、Vj∈V、Vi≠Vj,从Vi到Vj和从Vj到Vi都存在路径,则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量

路径的长度是路径上的边或弧的数目。

第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。两个图的粗线都构成环,左侧的环因第一个顶点和最后一个顶点都是B,且C、D、A没有重复出现,因此是一个简单环。而右侧的环,由于顶点C的重复,它就不是简单环了。

邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。


邻接表

我们把这种数组与链表相结合的存储方法称为邻接表(Adjacency List)。

边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成。

创建图的代码实现

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package com.nanzx.graph;

import java.util.ArrayList;
import java.util.Arrays;

public class Graph {

private ArrayList<String> vertexList;// 顶点集合
private int[][] edges;// 图对应的邻接矩阵
private int numOfEdges;// 边的数目

public static void main(String[] args) {

String Vertexs[] = { "A", "B", "C", "D", "E" };

// 创建图对象
Graph graph = new Graph(Vertexs.length);
// 循环的添加顶点
for (String vertex : Vertexs) {
graph.insertVertex(vertex);
}

// 添加边
// A-B A-C B-C B-D B-E
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);

// 显示一把邻结矩阵
graph.showGraph();
}

// 构造器
public Graph(int n) {
vertexList = new ArrayList<String>();
edges = new int[n][n];
numOfEdges = 0;
}

// 插入顶点
public void insertVertex(String vertex) {
vertexList.add(vertex);
}

// 添加边
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}

// 图中常用的方法
// 返回顶点的个数
public int getNumOfVertex() {
return vertexList.size();
}

// 显示图对应的矩阵
public void showGraph() {
// System.err.println(Arrays.deepToString(edges));
for (int[] e : edges) {
System.err.println(Arrays.toString(e));
}
}

// 得到边的数目
public int getNumOfEdges() {
return numOfEdges;
}

// 返回i(下标)对应的数据顶点 0->"A" 1->"B" 2->"C"
public String getValueByIndex(int i) {
return vertexList.get(i);
}

// 返回v1和v2的权值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
}

运行结果:

[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package com.nanzx.graph;

import java.util.ArrayList;
import java.util.Arrays;

public class Graph {

private ArrayList<String> vertexList;// 顶点集合
private int[][] edges;// 图对应的邻接矩阵
private boolean[] isVisited;// 记录某个顶点是否被访问

public static void main(String[] args) {

String Vertexs[] = { "1", "2", "3", "4", "5", "6", "7", "8" };

// 创建图对象
Graph graph = new Graph(Vertexs.length);
// 循环的添加顶点
for (String vertex : Vertexs) {
graph.insertVertex(vertex);
}
// 更新边的关系
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);
graph.insertEdge(3, 7, 1);
graph.insertEdge(4, 7, 1);
graph.insertEdge(2, 5, 1);
graph.insertEdge(2, 6, 1);
graph.insertEdge(5, 6, 1);

// 显示一把邻结矩阵
graph.showGraph();

System.out.println("深度遍历");
graph.dfs(0); // [1->2->4->8->5->3->6->7]
}

// 构造器
public Graph(int n) {
vertexList = new ArrayList<String>();
edges = new int[n][n];
isVisited = new boolean[n];
}

// 插入顶点
public void insertVertex(String vertex) {
vertexList.add(vertex);
}

// 添加边
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
}

// 深度优先遍历
public void dfs(int i) {
System.out.print(vertexList.get(i) + "->");
isVisited[i] = true;
for (int j = i + 1; j < vertexList.size(); j++) {
if (edges[i][j] > 0 && isVisited[j] == false) {
dfs(j);
}
}
}

// 显示图对应的矩阵
public void showGraph() {
for (int[] e : edges) {
System.out.println(Arrays.toString(e));
}
}
}

运行结果:

[0, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 1, 1, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 0]
深度遍历
1->2->4->8->5->3->6->7->

算法思路:

  1. 创建一个队列,用来存放每一层的顶点。

  2. 从初始访问顶点开始访问,将其标记为已访问,同时将其入队。

  3. 只要队列不空,则重复以下操作:

    (1)队头顶点first出队。

    (2)依次检查first的所有邻接顶点,若该邻接顶点没有被访问过,则将该邻接顶点标记为已访问,同时将其入队。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package com.nanzx.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

private ArrayList<String> vertexList;// 顶点集合
private int[][] edges;// 图对应的邻接矩阵
private boolean[] isVisited;// 记录某个顶点是否被访问

public static void main(String[] args) {
String Vertexs[] = { "1", "2", "3", "4", "5", "6", "7", "8" };

// 创建图对象
Graph graph = new Graph(Vertexs.length);
// 循环的添加顶点
for (String vertex : Vertexs) {
graph.insertVertex(vertex);
}

// 更新边的关系
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);
graph.insertEdge(3, 7, 1);
graph.insertEdge(4, 7, 1);
graph.insertEdge(2, 5, 1);
graph.insertEdge(2, 6, 1);
graph.insertEdge(5, 6, 1);

// 显示一把邻结矩阵
graph.showGraph();

System.out.println("广度优先!");
graph.bfs(0); // [1->2->3->4->5->6->7->8]
}

// 构造器
public Graph(int n) {
vertexList = new ArrayList<String>();
edges = new int[n][n];
isVisited = new boolean[n];
}

// 插入顶点
public void insertVertex(String vertex) {
vertexList.add(vertex);
}

// 添加边
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
}

// 广度优先遍历
public void bfs(int i) {
LinkedList<Integer> queue = new LinkedList<Integer>();
isVisited[i] = true;
queue.addLast(i);
while (!queue.isEmpty()) {
int first = (Integer) queue.removeFirst();
System.out.print(vertexList.get(first) + "->");
for (int j = first + 1; j < vertexList.size(); j++) {
if (edges[first][j] > 0 && isVisited[j] == false) {
queue.addLast(j);
isVisited[j] = true;
}
}
}
}

// 显示图对应的矩阵
public void showGraph() {
for (int[] e : edges) {
System.out.println(Arrays.toString(e));
}
}
}

运行结果:

[0, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 1, 1, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 0]
广度优先!
1->2->3->4->5->6->7->8->

找了一篇思路图解不错的博客帮助理解:CSDN 图的广度优先搜索(BFS)和深度优先搜索(DFS)算法解析