图
基本概念
图（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);
}
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() {
for (int[] e : edges) {
System.err.println(Arrays.toString(e));
}
}
public int getNumOfEdges() {
return numOfEdges;
}
public String getValueByIndex(int i) {
return vertexList.get(i);
}
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]
深度优先遍历(Depth First Search)
基本思想：
从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
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);
}
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 = 0; 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->
广度优先遍历(Broad First Search)
算法思路：
创建一个队列，用来存放每一层的顶点。
从初始访问顶点开始访问，将其标记为已访问，同时将其入队。
只要队列不空，则重复以下操作：
(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);
}
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）算法解析
微信
支付宝