如果结果不匹配，请 
更多“对于下面的带权有向图，写出其相邻矩阵，并画出其邻接表表示及邻…”相关的问题
点到某一指定顶点v的最短路径，例如，对于图8-47(a)所示的带权有向图，用该算法求得的从各顶点到顶点2的最短路径如图8-47(b)所示.
关于最短路径的读法以顶点0为例，在从顶点0到顶点2的最短路径上，顶点0的后继为顶点1(即path[0]=1)，顶点1的后继为顶点3(即path[1]=3)，顶点3的后继顶点为2(即path[3]=2).
编写一个算法，求解一个带权有向图的单目标最短路径问题。假设图G的顶点数据的类型为char，边上权值的数据类型为float。
下面是求无向连通图的最小生成树的一种算法：
//设图中总顶点数为n，总边数为m
将图中所有的边按其权值从大到小排序为
;
若图不再连通，则恢复e1;(m=m+1);I=i+1;
(1)试间这个算法是否正确，并说明原因。
(2)以图8-44所示的图为例，写出执行以上算法的过程。
JPEG标准中，需要对DCT变换后的系数进行量化。采用量化矩阵
.jpg)
对下面的系数矩阵进行均匀量化，写出量化和反量化后的结果。
.jpg)
关联矩阵(incidence matrix)是描述和实现图算法的另一重要方式，对于含有n个顶点、e条边的图，对应的关联矩阵I[][]共有n行e列。在无向图中，对于任意的0≤i＜n和0≤j＜e，若第i个顶点与第j条边彼此关联，则定义I[[i][j]=1;否则，定义I[[i][j]=0。
a)关联矩阵与邻接矩阵有何联系？
b)有向图的关联矩阵应如何定义？
c)有向图的关联矩阵，与邻接矩阵又有何联系？
d)基于关联矩阵，可以解决哪些问题？试举一例。
对于如图8-5所示的有向图，试写出：
(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树;
(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树。
●试题六
阅读以下说明和C++代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数;a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值;c为二维数组，存储有向网中每一对顶点间的最短路径长度;kay为二维数组，存储最短路径，kay［i］［j］=k表示顶点i 到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有：
Input():输入有向网的顶点数、各条弧及权值，建立带权领接矩阵a。若顶点i到顶点j有弧，则a［i］［j］取弧上的权值，否则a［i］［j］的值取NoEdge。
AllPairs();用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。
OutShortestPath(int i,int j):计算顶点i到顶点j的最短路径。
outputPath(int i,int j):输出顶点i到顶点j的最短路径上的顶点。
Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1，C2，…，Cn,其中C0是已知的带权邻接矩阵，a,Ck(i,j)(0≤i,j＜n)表示从顶点i到顶点j的中间顶点序号不大于k 的最短路径长度。如果i到j的路径没有中间顶点，则对于0≤k＜n,有Ck(i,j)=C0(i,j)=a［i］［j］。递推地产生C1，C2，…，Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。
【C++代码】
#include＜iostream．h＞
＃define NoEdge 10000 //当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示
void Make2DArray(int * * &x,int rows,int cols);
class AdjacencyWDigraph{
private
int n;//有向网中的顶点数目
int**a;//存储顶点间弧上的权值
int**c;//存储计算出的最短路径长度
int**kay;//存储求出的最短路径
pubic:
int Vertices()const {return n;}
void AllPairs();
void Input();//输入有向网的顶点数、各条弧及权值，建立邻接矩阵a
void OutShortestPath(int i,int j);//计算顶点i到j的最短路径(试卷中未列出)
~AdjacencyWDigraph();//析构函数(试卷中未列出)
private:
void outputPath(int i,int j);
};
void AdjacencyWDigraph::AllPairs()
{int i,j,k,t1,t2,t3;
for(i=1;i＜=n;k++)
for(j=1;j＜=n;++j)
{c［i］［j］= (1) ;kay［i］［j］=0;}
for(k=1;k＜=n;k++)
for(i=1;i＜=n;i++){
if(i==k) continue;
t1=c［i］［k］;
for(j=1;j＜=n;j++){
if(j==k||j==i)continue;
t2=c［k］［j］;t3=c［i］［j］;
if(t1!=NoEdge && t2!=NoEdge &&(t3==NoEdge||t1+t2＜t3))
{c［i］［j］= (2) ；kay［i］［j］= (3) ;}
}//for
}//for
}
void AdjacencyWDigraph:: outputPath(int i,int j)
{//输出顶点i到j的最短路径上的顶点
if(i==j)return;
if(kay［i］［j］==0)cout＜＜j＜＜′′;
else { outputPath(i, (4) ); outputPath((5) );}
}
void Adjacency WDigraph::Input()
{int i,j,u,v,w,E;
cout＜＜″输入网中顶点个数：″;cin＞＞n;
cout＜＜″输入网中弧的个数:″;cin＞＞E;
Make2DArray(a,n+1,n+1);
for(i=1;i＜=n;i++)
for(j=1;j＜=n;j++)a［i］［j］=NoEdge;
for(i=1;i＜=n;i++)a［i］［i］=0;
Make2DArray(c,n+1,n+1);
Make2DArray(kay,n+1,n+1);
for(i=1;i＜=E;i++){
cout＜＜″输入弧的信息(起点终点权值)：″；cin＞＞u＞＞v＞＞w;a［u］［v］=w;
}
}
void Make2DArray(int**&x,int rows,int cols)
{int i,j;
x=new int*［rows+1］;
for(i=0;i＜rows+1;i++)x［i］=new int ［cols+1］;
for(i=1;i＜=rows;i++)
for(j=1;j＜=cols;j++＝x［i］［j］=0;
}
