数据结构与算法（Python版）第2版 课件 chap8 图

第8章图图1．相关概念图是一种比线性表和树更为复杂的数据结构。图在交通规划、电路设计、互联网分析等领域都有着广泛的应用。在树形结构中，数据元素之间有着明显的层次关系，每一层上的数据元素可能和下一层中多个元素（孩子）相关，但却只能和上一层中一个元素相关；而在图形结构中，节点之间的关系可以是任意的，任意两个数据元素之间都可能相关。2图图G由两个集合V和E组成，可记为：G=(V，E)其中V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。

顶点集V(G)={a,b,c,d,e}，

关系集E(G)={<a,b>,<a,e>,<b,c>,<c,d>,<d,a>,<d,b>,<e,c>}。3图邻接矩阵邻接矩阵（AdjacencyMatrix）用一维数组存储图的顶点信息，用矩阵表示图中各顶点之间的邻接关系。对于n个顶点的无向图，其邻接矩阵是一个n×n的方阵，定义为：4邻接矩阵对于n个顶点的有向图，其邻接矩阵是一个n×n的方阵，定义为：

5图

对于加权图，用wij表示边<vi,vj>的权值。如果边不存在，则在矩阵中赋值，其邻接矩阵为：6NetworkX库NetworkX在2002年5月产生，是一个用Python语言开发的图论与复杂网络建模工具，networkx支持创建简单无向图、有向图和多重图；内置许多标准的图论算法，节点可为任意数据；支持任意的边值维度，内置了常用的图与复杂网络分析算法，可以方便的进行复杂网络数据分析、仿真建模等工作，功能丰富，简单易用。Networkx的制图功能，需要安装matplotlib和numpy7图的遍历

从图中某个顶点出发访遍图中其余顶点且仅访问一次的过程称为图的遍历。

图的遍历有两种方式：

深度优先遍历

广度优先遍历。8深度优先遍历深度优先遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先遍历可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。9图的遍历

10图的遍历深度优先遍历的详细步骤如下所示：第1步：访问a。第2步：访问a的邻接点b。在第1步访问a之后，接下来应该访问的是a的邻接点，即e,f,b中的一个。假设顶点abcdefg是按照顺序存储，b在e和f的前面，因此先访问b。第3步：访问b的邻接点c。第4步：访问c的邻接点d。第5步：访问a的邻接点e。d没有未被访问的邻接点，回溯到c和b，也没有未被访问的邻接点，回到a，访问a的邻接点e和f中的一个（b已经被访问），e在f前，先访问e。第6步：访问e的邻接点f。e有两个未被访问的邻接点g和f，f在前，先访问f。第7步：访问e的邻接点g。f没有未被访问的邻接点，回溯到e，访问e的另外一个未被访问的另节点g。因此访问顺序是：a->b->c->d->e->f->g11递归深度优先fromcollectionsimportdequedefdfs(G,v,visited=set()):print(v,"",end="")visited.add(v)#用来存放已经访问过的顶点#G[v]是这个顶点的相邻的顶点foruinG[v]:#这一步很重要，否则进入无限循环，只有这个顶点没有出现在这个集合中才会访问ifunotinvisited:dfs(G,u,visited)print('递归深度优先dfs')dfs(G,0)12迭代深度优先fromcollectionsimportdequedefdfs_iter(G,v):visited=set()s=[v]whiles:u=s.pop()ifunotinvisited:print(u,"",end="")visited.add(u)s.extend(G[u])print('迭代深度优先dfs')dfs_iter(G,0)13图的遍历2.广度优先遍历广度优先遍历类似于树的按层次遍历的过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过和邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程中以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1,2,通的顶点。和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1、2、…的顶点。。14图的遍历广度优先遍历的详细步骤如下所示：第1步：访问a。第2步：依次访问b、e、f。在访问了a之后，接下来访问a的邻接点。前面已经说过，假设顶点abcdefg按照顺序存储的，因此访问顺序为b、e、f。第3步：依次访问c、g。在第2步访问完b、e、f之后，再依次访问它们的邻接点。首先访问b的邻接点c，再访问e的邻接点f。第4步：访问d。在第3步访问完c、g之后，再依次访问它们的邻接点。只有c有邻接点d，因此访问c的邻接点d。因此访问顺序是：a->b->e->f->c->g->d15广度优先遍历fromcollectionsimportdequeG=[{1,2,3},#0{0,4,6},#1{0,3},#2{0,2,4},#3{1,3,5,6},#4{4,7},#5{1,4},#6{5,}#7]print(G)defbfs(G,v):q=deque([v])#同样需要申明一个集合来存放已经访问过的顶点，也可以用列表visited={v}whileq:u=q.popleft()print(u,"",