图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显懂得层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；在图形结构中，结点之间的关系可以任意的，图中任意两个数据元素之间都有可能相关。因此，图的应用极为广泛，已经渗入到诸如语言学、逻辑学、物理学、化学、计算机科学及数学的其他分支中，在信息学奥赛的许多试题中，需要用图来描述数据元素之间的关系。在实际生活中，很多事物可以抽象成图的形式，例如一个城市的公路网。
图的概念
图(graph)是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都有着广泛的应用。图的二元组定义为：
G=(V,E)
其中V是非空的顶点集合，即
V={vi|1≤i≤n,n≥1,vi∈elemtype,n为顶点数}
E是V上二元关系的集合，一般我们只讨论仅含一个二元关系的情况，且直接用E表示这个关系。这样，E就是V上顶点的序偶或无序对(每个无序对(x,y)是两个对称序偶<x,y>和<y,x>的简写形式)的集合。对于V上的每个顶点，在E中都允许有任意多个前驱和任意多个后继，即对每个顶点的前驱和后继个数均不限制。回顾一下线性表和树的二元组定义，都是在其二元关系上规定了某种限制，线性表的限制是只允许每个结点有一个前驱和一个后继，树的限制是只允许每个结点有一个前驱和多个后继。因此，图比线性表和树具有更广泛性，它包含线性表和树在内，线性表和树可看作图的简单情况。
对于一个图G，若E是序偶(有序对)的集合，则每个序偶对应图形中一条有向边；若E是无序对的集合，则每个无序对对应图形中的一条无向边，所以可把E看作是边的集合。这样图的二元组定义可叙述为：图由非空顶点集和边集所组成。针对图G，顶点集和边集可分别记为V(G)和E(G)。边集E(G)允许是空集，这时图G中的顶点均为孤立顶点。
对于一个图G，若边集E(G)为有向边，则称此图为有向图(digraph)，若边集E(G)为无向边，则称此图为无向图(undigraph)。如图1中所示的G1是无向图，G2是有向图。
图的基本术语
1、端点和邻接点
在一个无向图中，若存在一条边(vi,vj)，则称vi，vj为此边的两个端点，并称它们互为邻接点，即vi是vj的一个邻接点，vj也是vi的一个邻接点。如图1的G1中，以顶点v1的四条边是(1,2),(1,3),(1,4)和(1,6)，v1的四个邻接点分别为v2、v3、v4和v6 。
在一个有向图中，若存在一条边< vi,vj >,则称此边是顶点vi的一条出边(outedge)，顶点vj的一条入边(inedge)；称vi为此边的起始端点，简称起点或始点，vj为此边的终止端点，简称终点；称vi和vj互为邻接点，并称vj是vi的出边邻接点，vi是vj的入边邻接点。如图1的G2中，顶点C有两条出边<C,B>和<C,D>,两条入边<A,C>和<B,C>,顶点C的两个出边邻接点为vB和vD,两个入边邻接点为vA和vB。
2、顶点的度、入度、出度
无向图顶点v的度(degree)定义为以该顶点为一个端点的边的数目，简单地说，就是该顶点的边的数目，记为D(v)。如图1的G1中v1顶点的度为4，v2顶点的度为2。有向图中顶点v的度有入度和出度之分，入度(indegree)是该顶点的入边的数目，记为ID(v);出度(outdegree)是该顶点的出边的数目，记为OD(v)。顶点v的度等于它的入度和出度之和，即D(v)=ID(v)+OD(v)。如图1的G2中顶点A的入度为0，出度为2，度为2；顶点C的入度为2，出度为2，度为4。
若一个图中有n个顶点和e条边，则该图所有顶点的度同边数e满足下面关系：
e=
这很容易理解，因为每条边的度数为2，所以全部顶点的度数为所有边数的2倍，或者说，边数为全部顶点的度数的一半。
3、完全图、稠密图、稀疏图
若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。显然，若完全图是无向的，则图中包含有n(n-1)/2条边；若完全图是有向的，则图中包含有n(n-1)条边。当一个图接近完全图时，则可称为稠密图，相反地，当一个图有较少的边数(即e<<n(n-1))时，则可称为稀疏图。图2中的G3就是一个具有五个顶点的无向完全图，G4就是一个具有六个顶点的稀疏图。
4、子图
设有两个图G=(V,E)和G′=(V′,E′)，若V′是V的子集，且E′是E的子集，则称G′是G的子图。例如图2，由G3中全部顶点和同v1相邻的所有边可构成G3的一个子图，由G3中的顶点v1，v2，v3和他们之间的所有边可构成G3的另一个子图。
5、路径和回路
在一个图G中，从顶点v到顶点v′的一条路径(path)是一个顶点序列vi0，vi1，vi2，…，vim，其中v= vi0，v′= vim，若此图是无向图，则(vij-1，vij)∈E(G)(1≤j≤m);若此图是有向图，则< vij-1，vij >∈E(G)( 1≤j≤m)。路径长度是指该路径上经过的边的数目。若一条路径上除了前后端点可以相同外，所有顶点均不同，则称此路径为简单路径。若一条路径上的前后两端点相同，则被称为回路或环(cycle)，前后两端点相同的简单路径被称为简单回路或简单环。如图2的G4中，从顶点c到顶点d的一条路径为vc，ve，va，vb，vd，其路径长度为4；路径va，vb，ve，va为一条简单回路，其路径长度为3；路径va，vb，ve，vf，vb不是一条简单路径，因为存在着从顶点vb到vb的一条回路。
6、连通图和连通分量
在无向图G中，若从顶点vi到项点vj有路径，则称vi和vj是连通的。若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。例如，上面给出的图1中的G1和图2中的G3就是连通图。
7、强连通图和强连通分量
在有向图G中，若从顶点vi到顶点vj有路径，则称从vi到vj是连通的。若图G中的任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图G的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。
8、权和网
在一个图中，每条边可以标上具有某种含义的数值，此数值称为该边的权(weight)。例如，对于一个反映城市交通线路的图，边上的权可表示该条线路的长度或等级；对于一个反映电子线路的图，边上的权可表示两端点间的电阻、电流或电压；对于一个反映零件装配的图，边上的权可表示一个端点需要装配另一个端点的零件的数量；对于一个反映工程进程进度的图，边上的权可以表示从前一子工程到后一个子工程所需要的天数。边上带权的图称作带权图，也常称作网(network)。图3就是一个网。
图的存储结构
图的存储结构又称图的存储表示或图的表示。它有多种方法，这里主要介绍邻接矩阵、邻接表两种方法。
一、邻接矩阵
邻接矩阵是表示顶点之间相邻关系的矩阵(矩阵就是排成行与列的数的阵列)。设G=(V,E)是具有n个顶点的图，顶点序号依次为1、2、…、n,则G的邻接矩阵是具有如下定义的二维数组A，其规模为n×n ：
A[i,j]=
图4(a)和图4(b)对应的邻接矩阵分别为A1、A2:
A1= A2=
若图G是一个带权图，则用邻接矩阵表示也很方便，只要把1换为相应边上的权值，把0换为∞即可。其中∞表示“无穷大”，实际存储时它要大于图G中需要进行的各种运算所得到的最大的权值。
采用邻接矩阵表示图，便于查找图中任一条边或边上的权。如要查找边(vi ，vj)或
<vi ，vj>，则只要查找邻接矩阵中第i行第j列的元素Ai,j是否非零(或非∞)即可；若该元素非零(或非∞)，则表明此边存在，否则此边不存在。
由邻接矩阵A1和A2可以明显地看出，无向图的邻接矩阵A1[i,j]=A1[j,i](1≤i,j≤n)且对角线上的A[i,i]均为0(或±∞)。正因为如此，在实际存储邻接矩阵时只需存储其上三角(或下三角)的元素。因此具有n个结点的无向图，其邻接矩阵的存储容量可节约至n(n-1)/2。而有向图的邻接矩阵中A2[i,j]不一定与A2[j,i](1≤i,j≤n)相同，且图中出现自反边时其对角线上的A2[i,i]也不一定是0(或±∞)。
用邻接矩阵表示图，容易判定任意两个结点之间是否有边相联，并容易求得各个结点的度数。对于无权无向图的邻接矩阵，第i行元素值的和就是Vi的度数；对于无权有向图的邻接矩阵，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；对于有权无向图的邻接矩阵，第i行(或第i列)中元素值<>0的元素个数就是Vi的度数；对于有权有向图的邻接矩阵，第i 行中元素值<>0的元素个数就是Vi的出度；第i列元素值<>0的元素个数就是Vi的入度。
二、图的邻接表表示法
邻接矩阵用的是顺序存储的方式，而邻接表是图的一种链式存储法。
邻接表是对图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。为顶点vi建立的邻接关系的单链表又称作vi的邻接表。vi邻接表中的每个结点用来存储以该顶点为端点或起点的一条边的信息，因而被称为边结点。vi邻接表中的结点数，对于无向图来说，等于vi的边数、邻接点数或度数；对于有向图来说，等于vi的出边数、出边邻接点数或出度数。边结点的类型通常被定义为三个域：一是邻接点域，用以存储顶点vi的一个邻接顶点vi的序号j；二是权域，用以存储边(vi，vj)或<vi，vj>上的权；三是链域，用以链接vi邻接表中的下一个结点。在这三个域中，邻接点域和链域是必不可少的，权域可根据情况取舍，若表示的是无权图，则可省去此域。对于每个顶点vi的邻接表，需要设置一个表头结点，该结点除了包括vi邻接表的表头指针域(link)外，通常还包括用于存储顶点vi信息的值域(data)，若顶点vi的值就是该顶点的编号i，则此域可以省去。如图G中有n个顶点，则就有n个表头结点，为了便于随机访问任一顶点的邻接表，需把这n个表头结点用一个向量(即一维数组)存储起来，其中第i个分量存储vi邻接表的表头结点。这样，图G就可以由这个表头向量来表示。
在图的邻接表中便于查找一个顶点的边(出边)或邻接点(出边邻接点),这只要首先从表头向量中取出对应的表头指针，然后从表头指针出发进行查找即可。
如图3的邻接表表示如图5所示。
图6(a)为无向图，它的邻接表如图7(a)
图6(b)为有向图，在设置边表时，我们可以根据边的方向，统一以起点为基准或以终点为基准，有如下两种不同的存储方式图7(b)和(c):
在邻接表中，需要一个所有结点的顺序表和一个所有边的链接存储表。结点表的每个表目对应于图的一个结点，包括：
1、结点信息，即：
与该结点相连的边数(m)；
访问标志(visited)。
2、边表的首指针(firstarc)。图中每个结点都有一个边表，其中每一个结点对应于与该结点相关联的一条边，包括：
与此边相关联的另一个结点序号(v)；
若为带权图的话，该边的权值(w)；
指向边表的下一个结点的后继指针(nextarc)。
由此可见，用邻接表表示法来存储图，则占用的存储单元既与图的结点数有关，又与边数有关。
邻接表的定义如下：
const n=图的结点数上限；
type
graphlist=^enode; {边表的指针类型}
enode=record
adjv:1..n;
next:graphlist;
w:real;
end;
vnode=record {顶点表}
v:vtype; {顶点数据类型}
link:graphlist;
end;
adjlist=array[1..n] of vnode;
var
g:adjlist; {邻接表}
n,e:integer; {结点数和边数}
三、图的建立
建立带权无向图的邻接矩阵：
const max=1E5;
n=10;
type graph=array[1..n,1..n] of real;
var i,j,k,e:integer;
g:graph;w:real;
begin
for i:=1 to n do
for j:=1 to n do
g[i,j]:=max;
read(e);
for k:=1 to e do
begin
read(i,j,w);
g[i,j]:=w;
g[j,i]:=w;
end;
for i:=1 to n do
begin
for j:=1 to n do write(g[i,j]);
writeln;
end;
end.
建立有向图结构的邻接表过程：
procedure createlist(var g:adjlist)
begin
read(n,e);
for i:=1 to n do
begin
read(g[i].v);
g[i].link:=nil;
end;
for k:=1 to e do
begin
read(i,j);
new(s);
s^.adjv:=j;
s^.next:=g[i].link;
g[i].link:=s;
end;
end;
习题
一、单选题
1、设无向图的顶点个数为n，则该图最多有( )条边。
A. n-1 B. n(n-1)/2 C .n(n+1)/2 D. n(n-1)
2、N个顶点的连通图至少有( )条边.
A.n-1 B.n C.n+1 D.0
3.在一个无向图中，所有顶点的度数之和等于所有边数的( )倍.
A.3 B.2 C.1 D.1/2
4.N个(n>1)顶点的强连通图中至少含有( )条有向边。
A.n-1 B.n C.n(n-1)/2 D.n(n-1)
5、对于具有e条边的无向图，它的邻接表中有( )个边结点。
A.e-1 B.e C.2(e-1) D.2e
6、具有n个顶点的有向无环图最多可包含( )条有向边。
A.n-1 B.n C.n(n-1)/2 D.n(n-1)
7.一个有n个顶点和n条边的无向图一定是( )
A.连通的 B.不连通的 C.无环的 D.有环的
参考答案：BABBDCD
二、填空题
1、在一个图中，所有顶点的度数之和等于所有边数的( )倍.
2、在一个具有n个顶点的无向完全图中，包含有( )条边；在一个具有n个顶点的有向完全图中，包含有( )边.
3、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为( )和( )条。
4、在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有( )和( )结点。
参考答案:1.2 2.n(n-1)/2 ，n(n-1) 3.e,2e 4.输出，输入
三、运算题
1、对于图T(a)和(b),求出:
(1)每一个图的二元组表示。对于带权图，可将边的权写在该边的后面。
(2)(a)图中每个顶点的度，以及每个顶点的所有邻接点和所有边。
(3)(b)图中每个顶点的入度、出度和度，以及每个顶点的所有入边和出边。
(4)(a)图中从V0到V4的所有简单路径及相应路径长度。
(5)(b)图中从V0到V4的所有简单路径有相应带权路径长度。
2、对于图T(a) 和(b)，给出：
(1)每个图的邻接矩阵。
(2)每个图的邻接表。
图的遍历
图的遍历就是从指定的某个顶点(称为初始点)出发，按照一定的搜索方法对图中的所有顶点各作一次访问的过程。图的遍历比树的遍历要复杂，因为从树根到达树中的每个结点只有一条路径，而从图的初始点到达图中的每个顶点可能存在着多条路径。当顺着图中的一条路径访问过某一顶点后，可能还会顺着另一条路径回到该顶点。为了避免重复访问图中的同一个顶点，必须用标志量来标记每个顶点是否被访问过。
根据搜索方法的不同，图的遍历有两种：一种叫做深度优先搜索遍历，另一种叫做广度优先搜索遍历。
一、深度优先遍历
深度优先搜索遍历类似树的先根遍历，它是一个递归过程，可叙述为：首先访问一个顶点vi(开始为初始点)，并将其标记为已访问过，然后从vi的一个未被访问的邻接点(无向图)或出边邻接点(有向图)出发进行深度优先搜索遍历，当vi的所有邻接点均被访问过时，则退回到上一个顶点vk，从vk的另一个未被访问过的邻接点出发进行深度优先搜索遍历。
如图8(a)的深度优先遍历的具体步骤如下：
1、访问顶点v1,并标记v1已被访问过。选取v1的任意一个未访问过的邻接点(假设选v2)进行深度优先遍历。
2、访问顶点v2，并标记v2已被访问过。选取v2的任意一个未访问过的邻接点(假设选v5)进行深度优先遍历。
3、访问顶点v5，并标记v5已被访问过。选取v5的任意一个未访问过的邻接点(假设选v6)进行深度优先遍历。
4、访问顶点v6，并标记v6已被访问过。v6邻接点都被访问过，回溯到v2，选取v7进行深度优先遍历。
5、访问顶点v7，并标记v7已被访问过。选取v7的任意一个未访问过的邻接点(假设选v3)进行深度优先遍历。
6、访问顶点v3，并标记v3已被访问过。v3邻接点都被访问过，回溯到v7，选取v4进行深度优先遍历。
7、访问顶点v4，并标记v4已被访问过。v4邻接点都被访问过，回溯到v4，v2，v1发现所有点的邻接点都被访问过，至此遍历结束。
得到的深度优先遍历序列为：v1，v2，v5，v6，v7，v3，v4。
深度优先遍历图8(b)得到的结点序列为v1，v2，v4，v8，v5，v3，v6，v7。从vi出发的深度优先遍历递归过程算法如下：
program k1;
type pr=^node;
node=record
data:integer;
next:pr;
w:integer;
end;
qr=record
v:integer;
l:pr;
c:boolean;
end;
rr=array[1..10000]of qr;
var g:rr;m:pr;
procedure b(var g:rr);
var s:pr;n,e:integer;k,i,j:integer;
begin
readln(n,e);
for i:=1 to n do
begin
read(g[i].v);
g[i].l:=nil;g[i].c:=false;
end;
readln;
for k:=1 to e do
begin
readln(i,j);
new(s);
s^.data:=j;
s^.next:=nil;
if g[i].l=nil then
begin
s^.next:=g[i].l;
g[i].l:=s;
end
else
begin
m:=g[i].l;
while m^.next<>nil do
m:=m^.next;
m^.next:=s;
end;
end;
end;
procedure w(i,r:integer;var g:rr);
var p:pr;
begin
if r=1 then
write(g[i].v) else write(',',g[i].v);
g[i].c:=true; r:=r+1;
p:=g[i].l;
while p<>nil do
begin
if not(g[p^.data].c) then w(p^.data,2,g);
p:=p^.next;
end;
end;
begin
b(g);
w(1,1,g);
end.
输入：8 8 {图8(b)}
1 2 3 4 5 6 7 8
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
输出:1,2,4,8,5,3,6,7
二、广度优先搜索遍历
广度优先搜索遍历类似树的按层遍历，其过程为：首先访问初始点vi,并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…,vit并均标记为已访问过，然后再按照vi1,vi2,…,vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。
在广度优先搜索遍历中，先被访问的顶点，其邻接点亦先被访问，所以在算法的实现中需要使用一个队列，用来依次记住被访问过的顶点。算法开始时，将初始点vi访问后插入队列中，以后每从队列中删除一个元素，就依次访问它的每一个未被访问过的邻接点，并令其进队，这样，当队列为空时表明所有与初始点有路径相通的顶点都已访问完毕，算法到此结束。
图8(a)的广度优先遍历的具体步骤如下：
1、访问顶点v1,并标记已被访问过。
2、访问顶点v1的所有未被访问过的邻接点v2,v3,v4,并标记已访问过。
3、访问顶点v2的所有未被访问过的邻接点v5,v6,v7,并标记已访问过。
4、依次访问v3,v4,v5,v6,v7所有被访问过的邻接点，发现已经都被访问，广度优先遍历结束。
得到的广度优先遍历序列为v1,v2,v3,v4,v5,v6,v7。
广度优先遍历图8(b)得到的结点序列为v1, v2,v3,v4,v5,v6,v7,v8。广度优先遍历算法其实是尽可能沿结点的边表进行访问，然后再沿边表对应结点的边表进行访问。因此有关边表的顶点需要保存，以便进一步进行广度遍历。
从vi出发进行广度优先遍历递归过程算法如下：
program k1;
type pr=^node;
node=record
data:integer;
next:pr;
w:integer;
end;
qr=record
v:integer;
l:pr;
c:boolean;
end;
rr=array[1..10000]of qr;
var g:rr;
procedure b(var g:rr);
var s,m:pr;n,e:integer;k,i,j:integer;
begin
readln(n,e);
for i:=1 to n do
begin
read(g[i].v);
g[i].l:=nil;g[i].c:=false;
end;
readln;
for k:=1 to e do
begin
readln(i,j);
new(s);
s^.data:=j;
s^.next:=nil;
if g[i].l=nil then
g[i].l:=s
else begin
m:=g[i].l;
while m^.next<>nil do
m:=m^.next;
m^.next:=s;
end;
end;
end;
procedure w(i:integer;var g:rr);
var p,q:pr;
begin
if not(g[i].c)then begin writeln(g[i].v);g[i].c:=true;end;
p:=g[i].l;q:=g[i].l;
while p<>nil do
begin
if not(g[p^.data].c) then
begin writeln(g[p^.data].v);g[p^.data].c:=true;end;
p:=p^.next;
end;
while q<>nil do
begin
if g[q^.data].l<>nil then w(q^.data,g);q:=q^.next;
end;
end;
begin
b(g);
w(1,g);
end.
输入：8 8 {图8(b)}
1 2 3 4 5 6 7 8
1 2
2 4
4 8
8 5
2 5
1 3
3 6
3 7
输出：1,2,3,4,5,8,6,7
三、非连通图的遍历
前面提到的深度优先遍历和广度优先遍历都只从图的一个顶点开始进行一次遍历，对于连通图可以遍历到图的所有结点，但如果图不连通，则有一部分结点无法访问到。修改很简单，每次选取任意一个没有被遍历过的结点开始一次遍历，重复此操作直到遍历完图的所有结点即可。
与深度优先遍历一样，从一个顶点出发进行一次广度优先遍历只能得到一个连通分支，要遍历整个图，必须再从其他未被访问过的顶点出发继续进行广度优先遍历，直到每一个结点都被访问。整个图按广度优先遍历的过程如下：
procedure traver;
begin
fillchar(visited,sizeof(visited),0); {置所有结点未访问标志}
for i:=1 to n do if visited[i]=false then bfs(i);
{广度优先搜索每一个未访问的结点}
end;
附: Fillchar是个标准过程。有很多好的用处的。
var a:array [1..10] of arrtype;
执行fillchar(a,sizeof(a),0);
当arrtype为
1.real(其他差不多) 使得a中的元素全部成为0.0
2.integer(byte,word,longint,shortint都相同) 全部为0
3.boolean 全部为false
4.char 全部为#0
习题
1、对于下图(a)和(b)，按下列条件分别写出从顶点vo出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
(1) 假定它们均采用邻接矩阵表示。
(2) 假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
图的生成树与最小生成树
在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G′，即：
V(G′)=V(G)和E(G′) ⊆E(G)
若边集E(G′)中的边既将图中的所有顶点连通又不形成回路，则称子图G′是原图G的一棵生成树。
下面简单说明一下既包含连通图G中的全部n个顶点又没有回路的子图G′(即生成树)必含有n-1条边。要构造子图G′，首先从图G中任取一个顶点G′中，此时G′中只有一个顶点，自然是连通的，以后每次添加一条一个端点在图G′中，另一个不在G′中的边，并将不在G′中的端点连通到图G′中，这样不会产生回路。n-1次后，就向G′加入了n-1条边和n-1个顶点，使得G′中n个点连通且不存在回路。
图9中的(b)，(c)，(d)均是图(a)的生成树。对于一个连通网(假设边上的权都非负)生成树的不同，树的权(即树中所有边上的权值总和)。其中权最小的生成树为图的最小生成树。
求图的最小生成树很有实际意义，例如，若一个连通网表示城市之间的通讯系统，网的顶点代表城市，网的边代表城市之间架设通讯线路的造价，各城市之间的距离不同，地理条件不同，其造价也不同，即边上的权不同，现在要求既要连通所有城市，又要使总造价最低，这就是一个求图的最小生成树的问题。
无向图的生成树就是从图的边集中选择一些边，使得这些构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。
1）清空生成树，任取一个顶点加入生成树；
2）在那些一个端点在生成树里，另一个端点不在生成树里的边中，选取一条权最小的边，将它和另一个端点加进生成树；
3）重复步骤2，直到所有的顶点都进入了生成树为止，此时的生成树就是最小生成树。
另法:
①设置一个顶点的集合S1和一个边的集合TE，S1和TE的初始状态皆为空集；
②选定图中的一个顶点k（从此顶点开始求最小代价生成树），将k加入集合S1；
③重复下列操作，直到选取n-1条边。
选取一条权值最小的边(x,y),其中x∈S1，y∈S1；将顶点y加入集合S1，边(x,y)加入TE。
一、Prim(普里姆)算法
设网G=(V,E)是连通的，从顶点V0出发构造G的最小生成树T，记T=(U,A)，则Prim算可由下图的流程图描述。通过例1我们来详细分析Prim算法的使用。
| 置U(T)为{ V0},A(T)为空集 |
| 当U(T)的顶点数<>V(G)的顶点数
|
Prim算法流程
在程序中设立两个辅助数组：closest[1..n]和lowcost[1..n]。lowcost[i]表示顶点i到集合U(当前最小生成树的顶点集合)的距离；而closest[i]表示集合U中某个顶点，该顶点和顶点i组成的边的权值即为lowcost[i]。初始时，U={V0}，所以closest[i]=V0(i=1,2,3,…,n,i≠V0)，而lowcost[i]=cost[V0,i]。然后组织循环，扫描数组lowcost，寻找顶点k,使k满足：lowcost[k]=min{lowcost[i]|i∈V-U}。则(k,closest[k])是本次找到的权值最小的边并输出，令lowcost[k]=0,表示顶点k并入集合U。在程序中，并没有真正设立集合U，但集合U是存在的，某个顶点i(1≤i≤n)满足lowcost[i]=0,即顶点i到U的距离为0，那么i就在集合U里面。
每当找到一个k并入集合U后，则要判断那些V-U内的顶点j到集合U的距离是否改变，如果cost(k,j)<lowcost[j]，则令lowcost[i]=cost(k,j),closest=k,即顶点j到集合U的距离改由边(k,i)的权值cost(k,j)定义。如此反复寻找顶点k,直到网G的全部顶点都并入集合U。
Prim(普里姆)算法思想：任意时刻的中间结果都是一棵树。从一个点开始，每次都花费最小的代价，用一条边把不在树中的点加进来。
Prim(普里姆)算法的主要过程：
program aa;
const nv=5;
mat:array[1..nv,1..nv] of integer=
((0 ,2, 12,10, 0),
(2 ,0, 8 ,0 , 9),
(12,8, 0 ,6 , 3),
(10,0, 6 ,0 , 7),
(0 ,9, 3 ,7 , 0));
type
cost=array[1..nv,1..nv] of integer;
procedure prim( v0:integer);
var lowcost,closest:array[1..nv] of integer;
i,j,k,min:integer;
begin
for i:=1 to nv do
begin
lowcost[i]:=mat[v0,i];
closest[i]:=v0;
end;
for i:=1 to nv-1 do
begin
min:=32767;
for j:=1 to nv do
if (lowcost[j]<min) and (lowcost[j]<>0) then
begin
min:=lowcost[j];
k:=j;
end;
writeln(closest[k]:5,k:5,mat[closest[k],k]:5);
lowcost[k]:=0; mat[i,k]:=0;
for j:=1 to nv do
if (mat[k,j]>lowcost[j]) and (mat[j,k]<>lowcost[k]) then
lowcost[j]:=mat[k,j];
for j:=1 to nv do
if (mat[k,j]<lowcost[j])and (mat[k,j]<>0) then
begin
lowcost[j]:=mat[k,j];
closest[j]:=k;
end;
end;
end;
begin
prim(1);
end.
例1 网络建设问题
某大学准备在校园中构建校园网络，已知在校园中选好了N(N≤1000)个点，并准备在这些点安装网络设备和电脑。若要将N个点互相连接起来，问怎样连线布线才能使得总距离最短，两点间的布线长度等于这两个点的几何距离。
●输入数据
输入文件的第一行为一个正整数N。
接下来N行，每行2个数U，V，表示坐标。
●输出数据
输出最短距离(保留两位小数).
●输入输出示例
input.txt
5
0 0
0 1
0 -1
1 0
-1 0
output.txt
4.00
参考程序
const maxn=1000;
var
n:integer;
x,y,dist:array[1..maxn] of double;
vis:array[1..maxn] of boolean;
procedure init;
var
i:integer;
begin
read(n);
for i:=1 to n do
read(x[i],y[i]);
end;{init}
function getdist(a,b:integer):double;
begin
getdist:=sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));
end;{getdist}
procedure solve;
var
i,k:integer;
answer,min:double;
begin
answer:=0;
for i:=1 to n do
begin
dist[i]:=1e99;
vis[i]:=false;
end;
dist[1]:=0;
repeat
min:=1e100;
for i:=1 to n do
if (not vis[i]) and (dist[i]<min) then
begin
min:=dist[i];
k:=i;
end;
if (min>1e99) then break;
answer:=answer+min;
vis[k]:=true;
for i:=1 to n do
if (not vis[i]) and (getdist(k,i)<dist[i]) then
dist[i]:=getdist(k,i);
until false;
writeln(answer:0:2);
end;{solve}
begin
init;
solve;
end.
数据结构综合测试
一、填空题
1、在计算机科学中，算法是描述计算机解决给定问题的操作过程。通常，一个算法必须具备五个重要特性，即：( )、( )、( )、( )、( )。
2、在线性结构、树型结构和图型结构中，元素之间的联系分别对应为( )、( )、( )。
3、假定有三个元素A，B，C进栈，进栈次序为ABC，试写出所有可能的出栈序列：(
）。
4、队列是限定所有的插入操作在表的一端进行，而删除操作在表另一、端进行的线性表。它操作的是按（ ）原则进行的。用数组q[1..m]来存储队列，为了指示队首和队尾，需引进两 个指针：F——指向实际队首元素的前一个位置，R——指向实际队尾元素所在位置；循环队列，当R=（ ）后，一旦R=（ ），则为队满；出队时，当R=（ ），则为空排。
5、中缀算术表达式3*(5+x)/y-z所对庆的前缀算术表达式和后缀表达式分别为：（
）和（ ）。
6、已知一个图如下图(a)所示，它的邻接表如下图(b)所示，试写出从VA出发分别按深度优先遍历和广度优先遍历得到的顶点序列。
深度优先遍历：
广度优先遍历：
7、设S[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是______________，栈为满的条件是____________________。
8、有向图G用邻接矩阵A[1..n,1..n]存储，其第I行的非零元素之和等于顶点I的______________。
9、一棵二叉树的前序序列和中序序列分别如下，画出该二叉树。
前序序列：ABCDEFGHIJ
中序序列：CBEDAGHFJI
10、对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。
{4,5,6,7,10,12,15,18,23}
11、在有n个结点的无向图中，其边数最多为___________。
12、在有n个顶点的有向图G中最多有_________________________条弧。
13、已知栈的输入序列为1，2，3，…n,输出序列为a1,a2, …an,a2=n的输出序列共有___________种输出序列。
14、3个结点可构成__________棵不同形态的树。
15、一棵二叉树的前序、中序、后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。
前序____B____F____ICEH____G
中序D____KFIA____EJCG
后序____K____FBHJ____G____A
二、选择题
1、设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是( )
(1) A,B,C,D (2) D,C,B,A
(3) A,C,D,B (4) D,A,B,C
2、链表不具有的特点是( )
(1) 可随机访问任一元素 (2) 插入删除不需要移动元素
(3) 不必事先估计存储空间 (4) 所需空间与线性表长度成正比
3、在有N个叶子结点的哈夫曼树中，其结点总数为( ).
(1) 不确定 (2) 2n (3) 2n+1 (4) 2n-1
4、任何一个无向连通图的最小生成树( )。
(1) 只有一棵 (2) 有一棵或多棵 (3) 一定有多棵 (4) 可能不存在
5、将一棵有100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为( )。
6、队列操作的原则是( )。
(1) 先进先出 (2) 后进先出 (3) 只能进行插入 (4) 只能进行删除
7、有64个结点的完全二叉树的深度为( )（根的层次为1）。
(1) 8 (2) 7 (3) 6 (4) 5
参考答案:
一、填空
1有穷性，确定性，有效性，有0个或多个输入，有1个或多个输出。
2、1:1,1:n,n:m
3、ABC，ACB，BAC，BCA，CBA。
4、先进先出，R+1，F，F
5、-/*3+5XYZ，35X+*Y/Z-。
6、深度优先遍历：VA →VB →VD →VF →VC →VE
广度优先遍历：VA →VB →VD →VF →VC →VE
7、top=0 top=maxsize
8、出度
9、这棵二叉树如下：
10、WPL=299，哈夫曼树如下：
11、n(n-1)/2
12、n(n-1)
13、n-1
14、2
15、前：ABDFKICEHJG 中：DBKFIAHEJCG 后：DKIFBHJEGCA
二、选择题：
1-7：4 1 4 2 1 1 2
