《NOIP图的基础算法》PPT课件

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

1、NOIP图的常用算法简介石门中学江涛2009.10.4目录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法目录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法顶点给点编号为连续的整数把顶点存放在数组中边邻接矩阵布尔值(或边权值)-TRUE–有边FALSE–无边空间复杂度O(

2、V

3、2)图的表示-----

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

5、E

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

7、denodes[maxN];intvisited[maxN];AdjList*adj[maxN];标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构图的深度优先(Depth-First)遍历:邻接链表、C++图的表示-----图的遍历置每个点标识为“未访问”从所有未被访问的点k出发，调用DFS(k)voidsearch(){intk;for(k=0;k

8、邻的节点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);}图的深度优先(Depth-First)遍历:邻接链表、Pascal图的表示-----图的遍历//图的一般结构typegraph_node=record…end;typeAdjList=recordid:integer;next:^AdjList;end;varn_nodes,S_i:integer;nodes:a

9、rray[1..maxN]ofgraph_node;visited:array[1..maxN]ofinteger;adj:array[1..maxN]of^AdjList;标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构图的深度优先(Depth-First)遍历:邻接链表、Pascal图的表示-----图的遍历置每个点标识为“未访问”从所有未被访问的点k出发，调用DFS(k)proceduresearch();begink:integer;fork:=1ton_nodesdovisited[k]:=0;fork:=1ton_node

10、sdoifvisited[k]<>0thenDFS(k);end;置被访问节点的“时间”---次序访问k的所有相邻的节点procedureDFS(k:integer);begin//从k出发搜索varj:^AdjList;begininc(S_i);visited[k]:=S_i;j:=adj[k];while(j<>NULL)dobeginifvisited[j^.id]<>0thenDFS(j^.id);j:=j^.next;end;end;图的宽度优先(Breadth-First)遍历:邻接链表、C++图的表示-----图的遍历//图的一般结

11、构structgraph_node{…};structAdjList{intid;AdjList*next;};intn_nodes,S_index=0;graph_nodenodes[maxN];intvisited[maxN];AdjList*adj[maxN];标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构图的宽度优先(Breadth-First)遍历:邻接链表、C++图的表示-----图的遍历置每个点标识为“未访问”从所有未被访问的点k出发，调用BFS(k)voidsearch(){intk;for(k=0;k

12、s;k++)visited[k]=0;for(k=0;k