1.基本介绍
图的概念:顶点,边,路径,
图的表示方式:邻接矩阵 邻接表
图的类型:无向图 有向图 带权图
2.代码实现(图的创建 深度优先遍历 广度优先遍历)
package Arithmetic;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
/**
* Created with IntelliJ IDEA.
* Description:
* User:
* Date: 2020-10-29
* Time: 22:27
* 说明:A-C C-D A -E E-B
* 流程 A - C - A - D - A - E - A - B
* 流程 A -B -C ...找全了 B -E 找全了 C -E 找全了
*/
public class ChartStructureJava {
ArrayList<String> list;
int[][] edges;
int numOfEdgers;
//用于判断是否是否访问过,重置为true
Boolean[] isVi;
public static void main(String[] args) {
ChartStructureJava cha = new ChartStructureJava(5);
String[] name = new String[]{"A", "B", "C", "D", "E"};
//添加节点
for (String s : name) {
cha.add(s);
}
//手动赋值
cha.side(0, 4, 1);
cha.side(4, 0, 1);
cha.side(0, 2, 1);
cha.side(2, 0, 1);
cha.side(2, 3, 1);
cha.side(3, 2, 1);
cha.side(0, 1, 1);
cha.side(1, 0, 1);
cha.side(1, 4, 1);
cha.side(4, 1, 1);
//对方法的实践:返回权值 遍历数组 边的数目 对应下标
System.out.println(cha.getindex(1, 2));
cha.ergodic();
System.out.println(cha.numOfEdgers);
System.out.println(cha.getindex(1));
//深度遍历
cha.dfs();
System.out.println();
cha.bfs();
}
//用于初始化
public ChartStructureJava(int n) {
list = new ArrayList<String>(n); //容量为n
edges = new int[n][n];
numOfEdgers = 0;
// isVi = new Boolean[]{false,false,false,false,false};
}
//返回权值
public int getindex(int n1, int n2) {
return edges[n1][n2];
}
//遍历数组
public void ergodic() {
for (int i = 0; i < edges.length; i++) {
for (int j = 0; j < edges[i].length; j++) {
System.out.print(edges[i][j] + "\t");
}
System.out.println();
}
}
//获取边的数目
public int getNumOfEdgers() {
return this.numOfEdgers;
}
//获取对应下标的值
public String getindex(int st) {
return list.get(st) == null ? "不存在" : list.get(st);
}
//插入节点
public void add(String node) {
list.add(node);
}
//插入边
public void side(int v1, int v2, int wight) {
//犯了一个错误,这里注意wight为0是不能添加
edges[v1][v2] = wight;
edges[v2][v1] = wight;
this.numOfEdgers++;
}
//给定一个初始节点,判断是否存在邻接
public int firstView(int index) {
//由下标或者第一个邻接节点
for (int j = 0; j < isVi.length; j++) {
if (edges[index][j] > 0) {
//说明找到了下一个节点
// isVi[j] = true;
return j;
}
}
//没有找到
return -1;
}
//访问访问某个(初始节点,已经访问的节点) =>之后的节点
public int secondView(int s1, int s2) {
//s1 是我指定的第一个节点
//s2 是第一个邻接结点
for (int i = s2 + 1; i < isVi.length; i++) {
//找第二个邻接结点
if (edges[s1][i] > 0) {
return i;
}
}
return -1;
}
public void dfs(Boolean[] isVi, int index) {
//打印第一个结点
System.out.print(getindex(index) + "=>");
//把这个节点设置为true
isVi[index] = true;
//查找第一个邻接结点
int w = firstView(index);
//说明存在
while (w != -1) {
//并且要保证这个节点不为true
if (!isVi[w]) {
//说明这个节点没有访问,继续访问
dfs(isVi, w);
}
//判断下一个节点是否存在,存在就继续调用,不存在就退出
w = secondView(index, w);
}
}
public void dfs() {
isVi = new Boolean[]{false, false, false, false, false};
//这里是考虑了,断点情况!!!!!
for (int i = 0; i < list.size(); i++) {
if (!isVi[i]) {
dfs(isVi, i);
}
}
}
//广度优先遍历
public void bfs(Boolean[] isVi, int index) {
//队列第一个元素
int u;
//第一个邻接节点
int w;
//使用一个linkedlist来表示队列
LinkedList<Integer> queue = new LinkedList<>();
//首先打印这个节点
System.out.print(getindex(index) + "=>");
//把这个节点置为true
isVi[index] = true;
//把这个节点添加到最后面
queue.addLast(index);
//继续循环遍历,只要这个链表不为空
while (!queue.isEmpty()) {
//取出第一个元素
u = (Integer) queue.removeFirst();
//获取邻接节点,链表第一个元素的邻接节点
w = firstView(u);
//循环,只要节点不为-1
while (w != -1) {
//只要不为-1,说明存在下一个邻接节点,要判断这个节点是否为true
if (!isVi[w]) {
//这里我要把w给标记为true
isVi[w] = true;
//说明没有遍历过,打印这个节点
System.out.print(getindex(w) + "=>");
//入队
queue.addLast(w);
}
//否则寻找以第一个为首,下一个邻接节点
w = secondView(u, w);
}
}
}
public void bfs() {
isVi = new Boolean[]{false, false, false, false, false};
//for作用,假设存在断点的情况,按照加入的顺序打印结果
for (int i = 0; i < list.size(); i++) {
if (!isVi[i]) {
bfs(isVi, i);
}
}
}
}
3.深度优先遍历
image.png
4.广度优先遍历
image.png
两种方式的比较
image.png
网友评论