文档介绍：第 7 章图
一、基础知识题
,则该图最多有多少条边?
【解答】n(n-1)/2
,其边的个数至少为多少?
【解答】n-1
,至少需要多少条弧?
【解答】n
n个顶点的完全有向图含有弧的数目是多少?
【解答】n(n-1)
,最少有多少个连通分量,最多有多少个连通分量。
【解答】1, n
,对吗?
【解答】对
=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},写出对该图从顶点a出发进行深度优先遍历可能得到的全部顶点序列。
【解答】abedfc, acfdeb, aebdfc, aedfcb
在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度是多少?
【解答】O(n+e)
,e条边的无向图是一个森林,则该森林中必有多少棵树?
【解答】n-e
n个顶点的无向图的邻接矩阵至少有多少非零元素?
【解答】0
:具有n个顶点和多于n-1条边的无向连通图G一定不是树。
【证明】具有n个顶点n-1条边的无向连通图是自由树,即没有确定根结点的树,每个结点均可当根。若边数多于n-1条,因一条边要连接两个结点,则必因加上这一条边而使两个结点多了一条通路,即形成回路。形成回路的连通图不再是树。
,使其邻接矩阵为下三角形且主对角线为全零的充要条件是该图是无环图。
【证明】该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度的大小进行顺序编号。)
=(V,E)以邻接表存储,如图所示,试画出从顶点1出发所得到的深度优先和广度优先生成树。
略
已知一个图的顶点集V和边集E分别为:
V={0,1,2,3,4,5,6,7};
E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>};
若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照顶点序号从小到大的次序链接的,则按教材中介绍的进行拓扑排序的算法,写出得到的拓扑序列。
【解答】1-3-6-0-2-5-4-7-8
~ 略
二、算法设计题
设无向图G有n个顶点,m条边。试编写用邻接表存储该图的算法。
void CreatGraph (AdjList g)∥建立有n个顶点和m 条边的无向图的邻接表存储结构
{ int n,m;
scanf("%d%d",&n,&m);
for(i=0,i<n;i++)∥输入顶点信息,建立顶点向量
{scanf(&g[i].vertex); g[i].firstarc=null;}
for(k=0;k<m;k++)∥输入边信息
{scanf(&v1,&v2);∥输入两个顶点
i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2);∥顶点定位
p=(ode *)malloc(sizeof(ode));∥申请边结点
p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p; ∥将边结点链入
p=(ode *)malloc(sizeof(ode));
p->adjvex=i; p->next=g[j].firstarc; g[j].frstarc=p;
}∥for
}∥算法CreatGraph结束
已知有向图有n个顶点,请编写算法,根据用户输入的偶对建立该有向图的邻接表。
void CreatAdjList(AdjList g)∥建立有向图的邻接表存储结构
{ int n;
scanf("%d",&n);
for(i=0;i<n;j++)
{scanf(&g[i].vertex); g[i].firstarc=null;}∥输入顶点信息,下标从0开始
scanf(&v1,.&v2);