noip图的基础算法

《noip图的基础算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP图的常用算法简介石门中学江涛2009.10.5目录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法目录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法图的表示-----邻接矩阵顶点给点编号为连续的整数把顶点存放在数组中边邻接矩阵布尔值(或边

2、权值)-TRUE–有边FALSE–无边2空间复杂度O(

3、V

4、)图的表示-----邻接链表边邻接链表每一个顶点有一个所有与之相邻的链表每一条边2个（对无向图）要在两个顶点的链表中都加入空间复杂度O(

5、E

6、)对稀疏图这种方式比较好图的表示-----C/P语言程序实现图的邻接链表的Pascal和C++实现具体参见《NOIP基础数据结构》ppt图的表示-----图的遍历图的深度优先(Depth-First)遍历:邻接链表、C++//图的一般结构structgraph_node{…};structAdjLis

7、t{intid;邻接链表的节点AdjList*next;数据结构};intn_nodes,S_index=0;graph_nodenodes[maxN];intvisited[maxN];标识项点有没有访问过AdjList*adj[maxN];每个顶点都有邻接链表图的表示-----图的遍历图的深度优先(Depth-First)遍历:邻接链表、C++voidsearch(){置每个点标识为“未访问”intk;for(k=0;k

8、从所有未被访问if(!visited[k])DFS(k);的点k出发，}调用DFS(k)voidDFS(intk){//从k出发搜索AdjList*j;置被访问节点的visited[k]=++S_index;“时间”---次序for(j=adj[k];j!=NULL;j=j->next){if(!visited[j->id])DFS(j->id);}访问k的所有相邻的节点图的表示-----图的遍历图的深度优先(Depth-First)遍历:邻接链表、Pascal//图的一般结构typegraph_node=record

9、…end;typeAdjList=recordid:integer;邻接链表的节点next:^AdjList;数据结构end;varn_nodes,S_i:integer;nodes:array[1..maxN]ofgraph_node;visited:array[1..maxN]ofinteger;标识项点有没有访问过adj:array[1..maxN]of^AdjList;每个顶点都有邻接链表图的表示-----图的遍历图的深度优先(Depth-First)遍历:邻接链表、Pascalproceduresearch(

10、);begin置每个点标识为“未访问”k:integer;fork:=1ton_nodesdovisited[k]:=0;fork:=1ton_nodesdo从所有未被访问ifvisited[k]<>0thenDFS(k);的点k出发，end;调用DFS(k)procedureDFS(k:integer);begin//从k出发搜索varj:^AdjList;置被访问节点的begininc(S_i);visited[k]:=S_i;“时间”---次序j:=adj[k];while(j<>NULL)dobeginifvi

11、sited[j^.id]<>0thenDFS(j^.id);j:=j^.next;访问k的所有相邻的节点end;end;图的表示-----图的遍历图的宽度优先(Breadth-First)遍历:邻接链表、C++//图的一般结构structgraph_node{…};structAdjList{intid;邻接链表的节点AdjList*next;数据结构};intn_nodes,S_index=0;graph_nodenodes[maxN];intvisited[maxN];标识项点有没有访问过AdjList*adj[m

12、axN];每个顶点都有邻接链表图的表示-----图的遍历图的宽度优先(Breadth-First)遍历:邻接链表、C++voidsearch(){置每个点标识为“未访问”intk;for(k=0;k