《图论(c++版)》由会员分享，可在线阅读，更多相关《图论(c++版)（53页珍藏版）》请在金锄头文库上搜索。
1、图论算法 c+,一对一和一对多的结构：在前边讲解的线性表中，每个元素之间只有一个直接前驱和一个直接后继，在树形结构中，数据元素之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。 图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。,一、图的定义及其术语图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G
2、中顶点的集合，E是图G中边的集合。,对于图的定义，我们需要明确几个注意的地方： 线性表中我们把数据元素叫元素，树中叫结点，在图中数据元素我们则称之为顶点(Vertex)。 线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，而图结构在国内大部分的教材中强调顶点集合V要有穷非空。 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。,图的各种定义,无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边(Edge)，用无序偶数对(Vi,Vj)来表示。 无向图：图中所有
3、顶点间的边均是无向的。,上图G1是一个无向图，G1=V1,E1，其中 V1=A,B,C,D， E1=(A,B),(B,C),(C,D),(D,A),(A,C) 无序对(A,B) 表示A和B之间的一条边(Edge)，因此(A,B) 和(B,A)代表的是同一条边。,上图G2是一个无向图，G2=V2,E2，其中 V2=A,B,C,D， E2=,有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧(Arc)，用有序偶数对来表示，Vi称为弧尾，Vj称为弧头。 有向图：图中所有顶点间的边均是有向的。,简单图：在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。以
4、下两个则不属于简单图：,稀疏图、稠密图、权有很少边或弧的图（e e;for (k = 1; k i j w; /读入两个顶点序号及权值gij = w; /对于不带权的图gij=1gji = w; /无向图的对称性,如果是有向图则不要有这句！ return 0; ,建立邻接矩阵时，有两个小技巧: 初始化数组大可不必使用两重for循环。 1) 如果是int数组，采用memset(g, 0x7f, sizeof(g)可全部初始化为一个很大的数(略小于0x7fffffff)， 使用memset(g, 0, sizeof(g)，全部清为0， 使用memset(g, 0xaf, sizeof(g)，全部初
5、始化为一个很小的数。 2)如果是double数组，采用memset(g,127,sizeof(g);可全部初始化为一个很大的数1.38*10306， 使用memset(g, 0, sizeof(g)全部清为0.,2.数组模拟邻接表存储邻接矩阵看上去是个不错的选择，首先是容易理解，第二是索引和编排都很舒服 但是我们也发现，邻接矩阵适合于结点数较少的稠密图。如果用来表示稀疏图，则会造成很大的空间浪费。因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合一起来存储，这种方式在图结构也适用，我们称为邻接表(AdjacencyList)。 基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接
6、顶点及其相关信息。 每一个单链表设一个表头结点。 第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。图的邻接表存储法，又叫链式存储法。本来是要用链表实现的，但大多数情况下只要用数组模拟即可。,邻接表（有向图）邻接表的处理方法是这样： 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。 图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。,若是有向图，邻接表结构就是这样定义的。,有向图的邻接表： 我们先来看下把顶点当弧尾建立的邻接表，这样很容易就可以得到每个顶点的出度：,但也有
7、时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表：,此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。,对于带权值的网图，可以在边表结点定义中再增加一个数据域来存储权值即可：,邻接表（网）,在进行邻接表的输入时，可以直接使用邻接表的定义方式直接输入； 也可由别的输入方式进行演变，课本上的就是利用边的顶点及其权值进行输入的,以下是用数组模拟邻接表存储的参考程序段：,const int N=maxn； / maxn表示图中最大顶点数 const int E=maxe ； / maxe图中最大边数 struct Edge int u,v
8、; /边所邻接的两个顶点 int w; /边的权值 int next; /边指针，指向下一条边的内存地址 edgeE; / 静态内存，用于分配边 int headN; / 表头 int num; / 内存的指针 void init() for(int i=0;iE;i+) headi=-1; /这里为什么要设为-1 num= 0; void addedge(int b,int e,int w) edgenum.u=b; edgenum.v=e; edgenum.w=w; edgenum.next=headb; headb=num+; ,int main() num_edge=0;scanf(“%d %d“, 两种方法各有用武之地，需按具体情况，具体选用。,【例题】求一个有向图中指定顶点的出度,【问题描述】如题 【文件输入】 第1行：2个空格分开的整数n(2=n=200)和m(10=m=20000)，分别表示图的顶点数和边数。 第2m+1行：每行2个空格分开的整数i，j，i表示一条边的起点，j表示终点。 第m2行：1个整数k(2=k=n),表示指定的顶点。 【文件输出】只有一行为1个整数，表示顶点k的出度。 【样例输入】 5 8 3 5 4 5 4 3 2 3 5 4 4 1 4 2 2 4 4 【样例输出】4,
