1.图的定义

　　图G是由顶点的有穷集合，以及顶点之间的关系组成，顶点的集合记为V，顶点之间的关系构成边的集合E，G=(V,E).

　　如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。

２.图的存储

　　一般图的存储有两种方式
　　
　　1)邻接表：需要保存一个顺序存储的顶点表和每个顶点上的边的链接表。
　　
　　2)相邻矩阵：用一个矩阵来保持边的情况
　　　　

[数据结构] 图的BFS、DFS、prim、Dijkstra算法（Java代码）　

下图展示了两种表示上面这个图的方法：

[数据结构] 图的BFS、DFS、prim、Dijkstra算法（Java代码）　

３.图的遍历

　　①　DFS（Depth First Search）深度优先搜索，为每个顶点设立一个“访问标志”。首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行遍历。

　　若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之。反之，退回到最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕；

遍历图的过程实质上是对每个顶点查找其邻接点的过程，所耗费的时间取决于所采用的存储结构。
对图中的每个顶点至多调用1次DFS算法，因为一旦某个顶点已访问过，则不再从它出发进行搜索。

邻接链表表示：查找每个顶点的邻接点所需时间为O(e)，e为边(弧)数，算法时间复杂度为O(n+e)

数组表示：查找每个顶点的邻接点所需时间为O(n2)，n为顶点数，算法时间复杂度为O(n2)

　　②　BFS（Breadth First Search）广度优先遍历，从图的某一结点出发，首先依次访问该结点的所有邻接顶点 Vi1, Vi2, …, Vin 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。

３.１遍历代码（邻接矩阵）

// 邻接矩阵存储图
public class Graph {
    // 顶点数
    private int number = 9;
    // 记录顶点是否被访问
    private boolean[] flag;
    // 顶点
    private String[] vertexs = { "A", "B", "C", "D", "E", "F", "G", "H", "I" };
    // 边
    private int[][] edges = { 
            { 0, 1, 0, 0, 0, 1, 1, 0, 0 }, 
            { 1, 0, 1, 0, 0, 0, 1, 0, 1 }, 
            { 0, 1, 0, 1, 0, 0, 0, 0, 1 },
            { 0, 0, 1, 0, 1, 0, 1, 1, 1 },
            { 0, 0, 0, 1, 0, 1, 0, 1, 0 }, 
            { 1, 0, 0, 0, 1, 0, 1, 0, 0 },
            { 0, 1, 0, 1, 0, 1, 0, 1, 0 },
            { 0, 0, 0, 1, 1, 0, 1, 0, 0 }, 
            { 0, 1, 1, 1, 0, 0, 0, 0, 0 } 
            };

    // 图的深度遍历操作(递归)
    void DFSTraverse() {
        flag = new boolean[number];
        for (int i = 0; i < number; i++) {
            if (flag[i] == false) {// 当前顶点没有被访问
                DFS(i);
            }
        }
    }

    // 图的深度优先递归算法
    void DFS(int i) {
        flag[i] = true;// 第i个顶点被访问
        System.out.print(vertexs[i] + " ");
        for (int j = 0; j < number; j++) {
            if (flag[j] == false && edges[i][j] == 1) {
                DFS(j);
            }
        }
    }

    // 图的广度遍历操作
    void BFSTraverse() {
        flag = new boolean[number];
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < number; i++) {
            if (flag[i] == false) {
                flag[i] = true;
                System.out.print(vertexs[i] + " ");
                queue.add(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    for (int k = 0; k < number; k++) {
                        if (edges[j][k] == 1 && flag[k] == false) {
                            flag[k] = true;
                            System.out.print(vertexs[k] + " ");
                            queue.add(k);
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        System.out.println("-----------DFS-----------------");
        graph.DFSTraverse();
        System.out.println();
        System.out.println("-----------BFS-----------------");
        graph.BFSTraverse();
    }
}

运行结果：

[数据结构] 图的BFS、DFS、prim、Dijkstra算法（Java代码）　

4.最小生成树prim算法

　　从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

输入：一个加权连通图，其中顶点集合为V，边集合为E；
初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
重复下列操作，直到Vnew = V：

3.1 在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
3.2 将v加入集合Vnew中，将（u, v）加入集合Enew中；
输出：使用集合Vnew和Enew来描述所得到的最小生成树。

此为原始的加权连通图。每条边一侧的数字代表其权值。