图中的元素称为“顶点”，如果两个顶点是连通的，连通的线叫作“边”，两点之间的距离叫作“权”，对于无向边（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());
}
}
}
网友评论