一、圖的概念 1、基本概念

圖 (Graph) 是一個二元組 G =( V(G), E(G) )?。其中V(G)是非空集，稱為 點集 (Vertex set) ，對于?V?中的每個元素，我們稱其為 頂點 (Vertex) 或 節(jié)點 (Node) ，簡稱 點?；E(G)?為?V(G)?各結(jié)點之間邊的集合，稱為 邊集 (Edge set) 。圖的節(jié)點數(shù)也被稱作圖的階。

只為您設(shè)計更接底氣、較有營銷力的好網(wǎng)站，將營銷策劃與網(wǎng)頁設(shè)計互相結(jié)合的專業(yè)機構(gòu)，營銷型網(wǎng)站公司中較早掌握HTML5技術(shù)的機構(gòu)。一個好的品牌網(wǎng)站制作，不能只是一張名片，茫茫網(wǎng)海，想要快速吸引到您客戶的眼球，必須全方位的展現(xiàn)出企業(yè)突出的優(yōu)勢，以求達到主動營銷的效果，最終促成成交！

? 常用?G=(V,E) 表示圖。

有限圖：V, E 都是有限集合

無限圖：V 或 E 是無限集合

無向圖：邊的兩點u，v 是無序二元組。即 u?可以到 v，v?也可以到 u；

???邊稱為無向邊；u，v 稱為邊 e 的端點。

有向圖：邊的兩點u，v 是有序二元組。即 u?可以到 v，v?卻不能到 u；

???邊稱為有向邊；u 稱為邊的起點，v稱為邊的終點，共稱端點。

并稱 u 是 v 的直接前驅(qū)，v 是 u 的直接后驅(qū)。

混合圖：既有無向邊，又有有向邊。

賦權(quán)圖：邊帶有權(quán)值。如果權(quán)都為正實數(shù)，則程圖為正權(quán)圖。

形象地說，圖是由若干點以及連接點與點的邊構(gòu)成的。

?另有 概念：點與點鄰接（鄰域）

點與邊關(guān)聯(lián)

頂點的度（入度，出度）

自環(huán)，重邊

路徑，跡，回路，環(huán)

連通性（強聯(lián)通與弱聯(lián)通）

? 及圖種類：簡單圖，多重圖，稀疏圖，稠密圖

? 特殊的圖：完全圖，鏈，樹

二、圖的三類儲存及遍歷方式 1、數(shù)組存圖

當圖中兩點相連時，用二維數(shù)組 a [?i ] [ j ] 表示 i 連向?j 點。無向圖 a [?i ] [ j ]、 a [ j?] [ i?]各存一次即可。數(shù)組存圖空間占用較多。

m條邊的存圖：

for(int i=1;i<=m;++i)
{
    int x,y,val;
    scanf("%d%d%d",&x,&y,&val);// x與 y相連，邊權(quán)值為val
    a[x][y]=val;//有向圖存一次即可
    a[y][x]=val;
}

遍歷和每個點相連的所有邊：

for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    {
        if(a[i][j])
            printf("%d->%d:%d\n",i,j,a[i][j]);
        // i 連 j ，且權(quán)值為 a[i][j]
    }

2.vector 存圖

? 數(shù)組存圖有大量空間冗余，vector 可減少空間的浪費。

m條邊的存圖：

vectorg[100],w[100];//g存點  w存邊權(quán)值
for(int i=1;i<=m;++i)
{
	int x,y,val;
	scanf("%d%d%d",&x,&y,&val);// x連 y  邊權(quán)為val 
	g[x].push_back(y);w[x].push_back(val);
	g[y].push_back(x);w[y].push_back(val);
	//有向圖，存一條即可 
}

遍歷和每個點相連的所有邊：

for(int i=1;i<=n;++i)
{
	for(int j=0;j%d:%d\n",i,g[i][j],w[i][j]);
            // i連 g[i][j],且邊權(quán)為 w[i][j]
}

3、鏈式前向星

對邊建立編號，按編號索引。

方式：

??? 對于一個點，當一條邊與這個點相連時，標記此邊的編號，之后與此點相連的邊與該邊共同以鏈表形式存儲。由此，我們可快速找到與某一點相連的邊，進一步推出由此延伸出的點。

具體的：

用結(jié)構(gòu)體存邊，其包含：連接同一個點的下一條邊編號next，指向的另一個點to，邊權(quán)值val。

? 用 h [ u ] 表示與點 u 相連的第一條邊的編號。

存邊：

struct node
{
	int next,to,val;
}edg[10010];// 存邊
int cnt;//邊的編號
int h[10010];//h[u]:指向和 u點相連的第一條邊編號
void add(int u,int v,int val)
{
	++cnt;//對該邊進行編號
	edg[cnt].next=h[u];//新邊的下一條邊是上一個"第一條邊"
	edg[cnt].to=v;//該邊相連的另一個點
	edg[cnt].val=val;
	h[u]=cnt;//新邊成為"第一條邊"  
}
int main()
{
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&val);
		add(x,y,val);
		add(y,x,val);//有向邊讀一次 
	}
}

遍歷和每個點相連的所有邊：

for(int i=1;i<=n;++i)
{
	if(h[i])//h[i]=0，說明該點沒有任何邊相連
	{
		for(int j=h[i];j;j=edg[i].next)
		{
			int v=edg[j].to,val=edg[j].val; 
		}
	}
}

再次注意：edg存的是邊本身，h [ u ] 存的是與 u 點相連的第一條邊的編號，edg[?].next存的是下一條邊的編號，edg[ ].to存的是此邊連接的另一個點。

? 邊的鏈表是不斷在鏈表前方而不是后方插入，注意首邊 h[ ]的更新。

三、例題

