【每日一題】(31題)面試官:你對圖論了解多少?(一)

關注「松寶寫代碼」

精選好文，每日一題

作者：Overstarshttps://shuangxunian.gitee.io/2020/08/24/graphTheory/

2020，實「鼠」不易

2021，「牛」轉乾坤

風勁潮湧當揚帆，任重道遠須奮蹄！

一、前言

今天我們約來了 Overstars的圖論總結，ACM打比賽，他的方向是思維數論圖論。下文是他和他隊友四年刷圖論的總結。其實本身就是個筆記，以後方便打板子的。我們把整個總結分為多篇文章來發，歡迎關注「松寶寫代碼」每日一題。

原文地址：https://shuangxunian.gitee.io/2020/08/24/graphTheory/

2020.12.23 立的 flag，每日一題，題目類型不限制，涉及到JavaScript，Node，Vue，React，瀏覽器，http，算法等領域。

本文是：【每日一題】(31題)面試官:你對圖論了解多少？（一）

二、圖論

作者 Overstars

https://shuangxunian.gitee.io/2020/08/24/graphTheory/

1、常見概念

簡單圖：不含有平行邊和環的圖。

多重圖：含有平行邊（同向）的圖。

完全圖：每一對節點之間都有邊的簡單圖，$n$個節點無向完全圖記為$K_n$。

平面圖：能將所有點和邊畫在平面上，且邊與邊不相交的無向圖。

補圖：由$G$中所有節點和所有能使$G$成為完全圖的添加邊組成的圖。

生成子圖(Spanning Subgraph)：含有原圖$G$中所有結點的子圖。

圖同構的必要條件：

節點數相同。

邊數相同。

度數相同的結點數相同。

網絡流常用概念

連通圖：只有一個連通分支（極大連通子圖）的圖。

割點：無向連通圖中一個頂點$v$,，若刪除它以及關聯的邊後，得到的新圖至少包含兩個連通分支。

橋：無向連通圖中的一條邊$e$，刪除它得到的新圖包含兩個連通分量。

團(Clique)：原圖$G$的一個完全子圖。

極大團(Maximal Clique)：不是其它團的子圖的團。

最大團(Maximum Clique)：頂點最多的極大團。

誘導子圖(Induced Subgraph)：所有節點在原圖$G$上連接的邊都被包含在內的子圖。

獨立集：在圖上選出一些節點，這些節點間兩兩無邊的點集。

路徑覆蓋：在圖中找一些路徑，這些路徑覆蓋圖中所有的頂點，每個頂點都只與一條路徑相關聯。

最小染色數：用最少的顏色個數給點染色且任意兩點相鄰點顏色不同，最少的顏色個數。

弦圖常用概念

弦：連接環上兩個不相鄰節點的邊。

弦圖：圖上任意一個點數大於三的環都至少存在一條弦的無向圖。

單純點：節點$v$與相鄰節點的誘導子圖是一個團。

完美消除序列：有$n$個點的排列$v1,v2,\dots,vn$，該排列滿足$vi$在${vi,v{i+1},\dots,v_n}$的誘導子圖中是一個單純點。

一個無向圖是弦圖若且唯若它有一個完美消除序列

2、常見結論

每個圖中節點度數和等於邊數的二倍，$\sum\limits_{v\in V} deg(v)=2\left| E \right|$。

任何圖中度數為奇數的節點必定有偶數個。

完全圖$K_n$的邊數$=\frac{n(n-1)}{2}$

最大團中頂點數量 = 補圖的最大獨立集中頂點數量

最大團數 ≤ 最小染色數，最大獨立集 ≤ 最小團覆蓋

弦圖中：最大團數 = 最小染色數，最大獨立集 = 最小團覆蓋

平面圖邊數$m\le 3n-6$。

git config --global core.autocrlf false和git config --global core.safecrlf true還有git init

3、弦圖最大勢算法求消除序列並判定弦圖

判斷一個消除序列是否為完美消除序列：從後向前枚舉序列中的點$vi$，設序列中在$vi$後且與$vi$相鄰的點集依次為${v{j1},v{j2},\dots,v{jk}}$，判斷$vj1$是否與${v{j2},\dots,v_{jk}}$相鄰即可。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1005;

struct edge

{

int v,nex;

edge(int v=0,int n=-1):

v(v),nex(n){}

} e[maxn*maxn];

int cnt=0,head[maxn];

inline void add(int u,int v)

{

e[++cnt].v=v;

e[cnt].nex=head[u];

head[u]=cnt;

}

int label[maxn],id[maxn],order[maxn];//id[i]表示節點i在序列中的編號

bool vis[maxn];//order[i]為完美消除序列第i個節點,label[x]表示x點與多少個已標號節點相鄰

