// 邻接矩阵遍历 #include<iostream> #include<cstdio> using namespace std; #define N 10010 int x,y,z,n,m,a[N][N],vis[N]; void dfs(int x) { vis[x]=1; for(int i=1;i<=n;i++) if(a[x][i]&&!vis[i])//相连的 但是没有遍历过的 dfs(i); } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&x,&y,&z); a[x][y]=z; dfs(1); return 0; }
//邻接表 #include<iostream> #include<cstdio> using namespace std; #define N 10010 int x,y,z,n,cnt,v[N],next[N],head[N],len[N]; void add_edge(int x,int y,int z)//head为表头 { v[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; len[cnt]=z; } void dfs(int x){ vis[x]=1; for(int i=head[x];i;i=next[i]){ if(!vis[v[i]]){ dfs(v[i]); } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y,&z); add_edge(x,y,z); } return 0; }
//vector 储存图 #include<iostream> #include<cstdio> #include<vector> using namespace std; #define N 10010 int vis[N],x,y,z; vector<pair<int,int> >vec[N];//> >中间要有空格 void dfs(int x){ vis[x]=1; for(int i=0;i<vec[x].size();i++){ if(!vis[vec[x][i].first])dfs(vec[x][i].first); } } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); vec[x].push_back(make_pair(y,z)); } return 0; }
//前向星 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define N 10010 struct st{int x,y,z;}a[N]; int vis[N],cnt,L[N],R[N]; bool cmp(st a,st b){return a.x<b.x;} void dfs(int x){ vis[x]=1; for(int i=L[x];i<R[x];i++){//遍历以x为起点的边 if(!vis[a[i].y])dfs(a[i].y); } } int main() { int n,m; scanf("%d%d",&n,&m);//输入点数和边数 for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z);//起点 终点 权值 a[++cnt].x=x;a[cnt].y=y;a[cnt].z=z;//只记录边的信息 } sort(a+1,a+cnt,cmp);//根据出点大小排序，这样同一个点所连出的边都是连续的 for(int i=1;i<=m;i++){ if(a[i].x!=a[i-1].x){ //出现新的结点时，新结点的边的终点的区间左端点为i，上个结点边终点区间的右端点为i L[a[i].x]=R[a[i-1].x]=i; } } dfs(1); return 0; }
邻接矩阵：
矩阵算法 位运算时方便
边集数组 前向星：
没有将边挂在点上 而是储存每条边的信息 一般不需要遍历整张图 常用于并查集 方便排序