[数据结构与算法]使用矩阵和链表储存图的代码实现以及图的深度优先遍历代码实现

邻接矩阵保存图

用邻接矩阵来保存图

package Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author lixiangxiang
 * @description
 * @date 2021/8/6 16:49
 */
public class Graph {

    /** 边 */
    private int[][] edges;
    /**
     * 边数
     */
    private int numOfEdges;
    /**
     * 顶点集合
     */
    private List<String> vertexList;

    public static void main(String[] args) {
        int n = 8;  //结点的个数
        String vertexs[] = {"A", "B", "C", "D", "E"};
        
        //创建图对象
        Graph graph = new Graph(vertexs.length);
        //循环的添加顶点
        for(String vertex: vertexs) {
            graph.addVertex(vertex);
        }

        graph.insertEdge(0, 1, 1);
		graph.insertEdge(0, 2, 1);
		graph.insertEdge(1, 2, 1);
		graph.insertEdge(1, 3, 1);
		graph.insertEdge(1, 4, 1);
		graph.showGraph();
    }

    /**
     * 添加顶点
     */
    public void addVertex(String vertex) {
        vertexList.add(vertex);
    }

    //构造器
    public Graph(int n) {
        //初始化矩阵和vertexList
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;

    }

    /**
     * 显示图对应的矩阵
     */
    public void showGraph() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    /**
     * 根据下标获取数据
     * @param i
     * @return
     */
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

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

使用链表储存图

package Graph;

/**
 * @author lixiangxiang
 * @description 用链表来储存图
 * @date 2021/8/7 18:31
 */
public class LinkedGraphDemo {

    public static void main(String[] args) {

        String vertexs[] = {"A", "B", "C", "D", "E"};
        Integer edge[][] = {{1,3},{2,4},{1,4},{1,2},{2,4},{2,3}};
        LinkedGraph graph = new LinkedGraph(vertexs.length);
        //初始化每条链表的根节点。
        for (int i = 0; i < vertexs.length; i++) {
            graph.linkedLists[i].root = new RootNode(vertexs[i]);
        }
        for (int i = 0; i < edge.length; i++) {
            for (int j = 0; j < edge[i].length; j++) {
                System.out.print(edge[i][j]+" ");
//                if (i!=0&&j!=0) {
//                    graph.linkedLists[j].addNode(edge[i][j]);
//                    graph.linkedLists[edge[i][j]].addNode(j);
//                }
            }
            System.out.println();
        }
//        graph.linkedLists[0].show();
        graph.show();
    }

}

class LinkedGraph {

    //图的邻接表。
    GraphLinkedList[] linkedLists;


    //图的当前顶点数
    int vexNum;


    //初始化
    public LinkedGraph(int vexNum) {
        this.vexNum = vexNum;
        linkedLists = new GraphLinkedList[vexNum];
        for (int i = 0; i < linkedLists.length; i++) {
            linkedLists[i] = new GraphLinkedList();
        }
    }

    public void show() {
        for (int i = 0; i < linkedLists.length; i++) {
            linkedLists[i].show();
            System.out.println();
        }
    }

}


class GraphLinkedList {
    RootNode root;


    public void addNode(int value) {
        Node newNode = new Node(value);
        if (root.next == null) {
            root.next = newNode;
            return;
        }
        Node cur = root.next;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
    }

    public void show() {
        System.out.print(root.data+"->");
        Node cur = root.next;
        while (cur != null) {
            System.out.print(cur.data + "->");
            cur = cur.next;
        }
    }
}

/**
 * 顶点信息
 */
class Node {
    /**
     * 顶点值
     */
    int  data;

    /**
     * 下一节点
     */
    Node next;

    /**
     * 其根节点
     */
    RootNode rootNode;

    public Node(int value) {
        data = value;
    }
}

class RootNode {
    /**
     * 顶点值
     */
    String  data;

    /**
     * 下一节点
     */
    Node next;

    public RootNode(String value) {
        data = value;
    }
}

图的深度优先遍历

所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历

深度优先遍历基本思想

图的深度优先搜索(Depth First Search) 。

1.  深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解： 每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
   

2.  我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
   

3.  显然，深度优先搜索是一个递归的过程
   

深度优先遍历算法步骤

1. 输出v节点，并设置已访问

2. 依次检查邻接矩阵 第v 行 有没有没被访问的节点， 值!=0 且 visited = false

3. 当检测到未被访问的节点时，以w为初始节点进行递归。

package Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author lixiangxiang
 * @description
 * @date 2021/8/6 16:49
 */
public class Graph {

    /** 边 */
    private int[][] edges;
    /**
     * 边数
     */
    private int numOfEdges;
    /**
     * 顶点集合
     */
    private List<String> vertexList;

    /**
     * 记录是否被访问过
     */
    private boolean[] isVisit;

    public static void main(String[] args) {
        int n = 8;  //结点的个数
        String vertexs[] = {"A", "B", "C", "D", "E"};

        //创建图对象
        Graph graph = new Graph(vertexs.length);
        //循环的添加顶点
        for(String vertex: vertexs) {
            graph.addVertex(vertex);
        }
		//添加边
        graph.insertEdge(0, 1, 1);
		graph.insertEdge(0, 2, 1);
		graph.insertEdge(1, 2, 1);
		graph.insertEdge(1, 3, 1);
		graph.insertEdge(1, 4, 1);
		
        //显示储存图的二维数组
        graph.showGraph();
     
        //深度遍历
		graph.DFS(0);

    }

    /**
     * 添加顶点
     */
    public void addVertex(String vertex) {
        vertexList.add(vertex);
    }

    //构造器
    public Graph(int n) {
        //初始化矩阵和vertexList
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
        isVisit = new boolean[n];
    }

    /**
     * 显示图对应的矩阵
     */
    public void showGraph() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    /**
     * 根据下标获取数据
     * @param i
     * @return
     */
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

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



     /**
     * description:
     *
     * @author: lixiangxiang
     * @param index 初始被访问的节点
     * @return void
     * @date 2021/8/7 16:30
     */
    public void DFS(int index) {
        //输出当前节点
        System.out.print(getValueByIndex(index)+"->");
        //设置为已访问
        isVisit[index] = true;
        //依次检查邻接矩阵 index所在的行有没有没被访问的节点，(每行 index之前的节点其实都已经被访问过，我们无需再检查)
        for (int w = index+1; w < edges[index].length; w++) {
            //如果下标为w的节点未被访问，递归调用DFS
            if (edges[index][w]!=0 && !isVisit[w]) {
                DFS(w);
            }
        }
    }
    
   
}

DFS 算法效率分析

用邻接矩阵来表示图，遍历图每一个顶点都要从头扫描该顶点所在行，时间复杂度O(n2)

用邻接表来表示图，虽然有2e个表节点，但只需扫描e个节点即可完成遍历，加上访问n个头节点的时间，时间复杂度为O(n+e)

• 稠密图适用于在邻接矩阵上进行深度遍历
• 稀疏图使用与在邻接表上进行深度遍历。

非连通图的遍历

从一个节点进行深度优先遍历后，再判断哪些顶点仍未被遍历到，从这些顶点开始再继续遍历

/**
     * description: 处理无向图问题
     *
     * @author: lixiangxiang
     * @param index 开始节点
     * @return void
     * @date 2021/8/7 17:11
  */
public void unConnectDFS(int index) {
        //按给定开始节点进行深度优先遍历
        DFS(index);
        //对所有没有遍历过的节点再次进行DFS搜索。
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisit[i]) {
                DFS(i);
            }
        }
 }