《NOIp图论算法与模型构建课件》由会员分享，可在线阅读，更多相关《NOIp图论算法与模型构建课件（96页珍藏版）》请在金锄头文库上搜索。
1、NOIp图论算法与模型构建,长沙市一中 曹利国,图结构,图结构包括： 点 边 图涉及到的概念 边的权 点的度,图的储存结构,矩阵 邻接表 邻接多重表 十字链表,无向图邻接表,1,5,2,4,3,1 2 3 4 5,1 |,5 |,4 |,3 | /,2 |,2 |,2 |,3 |,1 |,2 |,4 | /,5 | /,4 | /,5 | /,邻接链表 每一个顶点 有一个所有与之相邻的链表 每一条边 2 个（对无向图） 要在两个顶点的链表中都加入 空间复杂度O(|E|) 对稀疏图这种方式比较好,邻接表,Pascal语言 const maxv=10000; type Tnode=record /
2、定义顶点类型 c:integer; /顶点编号 next:Tnode; /此点的邻接链表 end; Var /数组g表示每个顶点的邻接链表 /的链表头-哨兵 g:array1.maxv of Tnode; n,m,i,a,b:integer; t:Tnode;,C+语言 #include using namespace std; const int maxv=10000; struct Tnode /定义顶点类型 int c; /顶点编号 Tnode *next; /此点的邻接链表 ; /数组g表示每个顶点的邻接链表 /的链表头-哨兵 Tnode gmaxv ; int n,m,i,a,b;
3、Tnode *t;,图G有n个顶点，编号从1到n。有m条有向边，输入时每行两个整数a b， 表示边为从顶点a连接到顶点b。下面程序用指针实现图的邻接链表。,Pascal语言 procedure ins(x:integer; var p:Tnode); Begin /插入链表子过程 new(t); t.c:=x; t.next:=p.next; p.next:=t; end; begin readln(n,m); /初始化邻接链表“哨兵” for i:=1 to n do gi.next :=nil; /读入边，插入邻接链表 for i:=1 to m do begin readln(a,b);
4、 ins(b,ga); ins(a,gb);/无向边时再加入 end; /.,C+语言 void ins(int x, Tnode /无向边时 /,邻接表的实现A（指针）,Pascal语言 const maxV=1000; /最多顶点数 maxE=10000; /最多边数 type Tnode=record /定义顶点类型 c:integer; /节点编号 next:integer; /此节点的邻接链表 end; var e:array1.maxE of Tnode; g:array1.maxV of Tnode; n,m,efree,i,a,b,t:integer; procedure in
5、s(x:integer; var p:Tnode); begin /取一个空元素插入链表p后 eefree.c:=x; eefree.next:=p.next; p.next:=efree; efree:=efree+1; /新空元素下标 end;,C+语言 const int maxV=1000, /最多顶点数 maxE=10000; /最多边数 struct Tnode /定义顶点类型 int c; /顶点编号 int next; /此点的邻接链表 ; /数组g表示每个顶点的邻接链表 /的链表头-哨兵 Tnode gmaxV, emaxE ; int n, m, i, a, b, efre
6、e, t; void ins(int x, Tnode /新空元素下标 ,邻接表的实现B（数组）,Pascal语言 begin readln(n,m); /初始化邻接链表“哨兵” for i:=1 to n do gi.next := -1; efree:=1; /读入边，插入邻接链表 for i:=1 to m do begin readln(a,b); ins(b,ga); ins(a,gb);/无向边时 end; .,C+语言 int main() cin n m; efree=0; /初始化邻接链表“哨兵” for(i=1; iab; ins(b,ga); / ins(a,gb);/无
7、向边时 ,邻接表的实现B（数组）,Type Link = Node; Node = Record v, w: Longint; 顶点和费用 Next: Link; End; Map: Array1 . Maxnof Link; 用临接表记录的图,Read(n, m, s, t); For i:= 1 to m do Begin Read(a, b, c); New(p); p.v:= b; p.w:= c; p.Next:= Mapa; Mapa:= p; End;,图的遍历,从图中某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次。这一过程称为图的遍历。 遍历图的基本搜索方法
8、有两种：深度优先搜索DFS和广度优先搜索BFS。这两种方法都适用于有向图和无向图。,图的深度优先搜索遍历,图的深度优先遍历DFS算法是每次在访问完当前顶点后，首先访问当前顶点的一个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点，这样的算法是一个递归算法。 连通图的深度优先遍历算法思想。 （1）访问初始顶点v并标记顶点v已访问。 （2）查找顶点v的第一个邻接顶点w。 （3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。 （4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。 （5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi
9、转到步骤（3）。直到连通图中所有顶点全部访问过为止。,深度优先遍历的程序实现：（邻接表、Pascal）,/图的一般结构 type graph_node=record end; type AdjList=record id :integer; next :AdjList; end; var n_nodes,S_i:integer; nodes:array1.maxN of graph_node; visited:array1.maxNof integer; adj:array1.maxN of AdjList;,标识项点有没有访问过,每个顶点都有邻接链表,邻接链表的节点 数据结构,深度优先遍历的
10、程序实现：（邻接表、Pascal）,置每个点标识为“未访问”,从所有未被访问 的点k出发， 调用DFS(k),procedure search( ); begin k :integer; for k:=1 to n_nodes do visitedk:= 0; for k:=1 to n_nodes do if visitedk0 then DFS( k ); end;,置被访问节点的 “时间”-次序,访问k的所有相邻的节点,procedure DFS(k:integer);begin /从k出发搜索 var j:AdjList ; begin inc(S_i);visitedk:=S_i;
11、j:=adjk; while (jNULL) do begin if visitedj.id0 then DFS(j.id); j:=j.next; end; end;,图的广度优先搜索遍历,图的广度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。 连通图的广度优先遍历算法思想。 （1）顶点v入队列。 （2）当队列非空时则继续执行，否则算法结束。 （3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。 （4）查找顶点v的第一个邻接顶点col。 （5）若v的邻接顶点col未被访问过的，则co
12、l入队列。 （6）继续查找顶点v的另一个新的邻接顶点col，转到步骤 （5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。,宽度优先遍历的程序实现：（邻接表、C+）,/图的一般结构 struct graph_node ; struct AdjList int id; AdjList *next; ; int n_nodes,S_index=0; graph_node nodes maxN ; int visited maxN ; AdjList *adj maxN ;,标识项点有没有访问过,每个顶点都有邻接链表,邻接链表的节点 数据结构,宽度优先遍历的程序实现:（邻接表、C+）,
13、置每个点标识为“未访问”,从所有未被访问 的点k出发， 调用BFS(k),void search( ) int k; for(k=0;kn_nodes;k+) visitedk = 0; for(k=0;kn_nodes;k+) if ( !visitedk ) BFS( k ); ,宽度优先遍历的程序实现：（邻接表、C+）,int q maxN ; void BFS( int k ) int front,back; q0=k; front=back=0; for(;fronnext) if ( !visitedj-id ) q+back=j-id; visitedj-id=+S_index;
14、 ,BFS用的队列，一般全局,Front=back,队列不空,访问k的所有相邻的节点,图的连通性问题,有向图的强连通子图 生成树问题,强连通子图,有向图的强连通子图 强连通子图中，任两个节点都直接或间接相连 以深度优先搜索为基础的算法,1,4,2,7,8,5,3,6,生成树问题,无向图的最小生成树（贪心思想） Prim算法，适用于点少的图 Kruskal算法，适用于边少的图 有向图的最小树形图,局域网(net) 某局域网内有n(n=100)台计算机，由于建网时工作人员的疏忽，现在网内存在回路，造成网络卡的现象。 我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)=1000)，f(i,
15、j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要除去一些连线，使得网络中没有回路，并且被除去网线的f(i,j)最大，请求出这个最大值。,实际问题,生成树：一个|V|个点的图，取其中|V|-1条边，并连接所有的顶点，则组成原图的一个生成树。 属性：|v|-1条边、连通、无环。 最小生成树：加权图的最小生成树是一棵生成树，其所有边的权值之和不会大于其它任何生成树。 简单讲：找出连接所有点的最低成本路线,最小生成树(MST）,红边连接了所有顶点, 所以构成一棵生成树 权和=1+2+4+4+7+8+9,环属性：一棵生成树上，增加一条边e，再删除e所在环上的最大边，会得到另一棵“更好”的生成树(如果e不是最大边),最小生成树(MST)-算法原理,9,4,剪切属性：在图中，剪切将顶点划分成两个不相交集合。交叉边为这些顶点在两个不同集合的边。对于任何一个剪切，各条最小的交叉边都属于某个MST，且每个MST中都包含一条最小交叉边。,最小生成树(MST)-算法原理,7,4,9,最小边原则：图中权值最
