1.1鄰接矩陣儲存法

//創建:二維數組vector<vector<int>> graph(n,vector<int>(n,0));//儲存for(int i=0;i<m;i++){int x1,x2;cin>>x1>>x2;graph[x1-1][x2-1]=1;}

1.2鄰接表儲存法

補充：c++中的list是鏈表 鏈接

//創建：數組+鏈表
vector<list<int>> graph(n + 1);//輸入
while (m--) {cin >> s >> t;// 使用鄰接表 ，表示 s -> t 是相連的graph[s].push_back(t);
}
//讀取數據
if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1]  << endl;}

2.1 dfs

所有可達路徑

dfs三部曲：
確認遞歸函數和參數、確認終止條件、處理目前搜索節點的出發路徑（處理節點、dfs遞歸、回溯）

#include<iostream>
#include<vector>
using namespace std;vector<vector<int>> results;
vector<int> result;//1 確認遞歸函數參數: 鄰接表，當前歷遍節點，終點
void dfs(const vector<vector<int>>& graph,int x,int n){//2 確認終止條件：當當前節點x = 最后一個節點n，就是從起點到了終點if(x==n-1){results.push_back(result);//存入結果return;}//3、處理目前搜索節點的出發路徑for(int i=0;i<n;i++){if(graph[x][i]){            //找到下一個節點result.push_back(i+1);  //處理節點dfs(graph,i,n);         //處理下一個節點result.pop_back();      //利用vector的性質回溯}}
}int main(){int n,m;cin>>n>>m;vector<vector<int>> graph(n,vector<int>(n,0));for(int i=0;i<m;i++){int x1,x2;cin>>x1>>x2;graph[x1-1][x2-1]=1;}result.push_back(1); //重要！先把開始節點放進去dfs(graph,0,n);if(results.size()==0)cout<<"-1"<<endl;for(int i=0;i<int(results.size());i++){for(int j=0;j<int(results[i].size()-1);j++){cout<<results[i][j]<<" ";}cout<<results[i][results[i].size()-1]<<endl;}}

要注意0的問題。（開辟n個位置從0-n-1，開辟n+1個位置從0-n）

#include<iostream>
#include<vector>
#include<list>
using namespace std;vector<vector<int>> results;
vector<int> result;//1 確認遞歸函數參數: 鄰接表，當前歷遍節點，終點
void dfs(const vector<list<int>>& graph,int x,int n){//2 確認終止條件：當當前節點x = 最后一個節點n，就是從起點到了終點if(x==n-1){results.push_back(result);//存入結果return;}//3、處理目前搜索節點的出發路徑for(int i:graph[x]){            //找到下一個節點result.push_back(i+1);  //處理節點dfs(graph,i,n);         //處理下一個節點result.pop_back();      //利用vector的性質回溯}
}int main(){int n,m;cin>>n>>m;vector<list<int>> graph(n);for(int i=0;i<m;i++){int x1,x2;cin>>x1>>x2;graph[x1-1].push_back(x2-1);}result.push_back(1); //重要！先把開始節點放進去dfs(graph,0,n);if(results.size()==0)cout<<"-1"<<endl;for(int i=0;i<int(results.size());i++){for(int j=0;j<int(results[i].size()-1);j++){cout<<results[i][j]<<" ";}cout<<results[i][results[i].size()-1]<<endl;}}

島嶼問題99

#include<iostream>
#include<vector>
using namespace std;//1、確定參數
void dfs(const vector<vector<int>>& graph,vector<vector<int>>& visited, int x, int y){int dir[4][2]={0,1,  1,0,  -1,0,  0,-1};//2、終止條件(訪問過了/周邊都是0了，一條路就走完了)if(visited[x][y] || graph[x][y]==0) return;//3、處理當前點visited[x][y]=1;for(int i=0;i<4;i++){//上下左右四個位置,作用是感染同一島嶼的所有塊（顏色填充也是這個原理）int newx=x+dir[i][0];int newy=y+dir[i][1];if(newx<0||newx>=int(graph.size())||newy<0||newy>=int(graph[0].size())) continue;dfs(graph,visited,newx,newy);}}int main(){int n,m;cin>>n>>m;vector<vector<int>> graph(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];}}// for(int i=0;i<n;i++){//     for(int j=0;j<m;j++){//         cout<<graph[i][j]<<" ";//     }//     cout<<endl;// }vector<vector<int>> visited(n,vector<int>(m,0));int result=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(!visited[i][j] && graph[i][j]==1){dfs(graph,visited,i,j);result++;}}}cout<<result;
}

島嶼最大面積100

#include<iostream>
#include<vector>
using namespace std;//1、確定參數(注意！！這里visited和single想要被改變，要傳入變量本身！要用&)
void dfs(const vector<vector<int>>& graph,vector<vector<int>>& visited,int x,int y,int& single){//2、停止條件if(graph[x][y]==0||visited[x][y]){return;}//3、處理當前節點single++;visited[x][y]=1;int dir[4][2]={0,-1,0,1,-1,0,1,0};for(int i=0;i<4;i++){int newx=x+dir[i][0];int newy=y+dir[i][1];if(newx<0||newx>=int(graph.size())||newy<0||newy>=int(graph[0].size())) continue;dfs(graph,visited,newx,newy,single);}
}int main(){int n,m;cin>>n>>m;vector<vector<int>> graph(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];}}int result=0;vector<int> s;vector<vector<int>> visited(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(!visited[i][j] && graph[i][j]==1){int single=0;dfs(graph,visited,i,j,single);result=max(result,single);}}}cout<<result;}

2.2 最小生成樹

prim

#include<iostream>
#include <vector>
#include <climits>
using namespace std;int main(){int v,e;cin>>v>>e;vector<vector<int>> graph(v+1,vector<int>(v+1,100001));while(e--){int x1,x2,val;cin>>x1>>x2>>val;graph[x1][x2]=val;//是無向圖graph[x2][x1]=val;}//------------------檢查用----------------------------// for(int i=1;i<=v;i++){//     for(int j=1;j<=v;j++){//         cout<<graph[i][j]<<" ";//     }//     cout<<endl;// }//----------------------------------------------------vector<int> minDist(v+1,100001);vector<int> intree(v+1,false);vector<int> arc(v+1);int start=-1;for(int count=1;count<v;count++){//循環n-1次//1、選距離生成樹最近的節點，即更新startint min=INT_MAX;for(int i=1;i<=v;i++){if(!intree[i] && minDist[i]<min) {//這里是算生成樹的每個節點與離它最近的樹外節點的距離min=minDist[i];start=i;}}if(start==-1) {cout<<"-1"<<endl;return 0;}//把最近的節點加入生成樹intree[start]=1;//------------------檢查用----------------------------// for(int i=1;i<=v;i++){//     cout<<minDist[i]<<" ";// }// cout<<"###################"<<endl;//----------------------------------------------------//3、更新非生成樹節點到生成樹的距離，即minDist數組。并記錄1中最短邊，即更新arc數組for(int j=1;j<=v;j++){if(!intree[j] && graph[start][j]<minDist[j]){//只要一端在start，另一端不在樹里，且值比當前位置值小的，都放進來minDist[j]=graph[start][j];arc[j]=start;}}//------------------檢查用----------------------------// for(int i=1;i<=v;i++){//     cout<<minDist[i]<<" ";// }// cout<<"-------------------"<<endl;//----------------------------------------------------}int total=0;for(int i=2;i<=v;i++){total+=minDist[i];}cout<<total<<endl;
}