c++ 建图

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)。
{//邻接矩阵表示法的各个数据结构
VrType adj;// 顶点关系类型。对无权图，用或表示相邻否；对带权图，则为权值类型。
InfoType *info;// 该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
一、设计题目：图的建立及输出
*问题描述：
建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
二、算法设计的思想
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 │
intelem1[MAX_VERTEX_NUM];
inttop;
}SeqStack;
intLocateVertex(MGraph G,VertexType v);
voidCreateUDG(MGraph &G);
voidCreateUDN(MGraph &G);
voidDepthFirstSearch1(MGraph G);
#defineMAX_INFO 20
typedefintVrType;//定义新的类型
typedefintInfoType;
typedefcharVertexType;
typedefenum
{DG,DN,UDG,UDN}GraphKind;//有向图,有向网,无向图,无向网
typedefstructArcCell
ch=getchar();// ch吃掉回车符
i=LocateVertex(G,v1); j=LocateVertex(G,v2);
if(IncInfo)scanf("%d",&G.arcs[i][j].info);
G.arcs[i][j].adj=G.arcs[j][i].adj=1;// 置<v1,v2>的对称弧<v2,v1>
3、图的深度优先遍历算法分析
begin
for i:=1 to n do(visited[i]){初始化标志数组}
while （i<n）
｛for：i＝1 to n do｛按要求访问邻接点｝｝
end
当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n2)，其中n为图中顶点数。
4、图的广度优先遍历算法分析
{//用于返回输弧端点所表示的数值
intj=0,k;
for(k=0;k<G.vexnum;++k)
if(G.vertex[k]==v)
{j=k;break;}
return(j);
}
voidCreateUDG(MGraph &G)
{// 采用数组(邻接矩阵)表示,构造无向图
inti,j,k,IncInfo;
AdjMatrix arcs;// 邻接矩阵
intvexnum, arcnum;// 图的当前顶点数和弧(边)数
GraphKind kind;// 图的种类标志
若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下：
type adjmatrix=array[1..vnum,1..vnum]of adj;
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 }
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；
V1V2V4V8V5V3V6V7
显然，这是一个递归的过程。为了在遍历过程中便于区别顶点是否已被访问，需附设访问标志数组visted[0...n-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。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成了图的遍历。得到的顶点访问序列为
{将邻接矩阵的每个元素初始化成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)。
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为权类型}
└ 1 0 1 0 ┘
注意无向图的邻接是一个对称矩阵，例如 M2。
用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。因此其类型定义如下：
VertexType vertex[MAX_VERTEX_NUM];// 顶点向量
for(i=0;i<G.vexnum;++i)// 初始化邻接矩阵
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=0;
G.arcs[i][j].info=NULL;// {adj,info}
}
for(k=0;k<G.arcnum;++k)
{
scanf("%c %c",&v1,&v2);
V1V2V3V4V5V6V7V8
和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1、2…的顶点。
2、图的输出
图的邻接矩阵是一个二维数组，运用for语句的嵌套依次输出。
三、算法设计分析
1、无向图邻接矩阵的建立算法如下：
voidBreadthFirstSearch1(MGraph G);
intCreateGraph(MGraph &G);
voidDisplay(MGraph G);
/* Graph.cpp */
#include"Graph.h"
intLocateVertex(MGraph G,VertexType v)
{
VertexType vertex[MAX_VERTEX_NUM];// 顶点向量
AdjMatrix arcs;// 邻接矩阵
intvexnum, arcnum;// 图的当前顶点数和弧(边)数
GraphKind kind;// 图的种类标志
} MGraph;
typedefstruct
{//设置栈
begin
for i:=1 to n do(visited[i]){初始化标志数组}
while （i<n）
｛for：i＝1 to n do｛if…..if…..｝｝
end
二维数组表示邻接矩阵作图的存储结构，其中n为图中顶点数,查找每个顶点的邻接点所需时间为O(n2)。