有向圖 & 無向圖環判斷

公司成天坑爹考試；不過我下個月才考。閑來無事，寫個算法玩玩。

PS，公司坑爹，不讓用stl；是以用一個數組來替代stl::stack。

++++++++++++++++++++++++++++++++++++

#無向圖

無向圖比較簡單，隻需要用一個輔助的 Visit 資料記錄點是否被通路過即可。

#include <iostream>
//#include <stack>

using namespace std;

#define T_LEN 301

int Answer;    //0: has no circle; 1: has circle;
int N, E;    //N: number of point; E: number of edge;
int Edge[T_LEN][T_LEN];
int Visit[T_LEN];    //has been visited or not
//stack<int> SCircle;
int SCircle[T_LEN];    //store the circle
int g_index;    //key point of circle (position)
int g_circle_item;    //the key point of circle (value)

//trave Graphic from '_index';
//if has circle, return 1; else, return 0 to continue;
int TVisit(int _index)
{
    int res = 0;
    int j;
    int ind = _index;

    if (1 == Visit[ind])
    {
        res = 1;
    }
    else
    {
        Visit[ind] = 1;
        SCircle[g_index++] = ind;
        for (j = 1; j <= N; j++)
        {
            if (1 == Edge[ind][j])
            {
                Edge[ind][j] = Edge[j][ind] = 0;
                if (1 == Visit[j])
                {
                    res = 1;
                    SCircle[g_index] = j;
                    g_circle_item = j;
                    break;
                }
                else
                {
                    if (TVisit(j) == 1)
                    {
                        res = 1;
                        break;
                    }
                    else
                    {
                        //popup stack
                        SCircle[g_index-1] = 0;
                        g_index--;
                    }
                }
            }
        }
    }
    return res;
}

void TCase(int _index)
{
    int i, j;
    int a, b;

    //input & init
    cin >> N >> E;
    for (i = 1; i <= N; i++)
    {
        Visit[i] = 0;
        SCircle[i] = 0;        
        for (j = 1; j <= N; j++)
        {
            Edge[i][j] = 0;
        }
    }
    for (i = 0; i < E; i++)
    {
        cin >> a >> b;
        Edge[a][b] = Edge[b][a] = 1;
    }
    g_index = 0;
    //processing
    for (i = 1; i <= N; i++)
    {
        if (Visit[i] == 0)
        {
            //has not visited; then traverse the graphics from 'i';
            Answer = TVisit(i);
            if (Answer == 1)
            {
                //print circle
                j = g_index - 1;
                while (SCircle[j] != g_circle_item)    j--;
                for (; j <= g_index; j++)
                {
                    cout << SCircle[j] << " ";
                }
                break;
            }
        }
    }
}

int main(void)
{
    int i, T;

    freopen("graphics.txt", "r", stdin);
    cin >> T;
    for (i = 0; i < T; i++)
    {
        cout << "Case " << i + 1 << "# ";
        Answer = 0;
        TCase(i);
        cout << ( (Answer == 1) ? "has " : "has no " ) << "circle" << endl;        
    }
    return 0;
}

++++++++++++++++++++++++++++++++++++

#有向圖

一開始也嘗試用DFS的方式（和無向圖一樣）來判斷環，但發現還是有一些差别的。

後來搜了下，才知道每個頂點的狀态不對。

圖中的一個節點，根據其C[N]的值，有三種狀态：
    0，此節點沒有被通路過
    -1，被通路過至少1次，其後代節點正在被通路中
    1，其後代節點都被通路過。

    按照這樣的假設，當按照DFS進行搜尋時，碰到一個節點時有三種可能：
    1、如果C[V]=0，這是一個新的節點，不做處理
    2、如果C[V]=-1，說明是在通路該節點的後代的過程中通路到該節點本身，則圖中有環。
    3、如果C[V]=1，類似于2的推導，沒有環。

#include <iostream>
//#include <stack>

using namespace std;

#define T_LEN 301

int Answer;    //0: has no circle; 1: has circle;
int N, E;    //N: number of point; E: number of edge;
int Edge[T_LEN][T_LEN];
int Visit[T_LEN];    //has been visited
//stack<int> SCircle;
int SCircle[T_LEN];
int g_index;
int g_circle_item;

//trave Graphic from '_index';
//if has circle, return 1; else, return 0 to continue;
int TVisit(int _index)
{
    int res = 0;
    int j;
    int ind = _index;

    Visit[ind] = -1;

    SCircle[g_index++] = ind;

    for (j = 1; j <= N; j++)
    {            
        if (1 == Edge[ind][j])
        {
            if (Visit[j] == -1)
            {
                //find circle
                res = 1;
                SCircle[g_index] = j;
                g_circle_item = j;
                goto TVisit_END;
            }
            else if (Visit[j] == 0)
            {
                //has no visited
                if (TVisit(j) == 1)
                {
                    res = 1;
                    goto TVisit_END;
                }
                else
                {
                    SCircle[g_index - 1] = 0;
                    g_index--;
                }
            }            
        }
    }//for
    Visit[ind] = 1;

TVisit_END:
    return res;
}

void TCase(int _index)
{
    int i, j;
    int a, b;

    //input & init
    cin >> N >> E;
    for (i = 1; i <= N; i++)
    {
        Visit[i] = 0;
        SCircle[i] = 0;        
        for (j = 1; j <= N; j++)
        {
            Edge[i][j] = 0;
        }
    }
    for (i = 0; i < E; i++)
    {
        cin >> a >> b;
        Edge[a][b] = 1;
    }
    g_index = 0;
    //processing
    for (i = 1; i <= N; i++)
    {
        if (Visit[i] == 0)
        {
            //has not visited; then traverse the graphics from 'i';
            Answer = TVisit(i);
            if (Answer == 1)
            {
                //print circle
                for (j = 0; j <= g_index;j++)
                    cout << SCircle[j] << " ";
                break;
            }
        }
    }
}

int main(void)
{
    int i, T;
    freopen("graphics_ex.txt", "r", stdin);
    cin >> T;
    for (i = 0; i < T; i++)
    {
        cout << "Case " << i + 1 << "# ";
        Answer = 0;
        TCase(i);        
        cout << ( (Answer == 1) ? "has " : "has no " ) << "circle" << endl;        
    }

    return 0;
}

轉載于:https://www.cnblogs.com/bouygues/p/4664985.html

有向圖 &amp; 無向圖 環判斷

有向圖 & 無向圖環判斷