图中的元素称为“顶点”,如果两个顶点是连通的,连通的线叫作“边”,两点之间的距离叫作“权”,对于无向边(AB顶点相连,则A可以到达B,B也可以到达A),顶点A的边数叫作“度”;有向边,顶点A的边数叫作出度(AB顶点相连,A可以到达B,但B不能到达A)和入度(AB顶点相连,A不能到达B,B能到达A)。 邻接矩阵的存储结构是用两个数组来表示,一个一维数组存储顶点,一个二维数据(矩阵)存储边的关系
代码表示如下:
/**
* 图论-邻接矩阵
*/
public static class Graph {
private int[] vertices; // 顶点
private int[][] matrix; // 图的节点的边
private int verticeSize; // 顶点的数量
public Graph(int verticeSize) {
this.verticeSize = verticeSize;
vertices = new int[verticeSize];
matrix = new int[verticeSize][verticeSize];
for(int i = 0; i < verticeSize; i++) {
vertices[i] = i;
}
}
}
实现一些基本方法:
/**
* 获取v1到v2的路径长度
*
* @param v1
* @param v2
* @return MAX:无穷大,即没有路径 0:本身
*/
public int getWeight(int v1, int v2) {
return matrix[v1][v2];
}
/**
* 获取顶点
*
* @return
*/
public int[] getVertices() {
return vertices;
}
/**
* 获取出度
*
* @param v
* @return
*/
public int getOutDegree(int v) {
int count = 0;
for (int i = 0; i < verticeSize; i++) {
//matrix[v][v]的一行中存放的数组为v到别的顶点的权
if (matrix[v][i] != 0 && matrix[v][i] != MAX) {
count++;
}
}
return count;
}
/**
* 获取入度
*
* @param v
* @return
*/
public int getInDegree(int v) {
int count = 0;
for (int i = 0; i < verticeSize; i++) {
//matrix[v][v]的一列中存放的为别的顶点到v的权
if (matrix[i][v] != 0 && matrix[i][v] != MAX) {
count++;
}
}
return count;
}
图的遍历: 1.深度优先遍历,和二叉树的深度优先遍历差不多
/**
* 获取v的第一个邻接点
*
* @param v
*/
private int getFirstNeightbor(int v) {
return getNeightbor(v, -1);
}
/**
* 获取index以后的v的邻接点,不包含index
*
* @param v
* @param index
* @return
*/
private int getNeightbor(int v, int index) {
for (int i = index + 1; i < verticeSize; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != MAX) {
return i;
}
}
return -1;
}
/**
* 深度优先遍历
*/
public void dfs() {
isVisited = new boolean[verticeSize];
for (int i = 0; i < verticeSize; i++) {
dfs(i);
}
}
private void dfs(int i) {
if (!isVisited[i]) {//输出i顶点
isVisited[i] = true;
System.out.print(vertices[i]);
} else {//访问过了,后面也没必要深度遍历了
return;
}
int next = getFirstNeightbor(i);
while (next != -1) {//以next进行深度遍历
if (!isVisited[next])
dfs(next);
next = getNeightbor(i, next);
}
}
测试代码:
Graph graph = new Graph(4);
graph.matrix[0] = new int[]{0, Graph.MAX, 34, Graph.MAX};
graph.matrix[1] = new int[]{7, 0, Graph.MAX, 45};
graph.matrix[2] = new int[]{6, Graph.MAX, 0, 34};
graph.matrix[3] = new int[]{0, 5, 9, 0};
System.out.println(graph.getInDegree(3));
System.out.println(graph.getOutDegree(1));
graph.dfs();
结果: 2 2 0231
2.广度优先遍历
/**
* 广度优先遍历
*/
public void bfs() {
isVisited = new boolean[verticeSize];
for (int i = 0; i < verticeSize; i++) {
if (!isVisited[i]) {
bfs(i);
}
}
}
private void bfs(int v) {
if(isVisited[v]) return;
//输出顶点
isVisited[v] = true;
System.out.print(vertices[v]);
Deque<Integer> deque = new LinkedList<>();
//遍历v的所有邻接点
for (int j = 0; j < verticeSize; j++) {
if (matrix[v][j] != 0 && matrix[v][j] != MAX) {
//入队
deque.offer(j);
}
}
while (!deque.isEmpty()) {
bfs(deque.poll());
}
}
测试:
Graph graph = new Graph(4);
graph.matrix[0] = new int[]{0, Graph.MAX, 34, Graph.MAX};
graph.matrix[1] = new int[]{7, 0, Graph.MAX, 45};
graph.matrix[2] = new int[]{6, Graph.MAX, 0, 34};
graph.matrix[3] = new int[]{0, 5, 9, 0};
System.out.println(graph.getInDegree(3));
System.out.println(graph.getOutDegree(1));
graph.bfs();
结果: 2 2 0231
类的完整代码:
/**
* 图论-邻接矩阵
*/
public static class Graph {
private int[] vertices; // 顶点
private int[][] matrix; // 图的节点的边
private int verticeSize; // 顶点的数量
public static final int MAX = Integer.MAX_VALUE;
private boolean[] isVisited;
public Graph(int verticeSize) {
this.verticeSize = verticeSize;
vertices = new int[verticeSize];
matrix = new int[verticeSize][verticeSize];
for (int i = 0; i < verticeSize; i++) {
vertices[i] = i;
}
}
/**
* 获取v1到v2的路径长度
*
* @param v1
* @param v2
* @return MAX:无穷大,即没有路径 0:本身
*/
public int getWeight(int v1, int v2) {
return matrix[v1][v2];
}
/**
* 获取顶点
*
* @return
*/
public int[] getVertices() {
return vertices;
}
/**
* 获取出度
*
* @param v
* @return
*/
public int getOutDegree(int v) {
int count = 0;
for (int i = 0; i < verticeSize; i++) {
//matrix[v][v]的一行中存放的数组为v到别的顶点的权
if (matrix[v][i] != 0 && matrix[v][i] != MAX) {
count++;
}
}
return count;
}
/**
* 获取入度
*
* @param v
* @return
*/
public int getInDegree(int v) {
int count = 0;
for (int i = 0; i < verticeSize; i++) {
//matrix[v][v]的一列中存放的为别的顶点到v的权
if (matrix[i][v] != 0 && matrix[i][v] != MAX) {
count++;
}
}
return count;
}
/**
* 获取v的第一个邻接点
*
* @param v
*/
private int getFirstNeightbor(int v) {
return getNeightbor(v, -1);
}
/**
* 获取index以后的v的邻接点,不包含index
*
* @param v
* @param index
* @return
*/
private int getNeightbor(int v, int index) {
for (int i = index + 1; i < verticeSize; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != MAX) {
return i;
}
}
return -1;
}
/**
* 深度优先遍历
*/
public void dfs() {
isVisited = new boolean[verticeSize];
for (int i = 0; i < verticeSize; i++) {
dfs(i);
}
}
private void dfs(int i) {
if (!isVisited[i]) {//输出i顶点
isVisited[i] = true;
System.out.print(vertices[i]);
} else {//访问过了,后面也没必要深度遍历了
return;
}
int next = getFirstNeightbor(i);
while (next != -1) {//以next进行深度遍历
if (!isVisited[next])
dfs(next);
next = getNeightbor(i, next);
}
}
/**
* 广度优先遍历
*/
public void bfs() {
isVisited = new boolean[verticeSize];
for (int i = 0; i < verticeSize; i++) {
if (!isVisited[i]) {
bfs(i);
}
}
}
private void bfs(int v) {
if(isVisited[v]) return;
//输出顶点
isVisited[v] = true;
System.out.print(vertices[v]);
Deque<Integer> deque = new LinkedList<>();
//遍历v的所有邻接点
for (int j = 0; j < verticeSize; j++) {
if (matrix[v][j] != 0 && matrix[v][j] != MAX) {
//入队
deque.offer(j);
}
}
while (!deque.isEmpty()) {
bfs(deque.poll());
}
}
}