閉路搜尋

#include <conio.h>
#include <cstdarg>
#include <cstdio>
#include "global.h"


#define _STACK_CHECK_BOUNDARY_
template <class T, int N=512>
class Stack
{
    T& err (int n) {
        static char* s[] = {
            "Overflow","Underflow",
            "Out of range","Empty"
        };
        puts (s[n]); getch(); 
        return d[0];
    }
public:
    T d[N];                //資料項
    int n;                 //元素個數  
    Stack()      { reset(); } 
    void reset() { n = 0; }

#ifdef _STACK_CHECK_BOUNDARY_
    void push (T x)       { if (n<N) d[n++] = x; else err(0);}
    T pop()               { return n? d[--n]: err(1); }
    T& operator*()        { return n>0? d[n-1]: err(3); }
    T& operator[] (int i) { return 0<=i&&i<n? d[i]: err(2); }
#else
    void push (T x)       { d[n++] = x; }
    T pop()               { return n? d[--n]: *d; }
    T& operator*()        { return d[n-1]; }
    T& operator[] (int i) { return d[i]; }
#endif
};


//------------------------------------------------------------
// 使用方式:
//
//   1. 先 reset
//   2. 以 add_vertex 依序由 0~N 號配置頂點
//   3. 用 add_edge 加入目前點的外接點群
//   4. 重複 2 3 步直到配置完畢
//
//------------------------------------------------------------

struct Graph                        //圖形結構
{
    enum {
        MAX_V  = 256,               //節點最大個數
        MAX_ES = 4096               //Edge Stack 的容量
    };
    struct Vertex {
        int* edge;                  //鄰接點群
        int  nEdge;                 //鄰接邊數 (接出去的邊數)
    };
    
    Vertex  V [MAX_V];              //Vertex stack
    int     nV;                     //目前的頂點數
    int     curV;                   //目前正在做設置的頂點編號
    int     ES[MAX_ES];             //Edge Stack
    int     nES;                    //目前的邊線數

    void reset ()
    {
        nV = nES = 0;
    }

    void add_vertex (int id)        //id 為欲設置的頂點編號
    {
        curV = id;
        if (id != nV) 
            ERROR_MSG3_("頂點設置錯誤: %d 應為 %d", id, nV);
        V[curV].edge  = &ES[nES];
        V[curV].nEdge = 0;
        nV++;
    }

    void add_edge (int id)          //id 為欲外接的頂點編號
    {
        V[curV].nEdge++;
        ES[nES++] = id;
    }

    void add_edges (int v, int n...)
    {
        add_vertex (v);
        va_list p;
        va_start (p, n);
        while (n-- > 0) 
            add_edge (va_arg (p, int));
    }

    void print_edges ()
    {
        int i, j;
        for (i=0; i<nV; ++i) {
            printf ("\n %2d: ", i); 
            for (j=0; j<V[i].nEdge; ++j)
                printf ("%2d ", V[i].edge[j]); 
        }
    }
};



//------------------------------------------------------------
// 閉路搜尋: 
//
//     使用 Tarjan 算法尋找 strongly connected nodes
//     並略去元素個數為 1 或 2 的解 
//
//------------------------------------------------------------

class FindLoops                         //閉路搜尋算法
{
    typedef Stack<int,Graph::MAX_ES> TStack; 

    Graph::Vertex* V; 
    TStack  stack;                      //保存正被遍歷的頂點群
    int     visit    [Graph::MAX_V];    //存放頂點的 DFS 拜訪次序
    bool    bInStack [Graph::MAX_V];    //標示頂點是否在 stack 中
    int     order;                      //目前的拜訪次序

    void tarjan (int v)                 //傳入起始節點編號
    {
        static int cur;
        int  min = visit[v] = order++;  //min 存放頂點可追溯到的
                                        //最前頂點的拜訪次序
        int  t;
        int  n = V[v].nEdge;
        int* e = V[v].edge;
        
        stack.push (v);
        bInStack[v] = true;

        while (n-- > 0) {
            t = *e++;                   //取出鄰接點編號
            if (visit[t] == -1)         //以 DFS 拜訪鄰接點
                tarjan (t);
            else cur = visit[t];
            if (bInStack[t] && cur < min) 
                min = cur;
        }
        if (visit[v] == min) {
            puts ("");
            do printf ("%2d ", t=stack.pop()),
               bInStack[t] = false;
            while (t != v);
        }
    }
public:

    void operator() (Graph& graph)
    {   
        stack.reset();
        V = graph.V;
        order = 0;                //-1 = 未被拜訪
        memset (visit, -1, sizeof visit);
        for (int i=0; i<graph.nV; ++i)
            if (visit[i] < 0)                 
                tarjan (i);            
    }
};