通信原理大综合课件软件

在此幻灯片插入公司的徽标从“插入”菜单选择图片找到徽标文件单击“确定”重新设置徽标大小单击徽标内任意位置。徽标外部出现的方框是“调整控点”使用这些重新设置对象大小如果在使用尺寸调整控点前按下shift键，则对象改变大小但维持原比例。DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构2024/10/1622.6图图是一种非线性的数据结构，结点之间的关系可以是任意的。图中任意两个元素之间都可能相关。2.6.1图的基本概念2.6.2图的存储结构

（1）图的邻接矩阵表示法（2）图的邻接表表示法2.6.3图的遍历

2024/10/163图定义

图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：

Graph＝(V,E)

其中

V={x|x

某个数据对象}是顶点的有穷非空集合；

E={(x,y)|x,y

V}

是顶点之间关系的有穷集合，也叫做边(edge)集合。2024/10/164若<v,w>∈VR,则<v,w>表示从v到w的一条弧，且称v为弧尾或初始点,称w为弧头或终端点,此时的图称为有向图.V1V3V2V4V1V3V2V4弧的集合G={<V1

，V3>,<V3

，V4>,<V2

，V4>,<V4，V1>}若<v,w>∈VR，必有<w,v>∈VR，即VR是对称的，则以无序对（v,w）代替这两个有序对，表示v和w之间的一条边，此时的图称为无向图。边的集合E={(V1,V3),(V1,V2),(V1,V4),(V2,V4)}具有边的图，称做无向图，而具有弧的图，称做有向图。注意：在无向图中，(x,y)与(y,x)表示同一条边在有向图中，<x,y>与<y,x>表示不同的弧2024/10/165假定图的顶点数为n,那么具有n(n-1)/2条边的图为无向完全图具有n(n-1)条弧的图为有向完全图V3V1V2V4V1V2V3V42024/10/166图的一部分或自身都可称为图的子图(Subgraph)。V3V4V1V3V1V2V4V1V2V4V1V2V4V1V2V3V4V1V1V3V1V3V2V4V1V3V2V42024/10/167V1V3V2V4V1V3V2V4度:依附于该顶点的边数或弧数。出度和入度仅对有向图而言，出度是指以该顶点为尾的弧数，

入度是指以该顶点为头的弧数。2024/10/168在无向图G=(V,E)中,如果存在顶点序列(Vp,Vi1,Vi2,...,Vin,Vq）使得(VP,Vi1),(Vi1,Vi2)，…，(Vin,Vq)都在E中，则称从顶点VP到Vq存在一条路径。若G是有向图，则路径也是有向的,即<VP,Vi1>,<Vi1，,Vi2>,…,<Vin,Vq>都在E中,VP为路径的起点，Vq为路径的终点。路径上边或弧的数目称为该路径的路径长度起点和终点相同的路径称为回路或环

顶点不重复出现的路径称为简单路径。除了起点和终点相同外,其他顶点不重复出现的回路称为简单回路。V1V3V2V4V1V3V2V42024/10/169连通图：对无向图G而言,如果从Vi到Vj有路径，则称Vi到Vj是连通的。若图中任意两个顶点Vi和Vj(Vi≠Vj)都连通，则称G是连通图。一个无向图的各连通分量定义为该图的各个最大连通子图。V1V2V3V4V5V6V1V2V3V4V5V6(a)无向图G3(b)G3的两个连通分量

对有向图G而言，若任意两个顶点Vi和Vj(Vi≠Vj)，都有一条从Vi至Vj

的路径，同时还有一条从Vj

到Vi的路径,则称该有向图为强连通图，有向图的各个极大强连通子图称作该有向图的各个强连通分量。V2V3V1V4V1V3V2V42024/10/1610如果一个图有n个顶点和小于n-1条边，则是非连通图。如果一个图多于n-1条边，则一定有环。2024/10/1611V1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010

V20001

V30001

V41000

V1V2V3V4

V1

0111

V21001

V31000

V41100图的邻接矩阵表示法是否唯一无向图完全图2024/10/1612V1V3V2V4V1V3V2V4432121∧113∧4∧4∧2图的邻接表表示法∧1∧3∧44321∧4是否唯一2024/10/1613邻接表的形式说明typedefstructnode{//表结点

intadjvex；

structnode*next；

//若要表示权值，则增加一个数据域

}EdgeNode;

typedefstructvnode{//表头结点

VertexTypevertex；

EdgeNode*firstedge；//边表头指针

}VertexNode；头结点和表结点的个数2024/10/16142．6．3图的遍历(深度优先和广度优先两种方式)图的遍历是指从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次的过程。由于图中可能存在回路，容易造成顶点被重复访问，为此设置一个辅助数组visited[0..n-1],初始值为“0”或“假”，当顶点vi被访问后，将visited[i]置为“真”或被访问时的次序号。2024/10/16151.深度优先遍历（DFS)

深度优先遍历是从图中某个顶点V0出发，访问此结点，然后选择一个与V0相邻且未被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且未被访问的顶点Vj访问，...，如果当前被访问的顶点的所有邻接点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的w，从w出发按同样的方式向前搜索，直至图中所有连通的顶点都被访问。如果图中还有顶点未被访问，那么再从这些未被访问的顶点中的某个出发，按深度优先方式遍历，…，直至图中所有顶点都被访问。fbcdeagh从顶点a出发的可能次序为

abcdefghabecdfhg...等多种序列。2024/10/1616

2.广度优先遍历（BFS）广度优先遍历是指从图中某个顶点v0出发，在访问了v0之后依次访问v0的各个未曾访问的邻接点，然后再依次从这些邻接点出发广度优先遍历图，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未被访问，则另选图中一个未曾被访问的顶点做起始点,重复上述过程，直至图中所有顶点都被访问到为止。fbcdeagh例如，从a顶点出发访问右图,那么可以得到

abfceghdafbghced...等多种序列。2024/10/16172．6．4最小生成树对于一个连通图，无论是深度优先遍历和广度优先遍历，最终必然所有顶点都被访问到，且在遍历过程中一定要经过一些边，把这些顶点，用经过的边连起来就是生成树。fbcdeaghfbcdeaghfbcdeagh(a)(b)深度优先生成树(c)广度优先生成树如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。2024/10/1618图的生成树不惟一，从不同的顶点出发进行遍历，可以得到不同的生成树。一颗有n个顶点的生成树有且仅有n-1条边。如果在生成树上添加一条边，必定构成环。

有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权，这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称做网。2024/10/1619生成树中最有意义的问题是：

在n个城市之间建立通讯网络，如果每两个城市之间都设置一条线路，最多可设置n(n-1)/2条线路，而实际上只需要n-1条线路即可连通这n个城市。由于每条线路所付出的经济代价是不同的，如何在所有可能的线路中选择n-1条线路，使总的耗费最小，即是构造连通网的最小代价生成树（简称最小生成树〕问题。普里姆算法的思想是：从顶点集合和边集合为空开始，从图的任一顶点选起，把这个顶点加入到顶点集合中,然后选取依附于该顶点的权值最小的边，加入到边集合中，通过该边又得到一个顶点，把这个顶点也加入集合中，然后再通过这两个顶点选取不构成回路的、权值最小的、其依附的另外一个顶点不在新建的顶点集合中的顶点，把这个顶点和边也加入到集合中，……，直到n个顶点和n-