本文最後更新於 468 天前,其中的資訊可能已有所進展或是發生改變。
圖,由點與邊組成。
圖的種類
無向圖:可以從 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 <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<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";
}