1.學(xué)習(xí)總結(jié)

1.1圖的思維導(dǎo)圖

1.2 圖結(jié)構(gòu)學(xué)習(xí)體會(huì)

• 深度遍歷算法（DFS）：一直往深處走，直到找到解或者走不下去為止；類似于樹的先序遍歷；利用遞歸（實(shí)質(zhì)上是用棧來(lái)保存未訪問的結(jié)點(diǎn)，先進(jìn)后出）來(lái)實(shí)現(xiàn)比較簡(jiǎn)單；
• 廣度遍歷算法（BFS）：利用隊(duì)列（用隊(duì)列來(lái)保存未訪問的結(jié)點(diǎn)，先進(jìn)先出）實(shí)現(xiàn)；類似于樹的層次遍歷；
• DFS 和 BFS 本質(zhì)區(qū)別：BFS 的重點(diǎn)在于隊(duì)列，而 DFS 的重點(diǎn)在于遞歸；
• Prim和Kruscal算法：尋找最小生成樹，求最短路徑；這兩種算法的核心是并查集；一個(gè)是選點(diǎn)，一個(gè)是選邊；當(dāng)題中邊的數(shù)目較為復(fù)雜時(shí)，選用prim算法；一般性問題，選kruscal算法，理解起來(lái)比較簡(jiǎn)單；
• Dijkstra算法：類似于Prim算法，唯一區(qū)別為：mindist[ ]的意義變?yōu)榱嗽c(diǎn)到其他點(diǎn)的距離；這種算法只能解決權(quán)值不是負(fù)的圖；特點(diǎn)：可以求出單源點(diǎn)到其他頂點(diǎn)的最短距離，算法的復(fù)雜程度比f(wàn)loyd算法稍微低一些；
• Floyd算法：時(shí)間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)；特點(diǎn)：可以求多源最短路，權(quán)值同樣不能為負(fù)；
• 拓?fù)渑判蛩惴?#xff1a;拓?fù)渑判蚴轻槍?duì)有向無(wú)環(huán)圖，基于隊(duì)列來(lái)統(tǒng)計(jì)入度，先選擇輸出入度為0的點(diǎn)，刪去該點(diǎn)及有關(guān)邊，再依次循環(huán)處理其余點(diǎn)的入度；
• 算法比較多，需要理解并記憶，圖比線性表和樹更復(fù)雜，存儲(chǔ)及遍歷都需要記住，簡(jiǎn)單操作如建圖、DFS、BFS；

2.PTA實(shí)驗(yàn)作業(yè)

2.1 題目1：7-1 圖著色問題

• 對(duì)給定的一種顏色分配，請(qǐng)你判斷這是否是圖著色問題的一個(gè)解；

2.2 設(shè)計(jì)思路

• void DFS(MGraph g,int v);//深度遍歷 void CreateMGraph(MGraph &g,int n,int e );//建圖
• 偽代碼：

    定義變量n、e、k分別是無(wú)向圖的頂點(diǎn)數(shù)、邊、顏色數(shù)定義數(shù)組 color[MAXV]={0}表頂點(diǎn)顏色并置零sum 記錄當(dāng)前顏色總數(shù)目 ,標(biāo)記變量 flag=0數(shù)組c[MAXV]表 顏色類型 for i=1 to n判斷著色,不同,sum++ 圖的遍歷：if(顏色數(shù)sum不等于K) 不符合flag=1else  通過鄰接矩陣判斷

2.3 代碼截圖

2.4 PTA提交列表說明

• 部分正確;圖不連通，DFS不重復(fù)訪問頂點(diǎn)的錯(cuò)誤，答案錯(cuò)誤，圖的建立需要頂點(diǎn)初始化，頂點(diǎn)、邊數(shù)要賦值好；
• 答案錯(cuò)誤；有小于K種顏色，題目中顏色數(shù)可能恰好相等，需要判斷sum！=k；

2.1 題目2：7-3 六度空間

• 假如給你一個(gè)社交網(wǎng)絡(luò)圖，請(qǐng)你對(duì)每個(gè)節(jié)點(diǎn)計(jì)算符合“六度空間”理論的結(jié)點(diǎn)占結(jié)點(diǎn)總數(shù)的百分比；

2.2 設(shè)計(jì)思路

• int g[MAXN][MAXN]; //建圖 int BFS(int i,int N); //對(duì)圖進(jìn)行廣度遍歷
• 偽代碼：

    雙精度double sum 記錄六度空間總數(shù) queue<int> Q;  //用隊(duì)列存放每層相鄰頂點(diǎn) 標(biāo)志數(shù)組 visit[MAXN]={0},層數(shù)level=0,tail記錄最后頂點(diǎn) 對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行BFS,獲取六度內(nèi)的結(jié)點(diǎn)數(shù)sumfor i=1 to N{頂點(diǎn)相連且該頂點(diǎn)未被訪問,入隊(duì),計(jì)數(shù) tail 更新}一層層BFS,直到 level==6 break 輸出: sum/(N*1.0)*100)   //%%才能輸出百分號(hào)

