图(Graph)是由顶点集合和一些顶点间的连线组成的数据结构。通常可以用G(V,E)来表示。其中顶点集合(VertextSet)和边的集合(EdgeSet)分别用V(G)和E(G)表示。V(G)中的元素称为顶点(vertex)，用u、v等符号表示。E(G)中的元素称为边(edge)，用e等符号表示。图1(a)所示的图可以表示为G1(V,E)。其中，顶点集合V={1,2,3,4,5,6}，边集合E={(1,2),(1,3),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(4,5)}。这样的图叫无向图。边(u,v)和(v,u)是同一条边。图1(b)所示的图是有向图。有向边u,v中u为起点，v为终点。如果无向图中任何一对顶点之间都有一条边，这样的图称为完全图。在完全图中，顶点数m和边数n的关系为：m=n×(n-1)/2。边的数目相对较少的图称为稀疏图。边的数目相对较多的图称为稠密图。在无向图中，如果(u,v)是图中的一条无向边，则称顶点u和顶点v互为邻接顶点，或称(u,v)与顶点u和v相关联。顶点的度数：一个顶点u的度数是与它相关联的边的数目，记为deg(u)。有向图中，顶点的度数等于该顶点的出度与入度之和。其中，顶点u的出度是以u为起始顶点的有向边（即从顶点u出发的有向边）的数目，记为od(u)。顶点u的入度是以u为终点的有向边（即进入到顶点u的有向边）的数目，记为id(u)。顶点u的度数：deg(u)=od(u)+id(u)。
定理：在无向图和有向图中，所有顶点度数总和，等于边数的两倍。
这是因为，不管是有向图还是无向图，在统计所有顶点的度数之和时，每条边都被统计两次。为了方便起见，我们把度数为偶数的顶点称为偶点，把度数为奇数的顶点称为奇点。有以下推论：推论：每个图都有偶数个奇点。
图的连通性
在无向图中，如果从顶点u到v有路径，则称为顶点u和v是连通的。如果无向图中任意一对顶点都是连通的，则称此图为连通图。相反，如果一个无向图不是连通图，则称为非连通图。如果一个无向图不是连通的，则其极大连通子图称为连通分量。这里的极大是指子图中包含的顶点个数极大。例如图4所示的无向图就是非连通图。其中顶点1,2,3和5构成一个连通分量，顶点4,6,7和8构成另一个连通分量。在有向图中，若对每一对顶点u和v，即存在从u到v的路径，也存在从v到u的路径，则称此图为强连通图。对于非强连通图，其极大强连通子图称为其强连通分量。某些图的边具有与它相关的数，称为权值。这些权值可以表示一个顶点到另一个顶点的距离、花费的代价、所需的时间等等。如果一个图，其所有边都具有权值，则称为加权图，或者称为网络(net)。
图的存储结构
图的存储结构主要有四种：★邻接矩阵(使用二维数组存储，不推荐使用)★前向星★邻接表★链式前向星（静态建表）在编写程序中，后三种是我们经常采用的图的存储结构。
一、邻接矩阵(不推荐使用)
在邻接矩阵存储方法中，使用一个二维数组e[n][n]来表示，定义为：例如图1(a)中，下图表示无向图G1及其邻接矩阵表示。注意：如果图中存在自身环（连接某个顶点自身的边）和重边，多条边的起点一样，终点也一样，也称为平行边的情况，则无法使用邻接矩阵存储。
例1：图的存储
给定n个顶点，m条边，接下来m行，每行三个整数a,b,x，表示边(a,b)的权植为x样例输入：
cinnm;for(inti=0;im;i++){ cinabx; e[a][b]=e[b][a]=x;}
二、前向星
前向星是一种通过存储边的信息的方式存储图的数据结构。它的构造方式非常简单，读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序，前向星就构造完成了。为了查询方便，经常会有一个数组存储起点为Vi的第一条边的位置。
例2：前向星
给定n个顶点，m条边，接下来m行，每行三个整数a,b,x，表示边(a,b)的权植为x。将边从小到大排序后输出。样例输入：样例输出：
#includeiostream#includestring.h#includealgorithmusingnamespacestd;inthead[];//存储起点为Vi的第一条边的位置structnote{intxx,yy,ww;//起点，终点，权值}e[];boolcmp(notea,noteb){if(a.xx==b.xxa.yy==b.yy)returna.wwb.ww;if(a.xx==b.xx)returna.yyb.yy;returna.xxb.xx;}intmain(){intn,m;cinnm;//n个顶点,m条边for(inti=0;im;i++)cine[i].xxe[i].yye[i].ww;//读入边sort(e,e+m,cmp);//将边按顶点从小到大排序memset(head,-1,sizeof(head));//head初始化为-1head[e[0].xx]=0;for(inti=1;im;i++)if(e[i].xx!=e[i-1].xx)head[e[i].xx]=i;//确定起点为Vi的第一条边的位置intk;for(inti=1;i=n;i++) for(k=head[i];e[k].xx==ikm;k++)coute[k].xx""e[k].yy""e[k].wwendl;return0;}
三、邻接表
邻接表是一种链式的存储结构。对于图G中的每个顶点Vi，所有邻接于Vi顶点Vj链成一个单链表，这个单链表称为顶点Vi的邻接表。邻接表中每个表节点有三个属性：其一，邻接点序号to，用以存放与顶点Vi相邻接的顶点vj的序号j，其二，边上的权值我，其三，为指针next，用来将邻接表的所有节点链在一起。另外，为每个顶点Vi的邻接表设置一个具有两个属性的表头节点：一个是顶点序号from，另一个是指向其邻接表的指针first，它是指向Vi的邻接表的第一个节点的指针。建立一个Vnode的数组就可以访问每个顶点的邻接表了。上面的例题2中，利用邻接表存储如下：
#includeiostream#includestring.h#includestdio.husingnamespacestd;constintmaxn=;structenode{//边intto;intw;enode*next;};structvnode{//顶点intfrom;enode*first;};vnodeadjilist[maxn];intmain(){intn,m,j,i,w;while(cinnm){for(intii=1;ii=m;ii++){cinijw;enode*p=newenode();p-to=j;p-w=w;p-next=adjilist[i].first;adjilist[i].first=p;}for(inti=1;i=n;i++){for(enode*k=adjilist[i].first;k!=NULL;k=k-next)couti""k-tok-wendl;}}return0;}
另外，还可以只用到一个结构体，接着结构体数组定义为结构体指针数组，代码如下：
#includeiostream#includestdio.h#includestring.husingnamespacestd;structenode{intto;intw;edgenode*next;}*N[];intmain(){inti,j,w,n;while(~scanf("%d",n)){for(intkk=0;kkn;kk++){cinijw;edgenode*p=newedgenode();p-to=j;p-w=w;p-next=N[i];N[i]=p;}for(inti=1;i=n;i++)for(edgenode*k=N[i];k!=NULL;k=k-next)couti""k-to""k-wendl;}return0;}
四、链式前向星（静态建表）(熟记)
数组模拟链表的主要方式是记录下一个节点在数组中的那个位置。head数组存储描述vi边信息的链的起点在edge数组的位置。构造链式前向星就是将新加入的节点链在对应链的最开始并修改head数组的对应位置的值。链式前向星的建图效率非常高，读入结束建图就结束，时间复杂度为O(m)，空间上使用了两个数组，所以空间复杂度为O(m+n)。缺点：不能用起点和终点来确定是否有边存在。。。。
#includeiostream#includeistring.h#includeitdio.h#includeiiostream#includeialgorithmusingnamespacestd;constintN=;inthead[N];intip;structenode{intyy;intww;intnext;}e[N];voidadd(intu,intv,intw){e[ip].yy=v,e[ip].ww=w,e[ip].next=head[u],head[u]=ip++;}intmain(){intn,m,x,y,w,k=0; scanf("%d%d",n,m);memset(head,-1,sizeof(head));//head所有初始值为-1ip=0;for(intk=0;km;k++){cinxyw;add(x,y,w);//add(y,x,w);若是无向图就加上这句话}for(inti=1;i=n;i++)for(intk=head[i];k!=-1;k=e[k].next)coutie[k].yye[k].wwendl;return0;}
程序说明：假如在上面的程序中，读入如下数据：
在读入数据中，从顶点3出发的边共有3条，依次为(3,5)、(3,6)和(3,1)。读入边(3,5)时（说明：第4次读入），e[3].yy=5，表示编号为3的边的终点为5。 e[3].ww=6，表示编号为3的边的权值为6。 e[3].next=head[u]=head[3]=-1（初始为-1），表示编号为3的边只有一条，没有上一条边。 对应的head[3]=3，表示以顶点3为起点的第一条边的编号为3。读入边(3,6)时（说明：第5次读入），e[4].yy=6，表示编号为3的边的终点为6。 e[4].ww=4，表示编号为3的边的权值为4。 e[4].next=head[u]=head[3]=3，表示编号为4的上一条边的编号为3。 对应的head[3]=4，表示以顶点3为起点的第一条边的编号为4。读入边(3,1)时（说明：第8次读入），e[7].yy=1，表示编号为7的边的终点为1。 e[7].ww=3，表示编号为3的边的权值为3。 e[7].next=head[u]=head[3]=4，表示编号为7的上一条边的编号为4。 对应的head[3]=7，表示以顶点3为起点的第一条边的编号为7。最终，head[3]=7。
赞赏
长沙最好的白癜风医院治疗白癜风专科医院