图算法(一)—深入理解深度优先搜索
in 数据结构 with 0 comment

图算法(一)—深入理解深度优先搜索

in 数据结构 with 0 comment

基于实现无向图的API
由浅入深理解深度优先搜索算法
分析深度优先搜索解决的单点路径问题,连通性问题,二分色问题

无向图

  1. 无向图即为由边(edge)和顶点(vertex)组成的图模型。
  2. 图的几种表示方法(使用哪种数据结构表示图)
    1>邻接矩阵:

V*V的boolean矩阵,相连则true,这种数据结构对于上百万个顶点,空间需求太大。
2>边的数组:
使用一个边(edge)类,含有两个顶点变量。但是这种数据结构不能检查图所有的边。
3>邻接表数组
每个顶点都构造一个以顶点为索引的列表数组,数组中的元素都是和顶点相连的。下面的实现均是这种数据结构。

  1. 基于邻接表实现的图的性能分析
    1>使用空间和V+E成正比。

2>当增加一条边时,所需时间为常数。
3>遍历某个顶点的所有相邻顶点时,所需时间和V的度数成正比(处理每个相邻点所需时间为常数)
所以,结合三个分析:
基于以上操作的实现,邻接表性能趋向最优。

  1. 实现(Java)
package graphTheory;

import java.io.*;
import java.util.*;
/**
  * @author : luoz 
  * @date time:2016年9月16日 下午3:52:06 
**/
public class Graph {

    //vertex number
    private int V;
    
    //edge number
    private int E;
    
    //adjacency number    
    private Bag<Integer>[] adj;
    
    //FileIO
    FileIO fileio;
    
    /**
     * set up a graph and vertexs number are V.
     * @param V
     */
    public void Graph(int V)
    {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for(int v = 0;v<V;v++)
        {
            adj[v] = new Bag<Integer>();
        }
    }
    /**
     * read edge and vertex from a file and file name is Graph.txt
     * read String s from file,and the String data structure like:1 2,3 4,2 3,...
     */
    public void Graph()
    {
        fileio = new FileIO();
        String s = fileio.characterReader(new File("Graph.txt"));
        String[] st = s.split(",");
        int E = st.length;
        for(int i = 0;i<E;i++)
        {
            String[] str = st[i].split(" ");
            addEdge(Integer.parseInt(str[0]),Integer.parseInt(str[1]));            
        }
        
    }
    public int V(){
        return V;
    }
    
    public int E(){
        return E;
    }
    
    /**
     * add the vertex to the list.
     * @param v
     * @param w
     */
    public void addEdge(int v,int w)
    {
        adj[v].add(w);
        adj[w].add(v);
        E++;        
    }
    
    public Iterable<Integer> adj(int v)
    {
        return adj[v];
    }
}

深度优先搜索

  1. 思想
    走迷宫策略:按着通道(边),一直走未走过的,当遇到已经走过(标记过)的,则返回(递归)上一个路口(顶点),走这个路口的另外通道。走的过程中,用一个绳子标记已经走过的路(path)。

如图:
深度优先搜索
由图,红色是搜索路径(path),根据邻接表的顺序一直走下去,直到遇到没路或者走过的路,则返回。

  1. 实现(Java)
package graphTheory;

import java.util.Stack;

/**
  * @author : luoz 
  * @date time:2016年9月18日 上午9:20:34 
**/
public class DepthFirstSearch {
    
    //the vertex is called dfs()
    private boolean[] marked;
    //first vertex to last vertex way
    private int[] edgeTo;
    //the start point
    private final int s;
    
    public boolean marked(int w)
    {
        return marked[w];
    }
    
    public boolean hashPathTo(int v){
        return marked[v];
    }
    
    //method:set up a DepthFirstSearch
    public DepthFirstSearch(Graph G,int s){
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G,s);
    }
    //resursion for G to get the DepthFirstSearch
    private void dfs(Graph G,int v)
    {
        marked[v] = true;
        for(int w:G.adj(v))
            if(!marked[w])
            {
                edgeTo[w] = v;
                dfs(G,w);
            }
    }
    
    public Iterable<Integer> pathTo(int v)
    {
        if(!hashPathTo(v))
            return null;
        Stack<Integer> path = new Stack<Integer>();
        for(int x = v; x != s;x= edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }
}

广度优先搜索

  1. 单点路径
    给定一个图和一个顶点,是否存在该顶点到目标顶点的路径,存在则输出。

实现:即上一份API的实现方法pathTo()

  1. 是否为无环图
    给定的的图,是否为无环图?

实现:既然是判断,必然需要增加boolean型变量:hashCycle

    public void Cycle(Graph G)
    {
        marked = new boolean[G.V()];
        for(int s = 0;s <G.V();s++)
        {
            if(!marked(s))
                cdfs(G,s,s);
        }
    }
    
    private void cdfs(Graph G,int v,int u)
    {
        marked[v] = true;
        for(int w : G.adj(v))
        {
            if(!marked[w])
                cdfs(G,w,v);
            else if(w != v)
                hashCycle = true;
            
        }
    }
    
    public boolean hashCycle()
    {
        return hashCycle;
    }
  1. 双色问题(二分图)
    能否用两种颜色将图的所有顶点着色,使得任意一条边的两个顶点都为不同颜色?(这是否为一个二分图)

实现:

    public void TwoColor(Graph G)
    {
        marked = new boolean[G.V()];
        color = new boolean[G.V()];
        for(int s = 0;s<G.V();s++)
        {
            if(!marked[s])
                colorDFS(G,s);
        }
    }
    
    private void colorDFS(Graph G,int v)
    {
        marked[v] = true;
        for(int w : G.adj(v))
        {
            if(!marked[w])
            {
                color[w] = !color[v];
                colorDFS(G,w);
            }
            else if(color[w] == color[v])
                isTwoColor = false;
        }        
    }
    
    public boolean isTwoColor()
    {
        return isTwoColor;
    }

算法第四版

Responses