数据结构之图【深搜，广搜】-蒲公英云

package com.zhiru;
import java.util.Queue;
import java.util.LinkedList;
public class MyGraph {
    private int maxVertices;// 最大顶点数
    private int numVertices;// 当前顶点数
    private int numEdges;// 当期边数
    private int[] verticesList;// 顶点表
    private int[][] edge;// 边邻接矩阵
    public MyGraph(int size) {
        maxVertices = size;
        numVertices = 0;
        numEdges = 0;
        int i, j;
        verticesList = new int[maxVertices];
        edge = new int[maxVertices][];
        for (i = 0; i < maxVertices; i++) {
            edge[i] = new int[maxVertices];
        }
        for (i = 0; i < maxVertices; i++) {
            for (j = 0; j < maxVertices; j++)
                edge[i][j] = (i == j) ? 0 : Integer.MAX_VALUE;
        }
    }
    public int getPos(int v) {
        for (int i = 0; i < numVertices; i++) {
            if (verticesList[i] == v)
                return i;
        }
        return -1;// 没找到
    }
    // 插入顶点v
    public void insertVertex(int v) {
        if (numVertices == maxVertices)
            return;
        verticesList[numVertices++] = v;
    }
    // 删除顶点v
    public void deleteVertex(int v) {
        if (v < 0 || v >= numVertices)
            return;
        if (numVertices == 1)
            return;// 只有一个顶点不删除
        int i, j, k, m;
        k = getPos(v);
        m = k;
        for (; k < numVertices - 1; k++) {
            verticesList[k] = verticesList[k + 1];
        }
        for (i = 0; i < numVertices; i++)
            if (edge[i][v] > 0 && edge[i][v] < Integer.MAX_VALUE)
                numEdges--;
        for (i = 0; i < numVertices; i++) {
            for (j = m; j < numVertices - 1; j++) {
                edge[i][j] = edge[i][j + 1];
            }
        }
        int n = numVertices;
        numVertices--;
        for (j = 0; j < numVertices; j++) {
            for (i = m; i < n - 1; i++) {
                edge[i][j] = edge[i + 1][j];
            }
        }
    }
    // 插入边v1,v2,权值cost
    public void insertEdge(int v1, int v2, int cost) {
        if (v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices
                && edge[v1][v2] == Integer.MAX_VALUE) {
            edge[v1][v2] = edge[v2][v1] = cost;
            numEdges++;
        } else {
            return;
        }
    }
    public void deleteEdge(int v1, int v2) {
        if (v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices
                && edge[v1][v2] > 0 && edge[v1][v2] < Integer.MAX_VALUE) {
            edge[v1][v2] = edge[v2][v1] = Integer.MAX_VALUE;
            numEdges--;
        } else
            return;
    }
    // 建立图
    /*
     * l是顶点一维矩阵，a是邻接矩阵，n是顶点数，m是边数
     */
    public void buildGraph(int[] l, int[][] a, int n, int m) {
        numVertices = n;
        numEdges = m;
        for (int k = 0; k < numVertices; k++) {
            verticesList[k] = l[k];
        }
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                edge[i][j] = a[i][j];
            }
        }
    }
    public void prtGraph() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(edge[i][j] + " ");
            }
            System.out.print("\n");
        }
    }
    // 给出顶点v的第一个邻接顶点的位置，找不到返回-1
    public int getFirstNeighbor(int v) {
        if (v != -1) {
            for (int col = 0; col < numVertices; col++)
                if (edge[v][col] > 0 && edge[v][col] < Integer.MAX_VALUE)
                    return col;
        }
        return -1;
    }
    // 给出顶点v的邻接顶点w的下一个邻接顶点
    public int getNextNeighbor(int v, int w) {
        if (v != -1 && w != -1) {
            for (int col = w + 1; col < numVertices; col++)
                if (edge[v][col] > 0 && edge[v][col] < Integer.MAX_VALUE)
                    return col;
        }
        return -1;
    }
    public int getValue(int i) {
        if (i >= 0 && i < numVertices)
            return verticesList[i];
        return -1;
    }
    // 图的深度优先搜索
    public void traversal(int k) {
        int loc, n = numVertices;
        boolean[] visited = new boolean[n];
        loc = getPos(k);
        dfs(loc, visited);
    }
    private void dfs(int loc, boolean[] visited) {
        prt("" + getValue(loc));
        visited[loc] = true;
        int w = getFirstNeighbor(loc);
        while (w != -1) {
            if (visited[w] == false)
                dfs(w, visited);
            w = getNextNeighbor(loc, w);
        }
    }
    // 图的广度优先搜索算法,从节点k开始遍历图
    public void bfs(int k) {
        int i, j, loc;
        Queue<Integer> q = new LinkedList<Integer>();
        loc = getPos(k);
        boolean[] visited = new boolean[numVertices];
        prt(getValue(loc) + "");
        visited[k] = true;
        q.offer(k);// k进队列
        while (!q.isEmpty()) {
            i = q.poll();
            for (j = 0; j < numVertices; j++) {
                if (!visited[j]) {
                    prt(getValue(j) + "");
                    visited[j] = true;// 标记已被访问
                    q.offer(j);// 访问过的j入队
                }
            }
        }
    }
    public static void prt(String s) {
        System.out.print(s + "\n");
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyGraph mg = new MyGraph(10);
        int[][] a = { { 0, 1, Integer.MAX_VALUE, 4 },
                { Integer.MAX_VALUE, 0, 9, 2 }, { 3, 5, 0, 8 },
                { Integer.MAX_VALUE, Integer.MAX_VALUE, 6, 0 } };
        int[] vl = { 0, 1, 2, 3 };
        mg.buildGraph(vl, a, 4, 8);
        mg.prtGraph();
        mg.insertVertex(4);
        mg.insertEdge(0, 4, 100);
        prt("插入顶点4和0-->4边后");
        mg.prtGraph();
        // prt("删除顶点1后:");
        // mg.deleteVertex(1);
        //mg.prtGraph();
        prt("深度优先搜索：");
        mg.traversal(3);
         prt("广度优先搜索：");
         mg.bfs(4);
    }
}

0 1 2147483647 4
2147483647 0 9 2
3 5 0 8
2147483647 2147483647 6 0
插入顶点4和0—>4边后
0 1 2147483647 4 100
2147483647 0 9 2 2147483647
3 5 0 8 2147483647
2147483647 2147483647 6 0 2147483647
100 2147483647 2147483647 2147483647 0
深度优先搜索：
3
2
0
1
4
广度优先搜索：
4
0
1
2
3