图的存储与表示： 邻接矩阵：用一个二维数组g[n][n]，进行村粗，g[i][j] = 1，表示有一条边<i,j>，从点i指向点j。 若为无向图 则g[i][j] = g[j][i] = 1 (矩阵一定关于对角线对称) 若为有向图 则g[i][j] = 1 复杂度O(n^2) 存储空间大小 n^2
邻接表：为每个顶点创建一个单链表，顶点u的单链表中存储和顶点u直接相连接的点的下标(去掉表中0，将原先的1直接改为对应下标) 存储空间大小 m 代码： const int N = 2e6 + 5; vector<int> g[N]; //u - v 无向 g[u].push_back(v); g[v].push_back(u); //u -> v 有向 g[u].push_back(v); //u -> v cost w 有权值图 typedef pair<int,int> pii; vector<pii> g[N]; g[u].pb(pii(v,w));
顶点的度、入度和出度 无向图：顶点v的度指和v相连的边的数量 a - b | \ | c - d degree(a) = 3,degree(b) = 2 有向图：顶点v的出度指以v为起点的边的数量，顶点v的入度指以v为终点的边的数量 _____v1 -> v2 | /\ ___| \/ | \/ v5 -> v3 -> v6 <- v4 | /\ /\ | | |_____|_____| |___________| degree_out(v1) = 2,degree_in(v1) = 1 degree_out(v3) = 2,degree_in(v3) = 3
拓扑排序 对于一个DAG(有向无环图)进行拓扑排序，是将所有的项点排成一个线性序列，使得对于图中任意一条有向边<u,v>，都满足u在v之前。（即优先点要满足入度为0） 注意点：拓扑排序不一定唯一（可能会同时产生多个入度为0的点） queue<int> q; if (in[i] = 0) q.push_back(i); for (...) { in[g[q.top()]] -= 1; } //重复上述伪代码
拓扑排序例题：有N个比赛队（1 <= N < 500），编号依次为1，2，3...，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果 ，即P1赢P2，用P1,P2表示，排名时P1在P2之前。现在请你编程序确定排名。（hdu1285） 注意：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。
Sample input 4 3 1 2 2 3 4 3 Sample output 1 2 4 3
//朴素方法 #include <cstdio> #include <cstring> const int maxn = 505; int g[maxn][maxn];//路径 int in_degree[maxn];//入度 int ans[maxn]; int n,m,x,y; void toposort() { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (g[i][j]) { ++in_degree[j]; } } } for (int i = 1; i <= n; ++i) { //寻找编号最小且入度为0 int k = 1; while (in_degree[k] != 0) ++k; ans[i] = k; in_degree[k] = -1;//更新为-1，不影响后续检测 for (int j = 1; j <= n; ++j) { if (g[k][j]) --in_degree[j];//相关入度减1 } } } void init() { memset(in_degree,0,sizeof(in_degree)); memset(ans,0,sizeof(ans)); memset(g,0,sizeof(g)); } int main() { while(~scanf("%d%d",&n,&m)) { init(); for (int i = 1; i <= m; ++i) { scanf("%d%d",&x,&y); g[x][y] = 1; } toposort(); for (int i = 1; i < n; ++i) { printf("%d ",ans[i]); } printf("%d\n",ans[n]); } return 0; }
//拓扑排序 + 优先队列 #include <iostream> #include <queue> #include <cstdio> #include <cstring> using namespace std; const int maxn = 505; bool map[maxn][maxn]; int in[maxn]; priority_queue<int,vector<int>,greater<int> > q; void topo(int n) { for (int i = 1; i <= n ; ++i) { if (in[i] == 0) q.push(i); } int c = 1; while (!q.empty()) { int v = q.top(); q.pop(); if (c != n) { cout << v << " "; ++c; } else cout << v << endl; for (int i = 1; i <= n; ++i) { if (!map[v][i]) continue; --in[i];//保证已经push的不会重复push if (!in[i]) q.push(i); } } } int main() { int n,m,i,j; while (cin >> n >> m) { memset(map,0,sizeof(map)); memset(in,0,sizeof(in)); while (m--) { cin >> i >> j; if (map[i][j]) continue; map[i][j] = 1; ++in[j]; } topo(n); } }
//存疑 //邻接表 + 拓扑排序 (1)数组式邻接表： #include <iostream> using namespace std; const int maxn = 505; const int maxn1 = 250005; int ind[maxn];//入度 int adj[maxn1];//adjacency list邻接表位置值 int adj_next[maxn1];//邻接表下一指针 int tail[maxn];//邻接表尾 int main() { int n,m,i,j,a,b; while (scanf("%d%d",&n,&m) != EOF) { //初始化 for (i = 0; i <= n; ++i) { tail[i] = -1; adj[j] = -1; adj_next[i] = -1; ind[i] = 0; } for (i = 0; i < m; ++i) { scanf("%d%d",&a,&b); int x = tail[a],flag = 0; while (x != -1)//判断是否重边 { if (adj[x] == b) { flag = 1; break; } x = adj_next[x]; } if (!flag)//共联a的邻接表 { adj[i] = b; adj_next[i] = tail[a]; tail[a] = i; ++ind[b]; } } for (i = 1; i <= n; ++i)//找n次 { for (j = 1; j <= n; ++j)//遍历 { if (ind[j] == 0)//当入度为0，说明靠前 { ind[j] = -1;//在下次寻找入度时为0跳过 if (i == 1) printf("%d",j); else printf(" %d",j); //邻接位置入度减1 for (int k = tail[j]; k != -1; k = adj_next[k]) { --ind[adj[k]]; } break; } } } printf("\n"); } return 0; }