图的存储结构（邻接矩阵方式）
此图为带权无向图
public class MyGraph {
private ArrayList<Object> vertexList; //存放顶点的数组
private int[][] edges; //邻接矩阵，存放边集
private int numofEdges; //边数
private static final int INF = 65535; //权值为65535时表示不可达
private boolean[] visited; //用于深度、广度遍历时顶点是否已被访问的标志
public MyGraph(int n) {
vertexList = new ArrayList<>(n); //根据传入的顶点数构造顶点数组
edges = new int[n][n]; //构造对应的邻接矩阵
numofEdges = 0;
visited = new boolean[n];
//初始化邻接矩阵
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if (i == j) {
edges[i][j] = 0;
}else {
edges[i][j] = INF;
}
}
}
}
//获取顶点个数
public int getNumOfVertex() {
return vertexList.size();
}
//获取边数
public int getNumofEdges() {
return numofEdges;
}
//打印邻接矩阵
public void printEdges() {
for(int i = 0; i < vertexList.size(); i++) {
for(int j =0; j < vertexList.size(); j++) {
if (j == vertexList.size() - 1) {
System.out.println(edges[i][j]);
}else {
System.out.print(edges[i][j]+" ");
}
}
}
}
//获取顶点n的值
public Object getValueByIndex(int n) {
return vertexList.get(n);
}
//获取边n1-n2的权值
public int getWeight(int n1, int n2) {
return edges[n1][n2];
}
//插入结点
public void insertVertex(Object vertex) {
vertexList.add(vertexList.size(),vertex);
}
//插入顶点以及设置权值
public void insertEdge(int n1, int n2, int weight) {
edges[n1][n2] = weight;
//该图为无向图，所以矩阵关于对角线对称
edges[n2][n1] = weight;
numofEdges++;
}
//删除边
public void deleteEdge(int n1, int n2) {
edges[n1][n2] = INF;
//无向图删除边时矩阵依旧对称
edges[n2][n1] = INF;
numofEdges--;
}
}
测试类
测试图如图所示：
图片.png
测试程序如下:
//顶点数为4
int n = 4;
String[] vertex = {"A","B","C","D"};
MyGraph graph = new MyGraph(n);
for (String string : vertex) {
graph.insertVertex(string);
}
graph.insertEdge(0, 1, 3);
graph.insertEdge(0, 2, 8);
graph.insertEdge(0, 3,10);
graph.insertEdge(1, 2, 6);
System.out.println("结点数："+graph.getNumOfVertex());
System.out.println("边数："+graph.getNumofEdges());
System.out.println("删除前的邻接矩阵：");
graph.printEdges();
graph.deleteEdge(1, 2);
System.out.println("删除边<B,C>后：");
System.out.println("结点个数为："+graph.getNumOfVertex());
System.out.println("边数为："+graph.getNumofEdges());
System.out.println("删除后的邻接矩阵：");
graph.printEdges();
测试结果：
图片.png
遍历算法
测试图（由于权值不影响遍历结果，所以不标注）：
图片.png
深度优先
//邻接矩阵的深度遍历操作
public void DFSTraverse(MyGraph graph) {
for (int i = 0; i < graph.getNumOfVertex(); i++) {
visited[i] = false;
}
for( int i = 0; i < graph.getNumOfVertex(); i++) {
//对未访问过的结点调用DFS，若是连通图，只会执行一次，非连通图的话有多少个子图则会调用多少次
if (!visited[i]) {
DFS(graph, i);
}
}
}
//邻接矩阵的深度优先递归算法
public void DFS(MyGraph graph, int i) {
//设置访问标志位为true
visited[i] = true;
System.out.print(getValueByIndex(i)+" ");
for(int j = 0; j < graph.getNumOfVertex(); j++) {
if (edges[i][j] != 0 && edges[i][j] != INF && !visited[j] ) {
//对未访问的邻接结点递归调用
DFS(graph, j);
}
}
}
广度优先
//邻接矩阵的广度遍历算法
public void BFSTraverse(MyGraph graph) {
int i,j;
//初始化访问标志矩阵
for(i = 0; i < graph.getNumOfVertex(); i++) {
visited[i] = false;
}
//使用linkedList模拟队列的功能
LinkedList<Integer> queue = new LinkedList<>();
for(i = 0; i < graph.getNumOfVertex(); i++) {
//该图为非连通图时，第一次广度遍历完后还有结点未被访问时会再次进入这个分支
//该图为连通图时，该分支只会执行一次，因为执行一次后所有的结点都被访问到了
if (!visited[i]) {
visited[i] = true;
System.out.print(getValueByIndex(i)+" ");
//将结点添加到队尾
queue.addLast(i);
while(!queue.isEmpty()) {
//移除队头元素并将其赋值给i
i = ((Integer)queue.removeFirst()).intValue();
for(j = 0; j < graph.getNumOfVertex(); j++) {
if (edges[i][j] != 0 && edges[i][j] != INF && !visited[j] ) {
visited[j] = true;
System.out.print(getValueByIndex(j)+" ");
queue.addLast(j);
}
}
}
}
}
}
广度优先各结点在队列中的情况如下
图片.png
测试程序：
public class GraphTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
//顶点数为4
int n = 9;
String[] vertex = {"A","B","C","D","E","F","G","H","I"};
MyGraph graph = new MyGraph(n);
for (String string : vertex) {
graph.insertVertex(string);
}
graph.insertEdge(0, 1, 3);
graph.insertEdge(0, 2, 8);
graph.insertEdge(1, 3,10);
graph.insertEdge(1, 4, 3);
graph.insertEdge(2, 5, 3);
graph.insertEdge(2, 6, 3);
graph.insertEdge(3, 7, 3);
graph.insertEdge(7, 8, 3);
System.out.println("深度优先遍历结果：");
graph.DFSTraverse(graph);
System.out.println("\n广度优先遍历：");
graph.BFSTraverse(graph);
}
}
测试结果：
图片.png
网友评论