静压试验*问题描述：
建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法:
设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵：
1，若(Vi,Vj)∈E 或<Vi,Vj>∈E；
A[i,j]={
1，反之
图5-2中有向图G1和无向图G2的邻接矩阵分别为 M1和 M2:
M1=┌ 0 1 0 1 ┐
│ 1 0 1 0 │
│ 1 0 0 1 │
└ 0 0 0 0 ┘
M2=┌ 0 1 1 1 ┐
│ 1 0 1 0 │
│ 1 1 0 1 │
└ 1 0 1 0 ┘
注意无向图的邻接是一个对称矩阵，例如 M2。
用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。因此其类型定义如下：
VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 图的当前顶点数和弧(边)数
GraphKind kind; // 图的种类标志
若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下：
type adjmatrix=array[1..vnum,1..vnum]of adj;
利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。
对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即
n n
D(Vi)＝∑A[i,j] （或∑A[i,j]）
j=1 i=1炉灶节能器
对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi的入度ID(Vi)为第i列元素之和。即
n n
OD(Vi)＝∑A[i,j]， OD(Vi)＝∑A[j,i]）
j=1 j=1
用邻接矩阵也可以表示带权图，只要令
Wij, 若<Vi,Vj>或(Vi,Vj)
A[i,j]＝{
∞ , 否则。
其中Wij为<Vi,Vj>或(Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型定义应作如下的
修改： adj:weightype ; {weightype为权类型}
图5-6列出一个网和它的邻接矩阵。
┌ ∞ ３ １ ∞ ∞ ┐
│ ∞ ∞ ５ １ ∞ │
│ ∞ ∞ ∞ ∞ ∞ │
│ ∞ ∞ ６ ∞ ∞ │
└ ∞ ３ ２ ２ ∞ ┘
(a)网 (b)邻接矩阵
图5-6 网及其邻接矩阵
对无向图或无向网络，由于其邻接矩阵是对称的，故可采用压缩存贮的方法，仅存贮下三角或上三角中的元素(但不含对角线上的元素)即可。显然，邻接矩阵表示法的空间复杂度O()。
无向网邻接矩阵的建立方法是：首先将矩阵A的每个元素都初始化成∞。然后，读入边及权值(i,j,wij),将A的相应元素置成Wij。
*深度优先搜索
深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。 以图7.13(a)中无向图G4为例，深度优先遍历图的过程如图7.13(b)所示。假设从顶点V1出
发进行搜索，在访问了顶点V1后，选择邻接点V2。因为V2未曾访问，则从V2新型模板支撑出发进行搜索。依次类推，接着从V4,V8,V5出发进行搜索。在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到V8。由于同样的理由，搜索继续回到V4，V2直至V1，此时由于V阳光房天窗1的另一个邻接点为被访问，则搜索又从V1到V3，再继续进行下去。由此得到顶点的访问序列为：
V1 V2 V4 V8 V5 V3 V6 V7
显然，这是一个递归的过程。为了在遍历过程中便于区别顶点是否已被访问，需附设访问标志数组-1],其初值为0，一但某个顶点被访问，则其相应的分量置为1。
*广度优先搜索
假设从图中某顶点v出发，在访问了v之后一次访问v的各个未曾访问的扩大邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的邻接点”先于“后被访问的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中的顶点都
被访问为止。换句话说，广度优先遍历图的过程就是以v为起始点，有远至近，依次访问和v有路径相通且路径长度为1、2……的顶点。例如，对图G4进行广度优先搜索遍历的过程如图7.13（3）所示，首先访问v1和v1的邻接点v2和v3，然后依次访问v2的邻接点v4和v5及v3的邻接点v6和v7，最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成了图的遍历。得到的顶点访问序列为
V1 V2 V3 V4 V门栓5 V6 V7 V8
和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1、2…的顶点。
2、图的输出
图的邻接矩阵是一个二维数组，运用for语句的嵌套依次输出。
Y
N
Y
N Y
N 主程序流程图
Y
N
图的构造流程图
1、无向图邻接矩阵的建立算法如下：
procedure build-graph; {建立无向图的邻接矩阵}
begin
for i:=1 to n do read(G.vertex[i])； {读入n个顶点的信息}
for i:=1 to n do
for j:=1 to e do
G.arcs[i][j] =0；
{将邻接矩阵的每个元素初始化成0 }
for k:=1 to e do {e为边的数目}
[ read(i,j,w) {读入边<i,j>和权}G.arcs[i][j]:=w]
G.arcs[i][j]＝G.arcs[i][i]｛置对称弧｝
end；
该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2),而e<n2，所以上述算法的时间复杂度是O(n2)。
2、无向网邻接矩阵的建立算法如下：
procedure build-graph; {建立无向网的邻接矩阵}
begin
for i:=1 to n do read(G.vertex[i])； {读入n个顶点的信息}
for i:=1 to n do
for j:=1 to e do
G.arcs[i][j] =maxint；
{将邻接矩阵的每个元素初始化成maxint,计算机内∞用最大事数maxint表示}
for k:=1 to e do {e为边的数目}
[ read(i,j,w) {读入边<i,j>和权}G.arcs[i][j]:=w; G.arcs[i][j]:=w] end；
该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2),而e<n2柱层析，所以上述算法的时间复杂度是O(n2)。
3、图的深度优先遍历算法分析
begin
for i:=1 to n do(visited[i]){初始化标志数组}
while （i<n）
｛for：i＝1 to n do｛按要求访问邻接点｝｝
end
当用二维数组表示邻接矩阵作图的存储结构时，查每个顶点的邻接点所需时间为O(n2)，其中n为图中顶点数。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议