图与图论算法.doc

第十三单元　图与图论算法 注意：以下标识符适用于本单元的所有程序。 int n, m; // n代表结点个数，m代表边的个数（有的教材分别用V、E表示）。 int G[N][N]; // 用邻接矩阵存储的图 int u[M], v[M], w[M]; // 用边目录存储的图（u是起点，v是终点，w是权） int first[N], next[M]; // 用邻接表存储的图（不使用指针） vectorint g[N]; // 用邻接表存储的图（使用矢量） edge *adj[N]; // 用邻接表存储的图（使用指针，edge的定义见139页“邻接表”） const int INF=100000000; // 不要设置得过大，以防溢出 注意，其他的信息学资料用G[i][j]=0表示边不存在，而《资料》用G[i][j]=INF表示这条边不存在！ 若无特殊说明，邻接表使用edge *adj[N]。 为了保险，开数组时有N＞n，M＞m。 13.1　图的实现 (1) 邻接矩阵! 开一个二维数组G。G[i][j]表示边(i,j)的权。如果边(i,j)不存在，就令G[i][j]=INF（当然，(i,i)不是一条边，G[i][i]也等于INF）。 邻接矩阵最大的缺点就是内存空间占用太大，内存浪费严重。 (2) 边目录! 设置三个数组u[M]、v[M]、w[M]，分别表示起点、终点和权。 一般情况下，从文件中读取的图都是用边目录来表示的。 (3) 邻接表（链表）! 用一个列表列出所有与现结点之间有边存在的结点名称。 struct edge { int u,v,w; edge *next; } mem[M]; // mem相当于动态内存分配。 int size=-1; #define NEW(p) p=mem[++size]; p-next=NULL edge *adj[N]; // adj[i]代表以i为起点的边。 …… memset(adj, 0, sizeof(adj)); for (int e=0; em; e++) { edge *p; NEW(p); cin(p-u)(p-v)(p-w); p-next=adj[p-u]; adj[p-u]=p; } 如果想检查从a出发的所有边，那么可以 for (edge *e=adj[a]; e!=NULL; e=e-next) { // e-u是起点，e-v是终点，e-w是权 } (4) 邻接表（静态数组）! 注意，在这个“邻接表”里放置的元素是边的序号，不是点的序号。所以还要和边目录配合使用。 int first[N]; // first[u]表示从u出发的第一条边的序号 int u[M],v[M],w[M], next[M]; // next[e]表示编号为e的下一条边的序号 ...... memset(first, -1, sizeof(first)); for (int e=0; em; e++) { cinu[e]v[e]w[e]; next[e]=first[u[e]]; // 插入一条边 first[u[e]]=e; } 如果想检查从a出发的所有边，那么可以 for (int e=first[a]; e!=-1; e=next[e]) { // u[e]是起点，v[e]是终点，w[e]是权 } (5) 邻接表（STL）! 头文件：vector 这种邻接表也要和边目录配合使用。只需把(4)中的代码换成以下代码： vectorint g[N]; // g[u][i]表示从u出发的第i条边的序号 int u[M],v[M],w[M]; // 同样要和边目录配合使用 ...... for (int e=0; em; e++) { cinu[e]v[e]w[e]; g[u].push_back(e); } 如果想检查从a出发的所有边，那么可以 for (int i=0; ig[a].size(); i++) { int e=g[a][i]; // u[e]是起点，v[e]是终点，w[e]是权 } 13.2　图的遍历 (1) 深度优先遍历（递归）! [邻接矩阵] 这是基于邻接矩阵的遍历。如果需要，可以改成基于邻接表的遍历。 bool visited[N]; void DFS(int start) { visited[start]=true; // 处理点start coutstart ; for (int i=0; in; i++) if ((!visited[i]) (G[start][i]!=INF)) DFS(i); } 调用： memset