4.网的邻接矩阵表示 类似地可以定义网的邻接矩阵为: 若(ij)∈E(G)或(ij)∈E(G) A[i=10 其它情形 网及网的邻接矩阵见图7-10。 89 o0o24 82 7 47 (a)网G5 (b)网G5的邻接矩阵示意图 图7-10网及邻接矩阵示意图
4． 网的邻接矩阵表示 类似地可以定义网的邻接矩阵为： wij 若（i,j）∈E(G)或〈i,j〉∈E(G) A[i][j]= 0 若i=j ∞ 其它情形 网及网的邻接矩阵见图7-10。 3 9 4 7 8 2 7 1 2 4 6 8 9 6 1 3 (a) 网 G5 (b) 网 G5 的邻接矩阵示意图 图 7-10 网及邻接矩阵示意图 5 3 1 2 4 3 6 1 2 4 8 9 7
xs5.图的邻接矩阵数据类型描述 图的邻接矩阵数据类型描述如下 const int n= maxn: ∥图中顶点数 const int e=maxe ∥图中边数 struct grap h elemtype [n+1 ∥存放顶点信息 vl,v2,wn,不使用v0]存储空间 int arcs+1l[n+l] ∥邻接矩阵
5． 图的邻接矩阵数据类型描述 图的邻接矩阵数据类型描述如下: const int n= maxn； // 图中顶点数 const int e=maxe ； // 图中边数 struct graph { elemtype V[n+1]; // 存放顶点信息 v1,v2,….vn，不使用v[0]存储空间 int arcs[n+1][n+1] // 邻接矩阵 };
xs'6.建立无向图的邻接矩阵 void creatadj(graph &g) ii.( int i, j, k for (k-l; k<=n; k++) cin> /输入顶点信息 Xfor(i=1;i<=n;计+) for(=1;j<=n;j++) g arcs[]=0 for(k=1;,k<=e;k++) i cin>>i>> /输入一条边(ij g arcs[[l=1; garcs[=1; j 该算法的时间复杂度为O(n2)
6． 建立无向图的邻接矩阵 void creatadj(graph &g) { int i, j,k ; for (k=1; k<=n; k++) cin>>g.v[k]; //输入顶点信息 for (i=1; i<=n; i++ ) for (j=1; j<=n; j++) g.arcs[i][j]=0; for (k=1; k<=e; k++) { cin>>i>>j; //输入一条边(i,j) g.arcs[i][j]=1;g.arcs[j][i]=1;}} 该算法的时间复杂度为O（n 2）
小?7建立有向图的邻接矩阵 void creatadj(graph &g) i int i,j, k for(k-l; k<-n; k++) cin>>g v[k /输入顶点信息 for(i=1;i<=n;,i++) for (=1; j<=n:j++) g arcs[-=0 for(k-l; k<=e; k++) cn>>1>>1 /输入一条弧<j g arcs[]1; ) 该算法的时间复杂度为O(n2)
7.建立有向图的邻接矩阵 void creatadj(graph &g) { int i, j,k ; for (k=1; k<=n; k++) cin>>g.v[k]; //输入顶点信息 for (i=1; i<=n; i++ ) for (j=1; j<=n; j++) g.arcs[i][j]=0; for (k=1; k<=e; k++) { cin>>i>>j; //输入一条弧<i,j> g.arcs[i][j]=1;}} 该算法的时间复杂度为O（n 2）
它8建立无向网的邻接矩阵 I void creatadj( graph &g) Hi"( int 1, j, k, float w, for(k-1; k<=n; k++) cin>>g v[k ∥输入顶点信息 for (i=l; i 1+ for(=1;j<=n;j++) if(i==jg.arcs[1=0; else g arcs[ll=oo for(k-1; k<=e; k++) {cin>>1>>j>>w; /输入一条边(ij)及权值 g. arcsilll-w; g. arcslll-w,j 该算法的时间复杂度为O(n2)
8.建立无向网的邻接矩阵 void creatadj(graph &g) { int i, j,k ; float w; for (k=1; k<=n; k++) cin>>g.v[k]; //输入顶点信息 for (i=1; i<=n; i++ ) for (j=1; j<=n; j++) if (i==j) g.arcs[i][j]=0; else g.arcs[i][j]=∞; for (k=1; k<=e; k++) { cin>>i>>j>>w; //输入一条边(i,j) 及权值w g.arcs[i][j]=w;g.arcs[j][i]=w;}} 该算法的时间复杂度为O（n 2）