zcq
    图的创建图解
    深度搜索（DFS）
    广度搜索（BFS）

    1. package com.atguigu.graph;
    3. import java.util.ArrayList;
    4. import java.util.Arrays;
    5. import java.util.LinkedList;
    7. public class Graph {
    9.     private ArrayList<String> vertexList; //存储顶点集合
    10.     private int[][] edges; //存储图对应的邻结矩阵
    11.     private int numOfEdges; //表示边的数目
    12.     //定义给数组boolean[], 记录某个结点是否被访问
    13.     private boolean[] isVisited;
    15.     public static void main(String[] args) {
    16.         //测试一把图是否创建ok
    17.         int n = 8;  //结点的个数
    18.         //String Vertexs[] = {"A", "B", "C", "D", "E"};
    19.         String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
    21.         //创建图对象
    22.         Graph graph = new Graph(n);
    23.         //循环的添加顶点
    24.         for(String vertex: Vertexs) {
    25.             graph.insertVertex(vertex);
    26.         }
    28.         //添加边
    29.         //A-B A-C B-C B-D B-E 
    30. //        graph.insertEdge(0, 1, 1); // A-B
    31. //        graph.insertEdge(0, 2, 1); // 
    32. //        graph.insertEdge(1, 2, 1); // 
    33. //        graph.insertEdge(1, 3, 1); // 
    34. //        graph.insertEdge(1, 4, 1); // 
    36.         //更新边的关系
    37.         graph.insertEdge(0, 1, 1);
    38.         graph.insertEdge(0, 2, 1);
    39.         graph.insertEdge(1, 3, 1);
    40.         graph.insertEdge(1, 4, 1);
    41.         graph.insertEdge(3, 7, 1);
    42.         graph.insertEdge(4, 7, 1);
    43.         graph.insertEdge(2, 5, 1);
    44.         graph.insertEdge(2, 6, 1);
    45.         graph.insertEdge(5, 6, 1);
    49.         //显示一把邻结矩阵
    50.         graph.showGraph();
    52.         //测试一把，我们的dfs遍历是否ok
    53.         System.out.println("深度遍历");
    54.         graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]
    55. //        System.out.println();
    56.         System.out.println("广度优先!");
    57.         graph.bfs(); // A->B->C->D-E [1->2->3->4->5->6->7->8]
    59.     }
    61.     //构造器
    62.     public Graph(int n) {
    63.         //初始化矩阵和vertexList
    64.         edges = new int[n][n];
    65.         vertexList = new ArrayList<String>(n);
    66.         numOfEdges = 0;
    68.     }
    70.     //得到第一个邻接结点的下标 w 
    71.     /**
    72.      * 
    73.      * @param index 
    74.      * @return 如果存在就返回对应的下标，否则返回-1
    75.      */
    76.     public int getFirstNeighbor(int index) {
    77.         for(int j = 0; j < vertexList.size(); j++) {
    78.             if(edges[index][j] > 0) {
    79.                 return j;
    80.             }
    81.         }
    82.         return -1;
    83.     }
    84.     //根据前一个邻接结点的下标来获取下一个邻接结点
    85.     public int getNextNeighbor(int v1, int v2) {
    86.         for(int j = v2 + 1; j < vertexList.size(); j++) {
    87.             if(edges[v1][j] > 0) {
    88.                 return j;
    89.             }
    90.         }
    91.         return -1;
    92.     }
    94.     //深度优先遍历算法
    95.     //i 第一次就是 0
    96.     private void dfs(boolean[] isVisited, int i) {
    97.         //首先我们访问该结点,输出
    98.         System.out.print(getValueByIndex(i) + "->");
    99.         //将结点设置为已经访问
    100.         isVisited[i] = true;
    101.         //查找结点i的第一个邻接结点w
    102.         int w = getFirstNeighbor(i);
    103.         while(w != -1) {//说明有
    104.             if(!isVisited[w]) {
    105.                 dfs(isVisited, w);
    106.             }
    107.             //如果w结点已经被访问过
    108.             w = getNextNeighbor(i, w);
    109.         }
    111.     }
    113.     //对dfs 进行一个重载, 遍历我们所有的结点，并进行 dfs
    114.     public void dfs() {
    115.         isVisited = new boolean[vertexList.size()];
    116.         //遍历所有的结点，进行dfs[回溯]
    117.         for(int i = 0; i < getNumOfVertex(); i++) {
    118.             if(!isVisited[i]) {
    119.                 dfs(isVisited, i);
    120.             }
    121.         }
    122.     }
    124.     //对一个结点进行广度优先遍历的方法
    125.     private void bfs(boolean[] isVisited, int i) {
    126.         int u ; // 表示队列的头结点对应下标
    127.         int w ; // 邻接结点w
    128.         //队列，记录结点访问的顺序
    129.         LinkedList queue = new LinkedList();
    130.         //访问结点，输出结点信息
    131.         System.out.print(getValueByIndex(i) + "=>");
    132.         //标记为已访问
    133.         isVisited[i] = true;
    134.         //将结点加入队列
    135.         queue.addLast(i);
    137.         while( !queue.isEmpty()) {
    138.             //取出队列的头结点下标
    139.             u = (Integer)queue.removeFirst();
    140.             //得到第一个邻接结点的下标 w 
    141.             w = getFirstNeighbor(u);
    142.             while(w != -1) {//找到
    143.                 //是否访问过
    144.                 if(!isVisited[w]) {
    145.                     System.out.print(getValueByIndex(w) + "=>");
    146.                     //标记已经访问
    147.                     isVisited[w] = true;
    148.                     //入队
    149.                     queue.addLast(w);
    150.                 }
    151.                 //以u为前驱点，找w后面的下一个邻结点
    152.                 w = getNextNeighbor(u, w); //体现出我们的广度优先
    153.             }
    154.         }
    156.     } 
    158.     //遍历所有的结点，都进行广度优先搜索
    159.     public void bfs() {
    160.         isVisited = new boolean[vertexList.size()];
    161.         for(int i = 0; i < getNumOfVertex(); i++) {
    162.             if(!isVisited[i]) {
    163.                 bfs(isVisited, i);
    164.             }
    165.         }
    166.     }
    168.     //图中常用的方法
    169.     //返回结点的个数
    170.     public int getNumOfVertex() {
    171.         return vertexList.size();
    172.     }
    173.     //显示图对应的矩阵
    174.     public void showGraph() {
    175.         for(int[] link : edges) {
    176.             System.err.println(Arrays.toString(link));
    177.         }
    178.     }
    179.     //得到边的数目
    180.     public int getNumOfEdges() {
    181.         return numOfEdges;
    182.     }
    183.     //返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"
    184.     public String getValueByIndex(int i) {
    185.         return vertexList.get(i);
    186.     }
    187.     //返回v1和v2的权值
    188.     public int getWeight(int v1, int v2) {
    189.         return edges[v1][v2];
    190.     }
    191.     //插入结点
    192.     public void insertVertex(String vertex) {
    193.         vertexList.add(vertex);
    194.     }
    195.     //添加边
    196.     /**
    197.      * 
    198.      * @param v1 表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1
    199.      * @param v2 第二个顶点对应的下标
    200.      * @param weight 表示 
    201.      */
    202.     public void insertEdge(int v1, int v2, int weight) {
    203.         edges[v1][v2] = weight;
    204.         edges[v2][v1] = weight;
    205.         numOfEdges++;
    206.     }
    207. }