图论基础
1、图的定义
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
2、图的基本性质
线性表中我们把数据元素叫元素，树中将数据元素叫节点，在图中数据元素，则称之为顶点（Vertex）
线性表中可以没有数据元素，称为空表。树中可以没有节点，叫做空树。
线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的节点具有层次关系，而图中，任意两个顶点之间都有可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
3、图的基本概念
1.无向图
若顶点v1到v2之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（v¡, v𝚓）来表示。
如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）。
重要：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
1.png
2.有向图
用有序偶<v¡, vj>来表示，vi称为弧尾（Tail），Vj称为弧头（Head）。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图
2.png
3.图的权
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权
3.png
4.连通图
在无向图 G 中，如果从顶点 v 到顶点 v'有路径，则称 v和v'是连通的。
如果对于图中任意两个顶点v¡、vj（E， vi和vj都是连通的，则称 G 是连通图（Connected Graphs）。
4.png
5.度
无向图顶点的边数叫度，有向图顶点的边数叫出度和入度
5.png
4、图的数据存储结构
-
邻接矩阵：图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。有以下性质表示：
1.无向图， 2.有向图， 3.带权有向图， 4.邻接矩阵的问题
-
邻接表
1.无向图， 2.有向图， 3.带权
5、图的遍历
-
深度优先遍历（Depth Firsh Search)。
遍历规则：不断地沿着顶点的深度方向遍历。顶点的深度方向是指它的邻接点方向。
-
广度优先遍历（Breadth First Search）
1.先访问完当前顶点的所有邻接点。（应该看得出广度的意思）
2.先访问顶点的邻接点先于后访问顶点的邻接点被访问。
6、代码实现
import java.util.LinkedList;
/**
* author: bobo
* create time: 2018/12/22 10:24 PM
* email: jqbo84@163.com
*/
public class Graph {
//顶点集合
private int[] vertices;
//图的边的信息
private int[][] matrix;
private int verticesSize;
public static final int MAX_WEIGHT = Integer.MAX_VALUE;
private boolean[] isVisited;
public Graph() {
}
public Graph(int verticesSize) {
this.verticesSize = verticesSize;
this.vertices = new int[verticesSize];
this.matrix = new int[verticesSize][verticesSize];
this.isVisited = new boolean[verticesSize];
for (int i = 0; i < verticesSize; i++) {
vertices[i] = i;
}
}
/**
* 计算V1到V2的权度（路径长度）
*/
public int getWeight(int v1, int v2) {
int weight = matrix[v1][v2];
return (weight == 0 ? 0 : (weight == MAX_WEIGHT ? -1 : weight));
}
/**
* 获取顶点
*
* @return
*/
public int[] getVertices() {
return vertices;
}
/**
* 获取图的边的信息数组
* @return
*/
public int[][] getMatrix() {
return matrix;
}
/**
* 计算出度, 横向计算
*/
public int getOutDegree(int v) {
int count = 0;
for (int i = 0; i < verticesSize; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != MAX_WEIGHT) {
count += 1;
}
}
return count;
}
/**
* 计算入度， 纵向计算
*/
public int getInDegree(int v) {
int count = 0;
for (int i = 0; i < verticesSize; i++) {
if (matrix[i][v] != 0 && matrix[i][v] != MAX_WEIGHT) {
count += 1;
}
}
return count;
}
/**
* 获取第一个邻接点
*/
public int getFirstNeightBor(int v){
for (int i = 0; i < verticesSize; i++) {
if(matrix[v][i] > 0 && matrix[v][i] != MAX_WEIGHT){
return i;
}
}
return -1;
}
/**
* 获取到顶点 v 的邻接点的index到下一个邻接点
*/
public int getNextNeightBor(int v, int index){
for (int i = index + 1; i < verticesSize; i++) {
if(matrix[v][i] > 0 && matrix[v][i] != MAX_WEIGHT){
return i;
}
}
return -1;
}
/**
* 深度优先(很像二叉树的前序排序算法)
*/
public void dfs(){
for (int i = 0; i < verticesSize; i++) {
if(!isVisited[i]){
System.out.println("Visited Vertice = " + i);
dfs(i);
}
}
}
public void dfs(int i){
isVisited[i] = true;
int v = getFirstNeightBor(i);
while (v != -1) {
if(!isVisited[v]){
System.out.println("Visited Vertice = " + v);
dfs(v);
}
v = getNextNeightBor(i, v);
}
}
/**
* 广度优先（有点像二叉树的第四种排序算法）
*/
public void bfs(){
for (int i = 0; i < verticesSize; i++) {
isVisited[i] = false;
}
for (int i = 0; i < verticesSize; i++) {
if(!isVisited[i]){
isVisited[i] = true;
System.out.println("visited vertice = " + i);
bfs(i);
}
}
}
public void bfs(int i){
LinkedList<Integer> queue = new LinkedList<>();
//找到第一个邻接点
int fn = getFirstNeightBor(i);
if(fn == -1){
return;
}
if(!isVisited[fn]){
isVisited[fn] = true;
System.out.println("visited vertice = " + fn);
queue.offer(fn);
}
//开始把后面的邻接点都入队
int next = getNextNeightBor(i, fn);
while (next != -1){
if(!isVisited[next]){
isVisited[next] = true;
System.out.println("visited vertice = " + next);
queue.offer(next);
}
next = getNextNeightBor(i, next);
}
//从队列中取出来一个，重复之前的操作
while (!queue.isEmpty()){
int p = queue.poll();
bfs(p);
}
}
}
7、测试
@Test
public void testGraph(){
// Graph graph=new Graph(5);
// int[] a0=new int[]{0,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,6};
// int[] a1=new int[]{9,0,3,MAX_WEIGHT,MAX_WEIGHT};
// int[] a2=new int[]{2,MAX_WEIGHT,0,5,MAX_WEIGHT};
// int[] a3=new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0,1};
// int[] a4=new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0};
// graph.getMatrix()[0]=a0;
// graph.getMatrix()[1]=a1;
// graph.getMatrix()[2]=a2;
// graph.getMatrix()[3]=a3;
// graph.getMatrix()[4]=a4;
// System.out.println(graph.getInDegree(2));
// System.out.println(graph.getOutDegree(2));
Graph graph = new Graph(5);
int[] v0 = new int[]{0, 1, 1, MAX_WEIGHT, MAX_WEIGHT};
int[] v1 = new int[]{MAX_WEIGHT, 0, MAX_WEIGHT, 1, MAX_WEIGHT};
int[] v2 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT, MAX_WEIGHT};
int[] v3 = new int[]{1, MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT};
int[] v4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 1, MAX_WEIGHT, 0};
graph.getMatrix()[0] = v0;
graph.getMatrix()[1] = v1;
graph.getMatrix()[2] = v2;
graph.getMatrix()[3] = v3;
graph.getMatrix()[4] = v4;
graph.dfs();
System.out.println("--------------------------------");
graph.bfs();
}
结果：
--------------- 入度出度 -----------------
1
2
--------------- 深度优先 -----------------
Visited Vertice = 0
Visited Vertice = 1
Visited Vertice = 3
Visited Vertice = 2
Visited Vertice = 4
--------------- 广度优先 -----------------
visited vertice = 0
visited vertice = 1
visited vertice = 2
visited vertice = 3
visited vertice = 4
8、附测试图
1.入度出度测试图：
7.png
2.深度优先、广度优先测试图：
6.png