1.P8604 [藍橋杯 2013 國 C] 危險系數(shù) - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)

此題范圍較小，在此用矩陣存圖

解析：由題意得，關(guān)鍵點即為從 u 到 v 必須經(jīng)過的點。

將圖存在數(shù)組中，用 dfs 找出從 u 到 v 的路徑，對經(jīng)過的點進行標記。當找出所有路徑后，關(guān)鍵點每次都會被標記，被標記次數(shù)等于 u，v 兩點被標記的次數(shù)，統(tǒng)計有多少個這樣的點即可。

代碼：

#include#includeusing namespace std;
const int N=1005; 
int a[N][N];//矩陣存圖
int vis[N];
int cnt[N];//用于統(tǒng)計每個點被標記的次數(shù)
int ans;
int st,ed;
int n,m;
int tot;//統(tǒng)計有多少種路徑
void dfs(int k)
{
	
	if(k==ed)//已經(jīng)找到終點
	{
		++tot;//路徑數(shù)+1
		for(int i=1;i<=n;++i) if(vis[i]) ++cnt[i];//經(jīng)過的點
		return;
	}
	for(int i=1;i<=n;++i)//查找與 i相連的點
	{
		if(a[k][i]==1&&vis[i]==0)
		{
			vis[i]=1;dfs(i);vis[i]=0;
		}
	}
	
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=1;
		a[y][x]=1;
	}//矩陣存圖
	scanf("%d%d",&st,&ed);
	vis[st]=1;
	dfs(st);
	for(int i=1;i<=n;++i)
	{
		if(tot==cnt[i]) ++ans;
	}
	printf("%d",ans-2);
	return 0;
}

2.P3916 圖的遍歷 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)

采用vector存圖

解析：此題難點在于如何找出能到達的編號大的點。

如果按常規(guī)方法一一遍歷，那要進行n次搜索，時間復雜度高。

? 我們注意到當此點是編號大的點時，在該點前的所有點（即能到達該點的點）能到達的大編號就是這個點，這樣之前的點便不用再次遍歷，可以直接求得結(jié)果。

? 所以當存儲這個有向圖時，我們倒著存儲，把a[ u ][ v ] 的含義由 u 指向 v 變?yōu)?u 的上一個電是 v 。

代碼：

#include#include#include#includeusing namespace std;
vectorg[100010];// vector存圖
int n,m;
bool vis[100010];
int ans[100010];
void dfs(int a,int big)
{
	if(ans[a]) return;//a可以到達更大的點，已被記錄
	ans[a]=big;
	vis[a]=1;
	for(int i=0;i=1;--i)//倒序遍歷
	{
		if(ans[i]==0) dfs(i,i);//dfs（當前點，大點）
        //當該點沒有被記錄時，表明此點不能通向更大的點了，則以此點為大點遍歷
	}
	for(int i=1;i<=n;++i) printf("%d ",ans[i]);
	return 0;
}

3.P1330 封鎖陽光大學 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)

采用鏈式前向星存圖。

解析：

對于一個點，只有有河蟹和沒有河蟹兩種情況。

? 對于一條邊，要想被封鎖，兩個端點必須有一個是河蟹，且根據(jù)題意，兩邊不能都是河蟹，即兩端點的狀態(tài)不同。

? 目標是封鎖所有邊，那就設(shè)所有邊已被封鎖，由于點有兩種狀態(tài),我們可以將所有點分為狀態(tài)1和狀態(tài)2，有河蟹但不確定哪一點是河蟹，只需滿足一邊的兩點狀態(tài)不同即可。

? 具體的，對于未確定狀態(tài)的點，先確定一個狀態(tài)，再將它連接的其他所有點確定為另一個狀態(tài)；對于確定狀態(tài)的點，直接將連接的點確認為另一狀態(tài)，若在此過程中，另一點狀態(tài)已被確定且與此點相同，那么構(gòu)建失敗，輸出Impossible。此過程用dfs完成，一次dfs可以將相連的所有未確定狀態(tài)的點確定。確定狀態(tài)時統(tǒng)計每個狀態(tài)的個數(shù)，河蟹取較小的那個。

代碼：

#include#include#include#include
#includeusing namespace std;
struct node
{
	int nex,to;
}edg[200010];
int vis[10010];//存點狀態(tài)
int cnt;
int h[10010];
int n,m;
int ans;
int cnt1,cnt2;//用于統(tǒng)計每次dfs兩種狀態(tài)的點的個數(shù)
int f;
void add(int u,int v)
{
	++cnt;
	edg[cnt].nex=h[u];
	edg[cnt].to=v; 
	h[u]=cnt;
}//鏈式前向星存圖
void dfs(int u)
{
	for(int i=h[u];i;i=edg[i].nex)
	{
		int v=edg[i].to;//與 u相連的點
		if(vis[v]==vis[u]) {f=1;return;}//已確定且狀態(tài)相同
		if(vis[v]!=0) continue;
		if(vis[u]==1)//狀態(tài)翻轉(zhuǎn)
		{
			++cnt2;vis[v]=2;dfs(v);
		}
		if(vis[u]==2)
		{
			++cnt1;vis[v]=1;dfs(v);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	for(int i=1;i<=n;++i)
	{
		if(vis[i]==0)
		{
			++cnt1;vis[i]=1;
			dfs(i);
			if(f==1)
			{
				printf("Impossible");
				return 0;
			}
			ans+=min(cnt1,cnt2);
			cnt1=cnt2=0;//清空
		}
	}
	printf("%d",ans);
	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標題：Week5存圖-創(chuàng)新互聯(lián)
文章鏈接：http://chinadenli.net/article28/dgpgcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機網(wǎng)站建設(shè)、做網(wǎng)站、域名注冊、品牌網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計公司、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)