图算法（三）：两种基本图算法的应用实例

一、隐式图搜索

作用在解答树，是一种广度优先遍历的方法。解答树，或者更一般的状态图，在某些问题中规模本身是无限的，但是通常能嗅到如“最简单”，“最短”，“最少”等字眼，这就意味着广度优先遍历。

再回忆广度优先遍历的实现，由一个队列保存新发现的节点，并且有这样的距离关系：

新发现的节点与源节点的距离=其父节点与源节点的距离+1

广度优先遍历的实现：

#用字典保存一个图的邻接表形式
g = {'A': ['B', 'C'],
     'B': ['A', 'D', 'E'],
     'C': ['A', 'F', 'G'],
     'D': ['B', 'H'],
     'E': ['B', 'H'],
     'F': ['C', 'G'],
     'G': ['C', 'F'],
     'H': ['D', 'E']}

pi = {node: 0 for node in g.keys()} #父节点 
d = {node: 0 for node in g.keys()} #广度遍历的层次
visited = {node: 0 for node in g.keys()} #访问记录

def BFS(start):
    visited[start] = 1
    global q
    q = [] #队列，保存新发现的节点
    q.append(start)

    while len(q) > 0:
        v = q.pop(0)
        for w in g[v]:
            if  visited[w] == 0:
                visited[w] = 1
                pi[w] = v
                d[w] = d[v] + 1 #层次=父节点+1

                q.append(w)
        visited[v] = 2

def main():
    BFS('A')
    print pi

例一、最优程序问题

 有一台只有一个数据栈的计算机，支持ADD, SUB, MUL, DIV, DUP五种运算。设栈顶元素分别为a, b, c，五种运算的效果如下：　

ADD: a, b依次出栈，就算a+b，结果压栈

SUB: a, b依次出栈，就算b-1，结果压栈　

MUL: a, b依次出栈，就算a*b，结果压栈

DIV: a, b依次出栈，就算a/b，结果压栈

DUP: a出栈，再连续把两个a压栈

遇到一下情况，发生错误：执行DIV操作时，栈顶元素为0；执行ADD, SUB, MUL, DIV操作时栈中只有一个元素

问题：输入(a,b)，设计一个最短的程序，使得执行前栈中只有元素a，执行后栈顶元素是b

分析：

　　粗略看，这里有一个解答树，是一个五叉树。但是如果没有明显的叶子节点，无法回溯。有注意到最短这个关键词，因此本题用广度优先的方法。

问题的难点在于怎么表示这个状态图呢？状态图中的节点有这样几个属性：pre(历史操作)，下一步操作，stack（当前的栈状态）。

　　遍历过程由源节点出发，在每一个当前节点，计算下一步操作改变栈状态后，扩展下一层节点入队列。退出条件无疑是当前节点计算下一步操作后等于目标值。

程序：

import sys
import copy

name_dict = {0: "ADD", 1: "SUB", 2: "MUL", 3: "DIV", 4: "DUP"}

op_dict = {0: lambda a, b: a + b,
           1: lambda a, b: a - b,
           2: lambda a, b: a * b,
           3: lambda a, b: b / a}

class Node:
    def __init__(self):
        self.pre = [] #前缀操作
        self.op = -1 #下一次操作
        self.stack = [] #当前的栈情况

   
def op():
    n.pre.append(name_dict[n.op])

    if n.op != 4: 
        a = n.stack.pop()
        b = n.stack.pop()
        c = op_dict[n.op](a, b)
        n.stack.append(c)
    else:   
        a = n.stack.pop()
        n.stack.append(a)
        n.stack.append(a)

def main(): 
    global n1
    global n2
    global n
    global q

    for line in sys.stdin:
        line = line.rstrip()
        s = line.split(" ")
        n1 = int(s[0])
        n2 = int(s[1])

        n = Node()
        n.op = 4
        n.stack.append(n1)
                                                                                                   
        q = []  
        q.append(copy.deepcopy(n))

        while (len(q) > 0):
            n = q[0]
            q.pop(0)
            op()    
            if n.stack[-1] == n2:
                break                                                                              
                                                                                                   
            for i in range(4):
                if len(n.stack) < 2:
                    continue
                if i == 3 and n.stack[-1] == 0:
                   continue 
                n.op = i
                q.append(copy.deepcopy(n))     
                                                                                                   
            n.op = 4
            q.append(copy.deepcopy(n))
        
        for opp in n.pre:
            print opp

        print

if __name__ == '__main__':
    main()    

二、拓扑排序

　　拓扑排序是深度优先遍历的一个例子。拓扑排序专门作用与有向无环图（DAG),可以用来描述事务图的因果关系,具体是经过拓扑排序的节点箭头指向均是向右

注意点:判断有向图是否成环,即判断是否有反向边.

例一、假设有4个变量abcd，若a<b, c<b, d<c，求在这些条件下可能的从小到大的排序

分析：这种从小到大的排序明显的方向性

#include<stdio.h>

int g[4][4];
int f[4];

int visit[4];

int counter = 3;

int dfs(int);

int main()
{
    int x;  
    g[0][1] = 1;
    g[2][1] = 1;
    g[3][2] = 1;
    g[1][3] = 1;

    for (x = 0; x < 4; x++) 
    {
        if (visit[x] == 0)
        {       
            if (dfs(x) == -1)
            {       
                printf("this is not a DAG
");
                return -1;
            }       
        }       
    } 
    for (x = 0; x < 4; x++) 
    {
        printf("%d ", f[x]);
    }
    return 0;
}

int dfs(int v)
{
    int w;  
    visit[v] = -1;
    for (w = 0; w < 4; w++) 
    {
        if (g[v][w] == 1)
        {       
            if (visit[w] == -1)
            {       
                //排除反向边的情况
                //拓扑排序只有在有向无环图中才有意义
                return -1;
            }else if (visit[w] == 0)
            {       
                if (dfs(w) == -1)
                {       
                    return -1;
                }       
            }       
        }       
    }
    visit[v] = 1;
    f[counter] = v;
    counter--;
}

但是，深度优先遍历最重要的应用还是回溯与递归