vector<int> vec[maxn];//vec[x]存儲*與x個已標號節點相鄰*的節點

void mcs(int n)//節點數量

{//複雜度O(n+m)

memset(vis,0,sizeof(vis));

memset(label,0,sizeof(label));

for(int i=1;i<=n;i++)

vec[0].push_back(i);

int maxx=0,now=0;

for(int i=1;i<=n;i++)

{//從前往後,每輪必定會找出一個

bool flag=0;

while(!flag)

{

for(int j=vec[maxx].size()-1;j>=0;j--)

{//從後往前找

if(vis[vec[maxx][j]])//該節點已經標記過

vec[maxx].pop_back();

else{

flag=1;//找到個未訪問的節點

now=vec[maxx][j];

break;

}

}

if(!flag)

maxx--;

}

vis[now]=1;//

order[n-i+1]=now;

id[now]=n-i+1;//節點x在序列中的位置

for(int j=head[now];~j;j=e[j].nex)

{//遍歷與now節點相鄰的節點

int v=e[j].v;

if(!vis[v])

{

label[v]++;//v節點與已標號節點數++

vec[label[v]].push_back(v);

maxx=max(maxx,label[v]);//找出最大的那個節點

}

}

}

}

int bucket[maxn];

bool isperfect(int n)

{//複雜度O(n+m)

mcs(n);//計算消除序列並判斷是否為完美消除序列

memset(vis,0,sizeof(vis));//判斷序列中的點v_i是否與其後所有點相接

for(int i=n;i>0;i--)//序列從後向前

{

int tot=0,ret=1;//每輪桶清空

for(int j=head[order[i]];~j;j=e[j].nex)

if(id[e[j].v]>i)//排在序列編號x後面與x相鄰的點集記為:N(x)

vis[bucket[++tot]=e[j].v]=1;//序列中x後且與x鄰接點標記並放入桶中

for(int j=head[bucket[1]];~j;j=e[j].nex)//buc[1]的id為N(x)中最小？

{//bucket[1]=0...

int v=e[j].v;

if(v!=bucket[1]&&vis[v])

{//判斷N(x)中排在最前面的點是否與N(x)其他點相鄰

ret++;

}

}

for(int j=1;j<=tot;j++)

vis[bucket[j]]=0;//防止每次memset超時

if(tot&&ret!=tot)//不全部鄰接

return 0;

}

return 1;

}

int main()

{

int n,m,u,v;

while(cin>>n>>m&&n&&m)

{

memset(head,-1,sizeof(head));

memset(order,0,sizeof(order));

cnt=0;

for(int i=1;i<=n;i++)

vec[i].clear();

for(int i=1;i<=m;i++)

{

cin>>u>>v;

add(u,v);

add(v,u);

}

cout<<(isperfect(n)?"Perfect\n\n":"Imperfect\n\n");

}

return 0;

}

4、三元環步驟

對原無向圖進行定向，對任何一條邊，從度數大的點連向度數小的點，如果度數相同，從編號小的點連向編號大的點。得到一個有向無環圖。

枚舉每一個節點$u$，將$u$所有相鄰節點打上$u$的標記。再枚舉$u$的相鄰節點$v$，枚舉$v$的相鄰節點的相鄰節點$w$，如果$w$上有被標記為$u$，則$(u,v,w)$就是一個三元環。

統計圖上三元環數量，複雜度$O(m\sqrt{m})$。

vector G[maxn];//新圖

int vis[maxn],deg[maxn];

int cycle3(int n)

{

int ans=0;

for(auto &e:edges)

{//統計原無向圖度數

deg[e.u]++;

deg[e.v]++;

}

for(auto &e:edges)//建立新圖

if(deg[e.u]<deg[e.v]||(deg[e.u]==deg[e.v]&&e.u<e.v))

G[e.u].push_back(edge(e.u,e.v));

else

G[e.v].push_back(edge(e.v,e.u));

for(int u=1;u<=n;u++)

{

for(int v:G[u])

vis[v]=u;//相鄰節點打上u的標記

for(int v:G[u])

for(int w:G[v])

if(vis[w]==u)

ans++;

}

return ans;

}

5、最短路Dijkstra堆優化

複雜度$O(ElgE)$，稠密圖中有時不如普通版優秀，但比SPFA快。

const int MAXN=1050;

struct qnode{

int v,c;

qnode(int _v=0,int _c=0):v(_v),c(_c){}

bool operator <(const qnode &r)const{

return c>r.c;//重載運算符<

}

};

struct Edge{

int v,cost;

Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}

};

vector<Edge>E[MAXN];//使用前必須清空0~n

bool vis[MAXN];

int dist[MAXN];//到這個點的最近隊員的

