圖論筆記

圖,由點與邊組成。

圖的種類

無向圖:可以從 u 走到 v 也能走回來。
有向圖:這條邊允許從 u 走 到 v,但不能往回走。

擁有以下特徵之一的稱為樹(Tree)

連通 且 V = E + 1。
兩點間存在唯一的簡單路徑。 (意即不可刪任意條路徑)
沒有環,但加上任意一條邊就有環。
若節點編號存在順序,除了根,每個節點都伸出一條邊連到父節點。

vector<int>tree[1024];
int main()
{
    int n, a, b;
    cin >> n;
    while(n--)
    {
        cin >> a >> b;
        tree[a].emplace(b);
        tree[b].emplace(a);
    }
}

相關名詞

根 : 最上層的點
節點 : 储存的每筆資料
葉 : 最下層的點
父節點 : 現在節點上方直連點
子節點 : 現在節點下方連結的點
祖先 : 父節點之上的點,意旨向下dfs可以找到現在節點

存樹

以下介紹後面會使用的方法
主要是記下兩點關係,
像是 a 跟 b 相連,就讓 a 的陣列中存入 b。
利用動態陣列(vector)的特性,
只須不斷把點兩點的關係丟入。
當然也可以選擇開struct。

遍歷樹—DFS

走一點,走到不能再走為止。
再來會回到上一點,重複動作。
以遞迴執行。

vector<int>tree[1024];
bool vis[100005]; //紀錄是否走過以避免重複走造成的無限迴圈
void dfs(int x)  
{
    vis[x] = 1;   
    for(int i : tree[x].first)
    {
        if(!vis[i])
            dfs(i);
    }
    
}

遍歷—BFS

走完所有子節點,同時將該點的子節點存入queue,不斷循環。

vector<int>vec[100005];
queue &lt;int>que;
bool vis[100005];
void bfs(int x)
{
    vis[x] = 1;
    que.emplace(x); 
    while(!que.empty)
    {
        int front = que.front();
        que.pop();
        for(int i : vec[front]) //走完所有子節點
        {
            if(!vis[i]) //避免鬼打牆
            {                
                vis[i] = 1,
                que.emplace(i);
            }
        }
    }
}

紀錄父節點

方法是由dfs、bfs遍歷時,直接記錄下來。
下方提供dfs版:

vector<int>vec[1024];
bool visable[1024];
int parent[1024];
void dfs(int x)
{
    visable[x] = 1;
    for(int i:visable[x])
    {
        if(!visable[i])
        {
            visable[i] = 1;
            parent[vis[i]] = x;
        }
    }
}

某點最遠點

用 dfs 特性看深度,不斷刷新最遠值。

vector<pair<int, int> >vec[1024];
bool vis[1024];
pair<int, int>far;
void dfs(int x, int dis, int ord)
{
    vis[x] = 1;
    for(pair&lt;int, int> i:vec[x])
    {
        if(!vis[i.first])
        {
            vis[i.first] = 1;
            if (dis + i.second > far.second) //刷新最遠點
            {
                far.first = x, 
                far.second = dis;
            }
            dfs(i.first, dis + i.second);
        }
    }
}

樹直徑

先找任一點的最遠點,該點的最遠點與該點將會組成樹的直徑,
也就是相離最遠的兩點。

題源TOJ 378 (https://toj.tfcis.org/oj/pro/378/)
void dfs(int x, int dis)
{
    vis[x] = 1;
    
    for(pair<int, int> cld:node[x])
    {
        if(!vis[cld.first])
        {
            vis[cld.first] = 1;
            dis += cld.second;
            if(dis > far[ord].second)
            {
                far[ord].first = cld.first;
                far[ord].second = dis;
            }
            dfs(cld.first, dis);
            dis -= cld.second;
        }
    }
}
int main()
{
    int m, n;
    cin >> m >> n;
    while(n--)
    {
        int a, b, cost;
        cin >> a >> b >> cost;
        node[a].push_back({b, cost});
        node[b].push_back({a, cost});
    }
    dfs(0, 0);        
    memset(vis, 0, sizeof(vis));
    ord++;
    dfs(far[0].first, 0);    
    memset(vis, 0, sizeof(vis));
    cout << far[1].second << "\n"; 
}
本文採用 BY-NC-NC CC 條款授權,如無特別註明均為原創,轉載請註明出處「杜 靖智 來自 Cotpear」 及本文網址。
本文網址: https://www.cotpear.com/2020/06/blog-post-html/
暫無評論

發怖評論 編輯評論


上一篇
下一篇