在计算机科学中，图（英语：graph）是一种抽象数据类型，用于实现数学中图论的无向图和有向图的概念。
图的数据结构包含一个有限（可能是可变的）的集合作为节点集合，以及一个无序对（对应无向图）或有序对（对应有向图）的集合作为边（有向图中也称作弧）的集合。节点可以是图结构的一部分，也可以是用整数下标或引用表示的外部实体。
图的数据结构还可能包含和每条边相关联的数值（edge value），例如一个标号或一个数值（即权重，weight；表示花费、容量、长度等）。
基本概念
图是由顶点和边组成的：(可以无边，但至少包含一个顶点)
- 一组顶点：通常用 V(vertex) 表示顶点集合
- 一组边：通常用 E(edge) 表示边的集合
图可以分为有向图和无向图，在图中：
- (v, w) 表示无向边，即 v 和 w 是互通的
- <v, w> 表示有向边，该边始于 v，终于 w
图可以分为有权图和无权图：
- 有权图：每条边具有一定的权重(weight)，通常是一个数字
- 无权图：每条边均没有权重，也可以理解为权为 1
图又可以分为连通图和非连通图：
- 连通图：所有的点都有路径相连
- 非连通图：存在某两个点没有路径相连
图中的顶点有度的概念：
- 度(Degree)：所有与它连接点的个数之和
- 入度(Indegree)：存在于有向图中，所有接入该点的边数之和
- 出度(Outdegree)：存在于有向图中，所有接出该点的边数之和
有向网，存在2个节点不同方向权不同的有向图。
操作
图数据结构G支持的基本操作通常包括：
- adjacent(G, x, y)：查看是否存在从节点x到y的边；
- neighbors(G, x)：列出所有从x出发的边的另一个顶点y；
- add_vertex(G, x)：如果不存在，将节点x添加进图；
- remove_vertex(G, x)：如果存在，从图中移除节点x；
- add_edge(G, x, y)：如果不存在，添加一条从节点x到y的边；
- remove_edge(G, x, y)：如果存在，从图中移除从节点x到y的边；
- get_vertex_value(G, x)：返回节点x上的值；
- set_vertex_value(G, x, v)：将节点x上的值赋为v。
如果该数据结构支持和边关联的数值，则通常也支持下列操作：
- get_edge_value(G, x, y)：返回边(x, y)上的值；
- set_edge_value(G, x, y, v)：将边(x, y)上的值赋为v。
图的常见数据结构
邻接表 adjacency list
节点存储为记录或对象，且为每个节点创建一个列表。这些列表可以按节点存储其余的信息；例如，若每条边也是一个对象，则将边存储到边起点的列表上，并将边的终点存储在边这个的对象本身。
无权图
1
2
3
4
|
// 数组表示顶点
char[] vexs;
// graph[i][j] 表示节点i有连接的点集合
int[][] graph;
|
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
|
public class Node {
int n;
String name;
boolean visited;
}
//
private HashMap<Node, LinkedList<Node>> adjacencyMap;
private boolean directed;
public void depthFirstSearch(Node node) {
node.visit();
System.out.print(node.name + " ");
LinkedList<Node> allNeighbors = adjacencyMap.get(node);
if (allNeighbors == null)
return;
for (Node neighbor : allNeighbors) {
if (!neighbor.isVisited())
depthFirstSearch(neighbor);
}
}
public class ListUDG {
private static int INF = Integer.MAX_VALUE;
// 邻接表中表对应的链表的顶点
private class ENode {
int ivex; // 该边所指向的顶点的位置
int weight; // 该边的权
ENode nextEdge; // 指向下一条弧的指针
}
// 邻接表中表的顶点
private class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
};
private int mEdgNum; // 边的数量
private VNode[] mVexs; // 顶点数组
/*
* 深度优先搜索遍历图的递归实现
*/
private void DFS(int i, boolean[] visited) {
ENode node;
visited[i] = true;
System.out.printf("%c ", mVexs[i].data);
node = mVexs[i].firstEdge;
while (node != null) {
if (!visited[node.ivex])
DFS(node.ivex, visited);
node = node.nextEdge;
}
}
/*
* 深度优先搜索遍历图
*/
public void DFS() {
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
// 初始化所有顶点都没有被访问
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("DFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i])
DFS(i, visited);
}
System.out.printf("\n");
}
}
|
邻接矩阵 adjacency matrix
一个二维矩阵，其中行与列分别表示边的起点和终点。顶点上的值存储在外部。矩阵中可以存储边的值。
1
2
3
4
5
6
7
|
public class MatrixUDG {
private int edgeNum; // 边的数量
private char[] vexs; // 顶点集合
private int[][] matrix; // 邻接矩阵
private static final int INF = Integer.MAX_VALUE; // 最大值
}
|
关联矩阵（英语：incidence matrix）
一个二维矩阵，行表示顶点，列表示边。矩阵中的数值用于标识顶点和边的关系（是起点、是终点、不在这条边上等）。
邻接表在稀疏图（英语：sparse graph）上比较有效率。邻接矩阵则常在图比较稠密的时候使用，判断标准一般为边的数量$|E|$接近于节点的数量的平方$|V|^2$；邻接矩阵也在查找两节点邻接情况较为频繁时使用。
其它表示和存储图的数据结构还包括链式前向星、十字链表、邻接多重表（英语：adjacency multilist）等。
图的遍历
图的遍历问题分为四类：
- 遍历完所有的边而不能有重复，即所谓“欧拉路径问题”（又名一笔画问题）；
- 遍历完所有的顶点而没有重复，即所谓“哈密顿路径问题”。
- 遍历完所有的边而可以有重复，即所谓“邮递员问题”；
- 遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。
对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。
第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。
算法
图的遍历方法有
1
2
3
4
5
6
7
8
9
10
|
int graph[][] = {{1,2,3},{4,5,6}}
int[][] graph = new int[2][3];
// 第二维的长度可以动态申请
int [][] graph3 = new int[5][];
for (int i = 0; i< graph3.length; i++){
graph3[i] = new int[i+1];
for (int j=0; j< graph3[i].length; j++){
graph3[i][j] = i+j;
}
}
|
附件