void Dijkstra(int n,int start)//傳入總數及起點

{//點的編號從 1 開始

memset(vis,false,sizeof(vis));

for(int i=1;i<=n;i++)

dist[i]=inf;

priority_queue<qnode>que;

while(!que.empty())

que.pop();

dist[start]=0;

que.push(qnode(start,0));

while(!que.empty())

{

qnode now=que.top();

que.pop();

int u=now.v;

if(vis[u])

continue;

vis[u]=true;

for(int i=0;i<E[u].size();i++)

{

int v=E[u][i].v;

int cost=E[u][i].cost;

if(!vis[v]&&dist[v]>dist[u]+cost){

dist[v]=dist[u]+cost;

que.push(qnode(v,dist[v]));

}

}

}

}

void addedge(int u,int v,int w)

{

E[u].push_back(Edge(v,w));

}

SPFA

最壞複雜度$O(VE)$，V為節點數，不適用於稠密圖

檢測負環：當存在一個點入隊大於等於$V$次，則有負環

BFS實現（求最短路）

const int inf=0x3f3f3f3f,MAXN=5051;

struct node

{

int v,w,next;

} e[MAXN];

int cnt,dist[MAXN],head[MAXN],num[MAXN];

bool vis[MAXN];

void add(int u,int v,int w)//鏈式前向星存圖,無向則雙向添加

{

e[cnt].v=v;//邊的結尾節點

e[cnt].w=w;

e[cnt].next=head[u];//去找以u為起始的上一個節點(相當於鍊表,起始為-1)

head[u]=cnt++;//保存該邊(最後的邊)在e[i]中的編號

}

bool SPFA(int n,int x)//節點數量n,起點編號x

{

memset(dist,inf,sizeof(dist));

memset(vis,0,sizeof(vis));

memset(num,0,sizeof(num));

dist[x]=0;//該題起點任意

num[x]++;//入隊次數++

queue<int> QAQ;

QAQ.push(x);

while(!QAQ.empty())

{

int now=QAQ.front();

QAQ.pop();

vis[now]=0;//從隊列中取出

for(int i=head[now];i!=-1;i=e[i].next)

{//遍歷以now開頭的所有邊,嘗試以x->now->to鬆弛x->to

int to=e[i].v;//嘗試鬆弛x->to的當前距離

if(dist[to]>dist[now]+e[i].w)

{

dist[to]=dist[now]+e[i].w;//成功用x->now->to鬆弛x->to

if(!vis[to])//x->to被成功鬆弛且to不在隊列

{

vis[to]=1;//標記to加入隊列

QAQ.push(to);

num[to]++;//to加入隊列次數++

if(num[to]>n)

return 1;//有負權迴路,無法求最短路徑

}

}

}

}

return 0;

}

DFS優化（負環檢測）

請先用前向星加邊。因為圖有可能不連通，檢測負環要枚舉每個起點。

bool spfa(int x)//DFS優化

{

vis[x]=1;

for(int i=head[x];~i;i=e[i].next){

int v=e[i].v;

if(dist[v]>dist[x]+e[i].w)//求最短路

{

dist[v]=dist[x]+e[i].w;

if(vis[v])//存在一點在一條路徑上出現多次，存在負權環

return 0;

if(!spfa(v))//搜到了存在負權環

return 0;

}

}

vis[x]=0;

return 1;//未找到負權環

}

Floyd

long long path[805][805];

void floyd(int n)//節點編號1~n

{

for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

if(path[i][k]+path[k][j]<path[i][j])

{//當i，j的原來的邊的最短距離，大於經過k點所到達的距離就替換

path[i][j]=path[i][k]+path[k][j];

}

}

謝謝支持

1、文章喜歡的話可以「分享，點讚，在看」三連哦。

2、作者暱稱：saucxs，songEagle，松寶寫代碼。「松寶寫代碼」公眾號作者，每日一題，實驗室等。一個愛好折騰，致力於全棧，正在努力成長的字節跳動工程師，星辰大海，未來可期。內推字節跳動各個部門各個崗位。

3、長按下面圖片，關注「松寶寫代碼」，是獲取開發知識體系構建，精選文章，項目實戰，實驗室，每日一道面試題，進階學習，思考職業發展，涉及到JavaScript，Node，Vue，React，瀏覽器，http等領域，希望可以幫助到你，我們一起成長～

字節內推福利

回復「校招」獲取內推碼

回復「社招」獲取內推

回復「實習生」獲取內推

後續會有更多福利

學習資料福利

回復「算法」獲取算法學習資料

往期「每日一題」1、JavaScript && ES62、瀏覽器3、Vue4、HTML55、算法6、Node7、Http

PS：閱讀原文看代碼更清爽