图的表示和应用

图的深度优先遍历 GraphDFS

public class GraphDfs {
    private AdjList graph;
    private ArrayList<Integer> list = new ArrayList<>();
    private boolean visited[];

    public GraphDfs(AdjList graph) {
        this.graph = graph;
        this.visited = new boolean[graph.getV()];
        for (int i = 0; i < graph.getV(); i++) {
            if (!visited[i])
                Dfs(i);
        }
    }

    private void Dfs(int v) {
        visited[v] = true;
        list.add(v);
        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                Dfs(w);
            }
        }
    }

    public ArrayList<Integer> getList() {
        return list;
    }
}

应用-联通分量个数

int count=0;
this.graph = graph;
this.visited = new boolean[graph.getV()];
for (int i = 0; i < graph.getV(); i++) {
    count++;
    if (!visited[i])
        Dfs(i);
}

应用-划分联通分量组

public GraphDfs(AdjList graph) {
    int count = 0;
    this.graph = graph;
    this.visited = new int[graph.getV()];
    for (int i = 0; i < visited.length; i++) 
        visited[i] = -1;
    for (int i = 0; i < graph.getV(); i++) 
        if (visited[i] == -1)
            Dfs(i, count++);
}

private void Dfs(int v, int count) {
    visited[v] = count;
    list.add(v);
    for (int w : graph.adj(v)) 
        if (visited[w] == -1) 
            Dfs(w, count);
}

应用-判断两个点是否联通

public boolean isConnected(int v, int w) {
    graph.ValidateVertex(v);
    graph.ValidateVertex(w);
    return visited[v]== visited[w];
}

区别与使用图的邻接点的遍历方式判断

应用-求解单源路径

非最短路径，基于DFS遍历，将寻找结果缓存。

应用-判断是否有环路

private void Dfs(int v, int w) {//w为父亲节点
    from[v] = w;
    for (int next : graph.adj(v)) {
        if (from[next] == -1) {
            Dfs(next, v);
        } else if (next != w)//如果next节点遍历过，并且父亲节点不是next节点
            hasCycle = true;
    }
}

应用-判断是否为二分图

可参照leetcode分类中关于图论部分第一题

图的深度优先遍历 GraphBFS

public class GraphBFS {
    AdjList adjList;
    ArrayList<Integer> order = new ArrayList<>();
    boolean visited[];

    public GraphBFS(AdjList adjList) {
        this.adjList = adjList;
        visited = new boolean[adjList.getV()];
        for (int i = 0; i < visited.length; i++) {
            if (visited[i] == false)
                bfs(i);
        }
    }

    private void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        visited[v] = true;
        queue.add(v);
        while (!queue.isEmpty()) {
            Integer cur = queue.poll();
            order.add(cur);
            for (int next : adjList.adj(cur)) {
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }
}

应用-单源最短路径

相比DFS，可以求解出无权图的最短路径问题

应用-联通分量/是否联通/是否环路/二分图检测

同样的思路，不同的遍历顺序

---

• 分类： 数据结构与算法
• 标签： 计算机