Java数据结构与算法

Java数据结构:图

2020-07-21  本文已影响0人  Patarw

一、为什么要有图

基本介绍

二、图的表示方式

图的表示方式有两种:二维数组表示(邻接矩阵)链表表示(邻接表)

       public class ArrayQueue {

private ArrayList<String> vertexList; //存储顶点集合
private int[][] edgs; //存储对应邻接矩阵
private int numOfEdgs; //表示边的数目
private boolean[] isVisited; //记录某个节点是否被访问
public static void main(String[] args) {    
    int n = 5;
    String VertexValue[] = {"A","B","C","D","E"};
    ArrayQueue a = new ArrayQueue(n);
    for(String val : VertexValue) {
        a.insertVertex(val);
    }
    //A-B A-C B-C B-D B-E
    a.insertEdge(0, 1, 1);
    a.insertEdge(0, 2, 1);
    a.insertEdge(1, 2, 1);
    a.insertEdge(1, 3, 1);
    a.insertEdge(1, 4, 1);
    a.print();
    a.dfs();
}

//构造器,初始化实例
public ArrayQueue(int n) {
    edgs = new int[n][n];
    vertexList = new ArrayList<>(n);
    numOfEdgs = 0;
    isVisited = new boolean[n];
}

//插入节点
public void insertVertex(String vertex) {
    vertexList.add(vertex);
}

//添加边
public void insertEdge(int v1,int v2,int weight) {
    edgs[v1][v2] = weight;
    edgs[v2][v1] = weight;
    numOfEdgs++;
}

//返回节点个数
public int getNumOfVertex() {
    return vertexList.size();
}

//得到边的数目
public int getNumOfEdgs() {
    return numOfEdgs;
}

//返回i下表对应的数据
public String getValueByIndex(int i) {
    return vertexList.get(i);
}

//返回v1,v2的权值
public int getWeight(int v1,int v2) {
    return edgs[v1][v2];
}

//打印图
public void print() {
    for(int[] a : edgs) {
        for(int i = 0;i < a.length;i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

}

三、图的遍历方式

1、图的深度优先遍历 DFS (Depth First Search)
      //得到下一个邻接节点的下标
public int getFirstNeighbor(int index) {
    for(int j = 0;j < vertexList.size();j++) {
        if(edgs[index][j] > 0) {
            return j;
        }
    }
    return -1;
}

//获取下一位
public int getNextNeighbor(int v1,int v2) {
    for(int j = v2 + 1;j < vertexList.size();j++) {
        if(edgs[v1][j] > 0) {
            return j;
        }
    }
    return -1;
}

//深度优先遍历算法
public void dfs(boolean[] isVisited,int i) {
    //首先访问该节点
    System.out.print(getValueByIndex(i) + "->");
    isVisited[i] = true; //设置节点为已访问
    int w = getFirstNeighbor(i);
    while(w != -1) {
        if(!isVisited[w]) {
            dfs(isVisited,w);
        }
        w = getNextNeighbor(i,w);
    }
}

//对dfs进行一个重载,遍历我们所有的节点,并进行dfs
public void dfs() {
    //遍历所有节点,进行dfs[回溯]
    for(int i = 0;i < getNumOfVertex();i++) {
        if(!isVisited[i]) {
            dfs(isVisited,i);
        }
    }
}
2、图的广度优先遍历 BFS (Broad First Search)

二叉树的层次遍历,本质上也可以认为是深度优先遍历。

      //广度优先遍历算法
public void bfs(boolean[] isVisited,int i) {
    int u = 0;
    int w = 0;
    LinkedList q = new LinkedList(); //用链表模拟队列
    System.out.print(getValueByIndex(i) + "=>");
    isVisited[i] = true;
    q.addLast(i);
    
    while(!q.isEmpty()) {
        u = (Integer)q.removeFirst();
        w = getFirstNeighbor(u);
        while(w != -1) {
            if(!isVisited[w]) {
                System.out.print(getValueByIndex(w) + "=>");
                isVisited[w] = true;
                q.addLast(w);
            }
            w = getNextNeighbor(u,w);
        }
    }
}

五、图的深度优先VS 广度优先

上一篇 下一篇

猜你喜欢

热点阅读