数据结构与算法6 - 图文(2)

ENQUEUE (k, Q); while ( !EMPTY (Q) ){

i = FRONT(Q)->element;

DEQUEUE(Q);

p = G->vexlist[i].firstedge; while ( p ){ if (!visited[p->adjvex ]){ cout << G->vexlist[ p->adjvex ].vertex; visited[ p->adjvex ]=TRUE; ENQUEUE ( p->adjvex , Q );

}

p = p->next;

}

}

} int main() { AdjGraph G; IniADJGraph(&G);

VertexData v[6] = {'a', 'b', 'c', 'd', 'e', 'f'};

EdgeData e[6][NumVertices] = {{0, 1, 0, 1, 0, 1}, {1, 0, 1, 1, 1, 0}, {0, 1, 0, 0, 1, 0}, {1, 1, 0, 0, 1, 1}, {0, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 0, 0}}; CreateADJGraph(&G, v, e, 6); DFSTraverse(G); cout << endl; BFS1(&G, 1); cout<

}

//连接矩阵表示

BOOLEAN visited[NumVertices]; int dfn[NumVertices];//深度优先 void DFSTraverse(MTGraph G) {

int i , count = 1;

for ( i = 0; i < G.n; i++ ) visited [i] =FALSE; for ( i = 0; i < G.n; i++ ) if ( ! visited[i] ) DFS2( &G, i ); }

void DFS2(MTGraph *G, int i) { int j;

static int count=0;

cout<vexlist[i]; visited[i]=TRUE; dfn[i]=count; count ++;

for( j=0; jn; j++)

if((G->edge[i][j] == 1) && !visited[j] ) DFS2( G, j ); }

int bfn[NumVertices]; //广度优先 void BFS2 (MTGraph *G, int k) {

int i , j; QUEUE Q; MAKENULL(Q);

cout << G->vexlist[ k ]; visited[ k ] = TRUE; ENQUEUE (k, Q); while ( ! EMPTY (Q) )

{

i=FRONT(Q)->element;

DEQUEUE(Q);

for(j=0; jn; j++) {

if ( G->edge[ i ][ j ] ==1 && !visited[ j ])

{

cout << G->vexlist[ j ];

visited[j]=TRUE; ENQUEUE( j , Q );

} } } } int main() {

MTGraph G; IniMGraph(&G);

VertexData v[6]={'a', 'b', 'c', 'd', 'e', 'f'};

EdgeData e[6][NumVertices] = {{0, 1, 0, 1, 0, 1}, {1, 0, 1, 1, 1, 0}, {0, 1, 0, 0, 1, 0}, {1, 1, 0, 0, 1, 1}, {0, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 0, 0}}; }

CreateMGraph(&G, v, e, 6); PrintMT(&G); DFSTraverse(G); cout<

四、基于深度优先搜索算法，写出求无向图连通分量的算法。

typedef char VertexData; typedef int EdgeData; typedef struct{

VertexData vexlist[NumVertices];

EdgeData edge[NumVertices][NumVertices]; int n; int e; } MTGraph;

bool visited[NumVertices]; int dfn[NumVertices]; void DFS2(MTGraph *G, int i) {

int count = 0; cout << G->vexlist[i]; visited[i]=true;

dfn[i]=count; count++;

for( int j=0; jn; j++)

if((G->edge[i][j] == 1) && !visited[j] ) DFS2( G, j ); }

void DFSTraverse(MTGraph G) {

for ( int i = 0; i < G.n; i++ ) visited [i] = false; int count = 0;

for ( int i = 0; i < G.n; i++ ) if ( ! visited[i] ){ count++;

cout << count << \ DFS2( &G, i ); } } int main() {

MTGraph G;

EdgeData e[NumEdges][NumVertices]; int n; cin >> n;

for ( int i = 0; i < n; i++ ) for ( int j = 0; j < n; j++ ) cin >> e[i][j]; VertexData v[NumEdges]; for ( int i = 0; i < n; i++ ) v[i] = 'a' + i - 0;

CreateMGraph(&G, v, e, n); DFSTraverse(G); cout<

五、网络G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。

六、下图是一个无向带权图，请给出该图的邻接矩阵，并分别按Prim算法和Kruskal算法求最小生成树（包括算法代码和画图）。

邻接矩阵如下：

a b c d e f

a b c d e f

0 6 3 0 0 0 6 0 0 1 0 5 3 0 0 6 6 0 0 1 6 0 0 5 0 0 6 0 0 2 0 5 0 5 2 0

最小生成树：