图（无向网）的邻接矩阵存储以及深度、广度优先遍历 *** 作-java

public class AdjacencyMatrixGraph {

    // 图的顶点数组
    char[] vexs;
    // 邻接矩阵
    int arcs[][];
    // 图中顶点和边的数量
    int vexNums,arcNums;

    // 构造方法
    public AdjacencyMatrixGraph(int n){
        this.vexs=new char[n];
        this.arcs=new int[n][n];
    }

    
    public void init(String vexStr,String[] arcStr){
        // 初始化顶点数组
        for (int i = 0; i < vexs.length; i++) {
            vexs[i]=vexStr.charAt(i);
            vexNums++;
        }

        // 初始化邻接矩阵，并附默认值为最大数
        for (int i = 0; i < arcs.length; i++) {
            for (int j = 0; j < arcs[i].length; j++) {
                arcs[i][j]=Integer.MAX_VALUE;
            }
        }

        // 根据边的关系给邻接矩阵赋值
        for (String s : arcStr) {
            // 顶点v1
            char v1=s.charAt(0);
            // 顶点v2
            char v2=s.charAt(2);
            // 权值
            int w=s.charAt(4)-'0';
            // 得到i，j
            int i=locateVex(v1);
            int j=locateVex(v2);

            // 设边(v1,v2)的权值为w
            arcs[i][j]=w;
            // 因为是无向网，它的邻接矩阵是对称的，所以设边(v2,v1)的对称边也为w
            arcs[j][i]=w;
            arcNums++;
        }

    }

    // 查找某一顶点在顶点数组中的下标
    private int locateVex(char v){
        for (int i = 0; i < vexs.length; i++) {
            if(v==vexs[i]){
                return i;
            }
        }
        return -1;
    }

    
    public void DFS(int vex,int[] visited){
        visited[vex]=1;
        System.out.println("访问了"+vexs[vex]);
        for (int j = 0; j < this.vexs.length; j++) {
            if(this.arcs[vex][j]!=0 && visited[j]==0){
                DFS( j, visited);
            }
        }
    }

    
    public void BFS(int vex, Queue queue, int[] visited){
        queue.add(vex);
        visited[vex]=1;
        System.out.println("访问了"+vexs[vex]);
        // 如果队列不为空
        while(!queue.isEmpty()){
            int i= (int) queue.poll();
            for (int j=0; j 
测试类：
 
public class Test {
    public static void main(String[] args) {
        AdjacencyMatrixGraph adjacencyMatrixGraph=new AdjacencyMatrixGraph(4);
        // 无向网的顶点集合
        String vexStr="ABCD";
        // 无向网的边集合，例如"A,B,4"，A，B分别为边的两个顶点，4为此条边的权值
        String arcStr[]={"A,B,4","A,C,3","A,D,9","B,C,1","B,D,7","C,D,2"};
        adjacencyMatrixGraph.init(vexStr,arcStr);
        System.out.println("无向网初始化完成");

        System.out.println("深度优先遍历：");
        adjacencyMatrixGraph.DFS(2,new int[4]);
        System.out.println("广度优先遍历：");
        adjacencyMatrixGraph.BFS(3,new ArrayDeque(), new int[4]);
    }
}
 
测试类运行结果：
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5707427.html