练习3 思路：利用栈进行遍历访问，若栈空则形成一个连通子图 非递归遍历算法思想： （1）访问一个顶点，记录被访问；其所有未被访问的邻接顶点入栈 （2）若栈空，退出；否则，栈中一顶点出栈 （3）若顶点已被访问，则转（2）；否则，转（1）
#include<bits/stdc++.h> using namespace std; const int MAX_N = 110; stack<int>s; struct Mgraph { int map[MAX_N][MAX_N]; int vexnum; }G; int visited[MAX_N]; int main() { cin >>G.vexnum; int i, j, v; for (i = 1; i <= G.vexnum; i++) for (j = 1; j <= G.vexnum; j++) cin >> G.map[i][j]; int cnt = 0, find = 0; for (int i = 1; i <= G.vexnum; i++) if (visited[i] == 0) {//若该顶点没被访问 v = i; while (1) { find = 0; visited[v] = 1;//标记一顶点 for (j = 1; j <= G.vexnum; j++) //所有未标记的邻接顶点入栈 if (G.map[v][j] == 1 && visited[j] == 0) s.push(j); do { if (s.empty()) {//如果栈空则退出 cnt++; find = 1; break; } v = s.top(); s.pop();//否则栈中一顶点出栈 } while (visited[v] == 1);//如果顶点未被访问过，退出循环，访问这个顶点 } if (find == 1)break;//退出外层循环 } cout << cnt; return 0; }递归：
#include <bits/stdc++.h> using namespace std; const int MAX_N = 110; struct MGraph { int map[MAX_N][MAX_N]; int vexnum; }G; int visited[MAX_N]; void DFS(int v){//遍历一个连通图 visited[v] = 1; for (int j = 1; j <= G.vexnum; j++) if (G.map[v][j] && !visited[j]) DFS(j); } int main() { cin >> G.vexnum; for (int i = 1; i <= G.vexnum; i++) for (int j = 1; j <= G.vexnum; j++) cin >> G.map[i][j]; int cnt = 0; for (int i = 1; i <= G.vexnum; i++)//遍历图中所有连通子图 if (!visited[i]){ DFS(i);//遍历一个连通子图 cnt++;//得到一个连通子图 } cout << cnt; return 0; }练习1 思路：利用普利姆算法。 普利姆算法：从U={u0}, TE={}开始，在所有u∈U, v∈V-U的边(u,v)∈E中找到一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止
#include<bits/stdc++.h> using namespace std; const int MAX_N = 100; const int MAX_NUM = 10000; struct Graph {//邻接矩阵 int GMap[MAX_N][MAX_N]; int vexnum; }G; vector<int>u;//存放U中顶点 int main() { cin >> G.vexnum; int i, j; for (i = 1; i <= G.vexnum; i++) for (j = 1; j <= G.vexnum; j++) cin >> G.GMap[i][j]; int min, sign, sum = 0; u.push_back(0); u.push_back(1);//顶点1进U while (u.size() <= G.vexnum) { min = MAX_NUM; for (i = 1; i < u.size(); i++) for (j = 1; j <= G.vexnum; j++) if (G.GMap[u[i]][j]!=0&&G.GMap[u[i]][j] < min) { min = G.GMap[u[i]][j]; sign = j; } G.GMap[--i][sign] = 0; G.GMap[sign][i] = 0;//将遍历过的图置0，防止重复遍历 sum += min; u.push_back(sign);//将顶点入U } cout << sum; return 0; }练习2 思路：利用迪杰斯特拉算法求源点到其余各点的最短路径 迪杰斯特拉算法：按路径长度递增的次序产生你最短路径。下一条最短路径或者是弧(v,x),或者是中间只经过S中的顶点而最后到达顶点x的路径。
#include<bits/stdc++.h> using namespace std; const int MAX_N = 25; const int MAX_NUM = 10000; struct Graph {//邻接矩阵 int GMap[MAX_N][MAX_N]; int vexnum; }G; int final[MAX_N],D[MAX_N];//final[i]为1,i顶点在S中 int main() { cin >> G.vexnum; int i, j; for (i = 1; i <= G.vexnum; i++) for (j = 1; j <= G.vexnum; j++) cin >> G.GMap[i][j]; for (i = 1; i <= G.vexnum; i++) for (j = 1; j <= G.vexnum; j++) if (j != i && G.GMap[i][j] == 0) G.GMap[i][j] = MAX_NUM;//设没有路径的两顶点间距离为MAX_NUM final[1] = 1;//第一个顶点入S for (i = 2; i <= G.vexnum; i++) {//初始化D数组 D[i] = G.GMap[1][i]; int min,v; for (i = 2; i <= G.vexnum; i++) {//其余n-1个顶点 min = MAX_NUM;//当前所知离v1最近的距离 for(j=1;j<=G.vexnum;j++)//得到从1出发的最短路径的终点v if (!final[j]&& D[j] < min){ min = D[j];v = j; } final[v] = 1;//顶点v入S for(j=1;j<=G.vexnum;j++)//修改从v出发到集合V-S上任一顶点vk可达最短路径长度 if (!final[j] && min + G.GMap[v][j] < D[j]) D[j] = min + G.GMap[v][j]; } if (D[G.vexnum] == MAX_NUM)cout << -1;//没有路径 else cout << D[G.vexnum]; return 0; }佛洛依德算法（每一对顶点之间的最短路径）： d[N][N]为带权路径长，p[N][N][N]，若p[i][j][k]=1，则k是从i到j求得的最短路径上的顶点
int d[N][N], p[N][N][N];//数据过大时，可把三维数组改为结构体数组 void floyd() { int i, j, k, t; for(i=1;i<=G.vexnum;i++)//各对顶点之间初始已知路径及距离 for (j = 1; j <= G.vexnum; j++) { d[i][j] = G.map[i][j]; if (d[i][j] < N) {//从i到j有直接路径 p[i][j][i] = 1; p[i][j][j] = 1; } } for(k=1;k<=G.vexnum;k++) for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) if (d[i][k] + d[k][j] < d[i][j]) {//从i经k到j的一条路径更短 d[i][j] = d[i][k] + d[k][j]; for (t = 1; t <= G.vexnum; t++)//更新路径 p[i][j][t] = p[i][k][t] || p[k][j][t]; } }练习3 思路：利用拓扑排序，如果排序序列中数字个数小于n，则有环 拓扑排序： (1)在有向图中选一个没有前驱的顶点输出 (2)从图中删除该顶点和所有以它为尾的弧
#include<bits/stdc++.h> using namespace std; const int MAX_N = 25; typedef long long ll; struct Graph {//邻接矩阵 int GMap[MAX_N][MAX_N]; int vexnum; }G; stack<int>s;//存储入度为0的顶点 int degree[MAX_N]; int main() { cin >> G.vexnum; int i, j; for (i = 1; i <= G.vexnum; i++) for (j = 1; j <= G.vexnum; j++) cin >> G.GMap[i][j]; for (i = 1; i <= G.vexnum; i++) //逐列计算各顶点入度 for (j = 1; j <= G.vexnum; j++) if (G.GMap[j][i] == 1) degree[i]++; for (i = 1; i <= G.vexnum; i++)//入度为0的顶点入栈 if (degree[i] == 0) s.push(i); int cnt = 0;//对已排序顶点计数 while (!s.empty()) { i = s.top(); s.pop(); cnt++;//顶点出栈 for (j = 1; j <= G.vexnum; j++) { if (i == j)continue; if (G.GMap[i][j] == 1) {//i号顶点的每个邻接顶点入度-1 degree[j]--; if (degree[j] == 0)s.push(j);//入度为0入栈} } } } if (cnt < G.vexnum)cout << "YES"; else cout << "NO"; return 0; }拓扑排序（关键路径中的）：用栈t逆序存放拓扑序列
void topological_order() { int j; for (int i = 1; i <= G.vexnum; i++) for (int j = 1; j <= G.vexnum; j++) if (G.map[j][i]) indegree[i]++; for (int i = 1; i <= G.vexnum; i++) if (!indegree[i]) s.push(i); int cnt = 0,dut; while (!s.empty()) { j = s.top(); s.pop(); t.push(j); cnt++; for(int k=1;k<=G.vexnum;k++) if (G.map[j][k]) { indegree[k]--; if (!indegree[k])s.push(k); dut = G.map[j][k]; if (ve[j] + dut > ve[k])//ve[k]=max{ve[j]+dut} ve[k] = ve[j] + dut; } } }关键路径：
void critical_path() { topological_order(); int j,k,dut; memset(vl, ve[G.vexnum], sizeof(int)); while (!t.empty()) { j = t.top(); t.pop(); for(k=1;k<=G.vexnum;k++) if (G.map[j][k]) { dut = G.map[j][k]; if (vl[k] - dut < vl[j])//vl[j]=min{vl[k]-dut} vl[j] = vl[k] - dut; } } int ee, el; for(j=1;j<=G.vexnum;j++) for(k=1;k<=G.vexnum;k++) if (G.map[j][k]) { dut = G.map[j][k]; ee = ve[j]; el = vl[k] - dut;//计算关键路径 if (ee == el)cout << j << ' ' << k << endl; } }