2.3 代碼截圖

2.4 PTA提交列表說明

• 在DEV-C運(yùn)行正確后提交無(wú)誤；
• 過程中錯(cuò)誤：圖初始化時(shí)，節(jié)點(diǎn)從1到N編號(hào)，圖是從0開始的 ；
• 定義一個(gè) last記錄當(dāng)前層訪問的最后一個(gè)節(jié)點(diǎn) ，查資料所得；%%才能輸出百分號(hào) ；

2.1 題目3：7-4 公路村村通

• 現(xiàn)有村落間道路的統(tǒng)計(jì)數(shù)據(jù)表中，列出了有可能建設(shè)成標(biāo)準(zhǔn)公路的若干條道路的成本，求使每個(gè)村落都有公路連通所需要的最低成本；

2.2 設(shè)計(jì)思路

• int g[MAX][MAX]; //建無(wú)向圖,以鄰接矩陣進(jìn)行存儲(chǔ) void Prim(int N); //普里姆算法
• 偽代碼：

定義數(shù)組 lowcost[MAX]存放最低成本 
定義變量 min,sum=0lowcost[1] //序號(hào)為1的頂點(diǎn)出發(fā)
for i=0 to N-1 //找出N-1個(gè)頂點(diǎn)即可 
{ min=INF;for(j=1;j<=N;j++) // 找生成樹距離最近的頂點(diǎn) 比min 小 更新K記錄最近頂點(diǎn) sum=sum+lowcost[k];
} 

2.3 代碼截圖

2.4 PTA提交列表說明

• 段錯(cuò)誤；M<N-1，不可能有生成樹 ，對(duì)一開始的頂點(diǎn)判斷，加上條件if(N<=0||M<N-1)；
• 答案錯(cuò)誤；最大N和M，連通，在Prim（）函數(shù)里面進(jìn)行判斷，加上if(i<=N) return -1；
• 答案錯(cuò)誤；M達(dá)到N-1，但是圖不連通，判斷最小為無(wú)窮，則表示不連通， if(min==INF) return -1，前面改的也要變化;

3.截圖本周題目集的PTA最后排名

3.1 PTA排名

3.2 我的總分：221

4. 閱讀代碼

• 二分圖匹配——棋盤游戲，題目鏈接：[https://blog.csdn.net/a1046765624/article/details/79440860]
• 代碼:

#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#define MAXN 110
using namespace std;
int G[MAXN][MAXN];
int pipei[MAXN];
bool used[MAXN];
int N, M,K;
void init()
{memset(G,0,sizeof(G));}
void getMap()
{int u,v;for(int i = 0; i < K; i++){scanf("%d%d",&u,&v);G[u][v]=1;}
}
int find(int x)
{for(int i = 1; i <=M; i++){int y = G[x][i];if(y&&!used[i]){used[i] = true;if(pipei[i] == -1 || find(pipei[i])){pipei[i] = x;return 1;}}}return 0;
}
int solve()
{int ans = 0;memset(pipei, -1, sizeof(pipei));for(int i = 1; i <=N; i++){memset(used, false, sizeof(used));ans += find(i);}return ans;
}
int te=0;
int main()
{while(~scanf("%d%d%d", &N,&M,&K)){te++;init();getMap();int ans=solve();int su;int sum=0;for(int i=1;i<=N;i++){for(int j=1;j<=M;j++){if(G[i][j]){G[i][j]=0;su=solve();if(su<ans)sum++;G[i][j]=1;}}}printf("Board %d have %d important blanks for %d chessmen.\n",te,sum,ans);}return 0;
}

• 代碼思想:二分圖匹配，匹配行和列，最后，搜索所有邊，每次刪除一條邊，如果最大匹配變少了，這條邊（就是棋盤位置）就是關(guān)鍵位置；
• 本題為二分圖應(yīng)用，有用到匈牙利算法，其本質(zhì)就是尋找最大流的增廣路徑，本題中利用匈牙利算法求出最大匹配，即可放置的最大車的數(shù)量；
• 還有STL的應(yīng)用,用STL中的 vector 建立鄰接表實(shí)現(xiàn)匈牙利算法,效率比較高 ；
• 匈牙利算法有兩種版本： DFS 和 BFS ，有利于我們結(jié)合所學(xué)進(jìn)行聯(lián)系比較學(xué)習(xí)；
• 二分圖的最大匹配、完美匹配和匈牙利算法鏈接：[http://blog.jobbole.com/106084]

5.Git提交

轉(zhuǎn)載于:https://www.cnblogs.com/78tian/p/9190694.html

總結(jié)

以上是生活随笔為你收集整理的博客作业06--图的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。