数据结构与算法

的数组参与使用）

C

。

二、填空题

1

、若无向图

G

中顶点数为

n

，则图

G

至多有

n*( n-1)/2

条边；若

G

为有向图，则 图

G

至多

有

n *(n-1)

条边。

2

、图的存储结构主要有两种，分别是

邻接矩阵

和

邻接表

。

3

、若

G

是有向图，则把邻接到顶点

v

的顶点数目或边数目称为顶点

v

的

入度

；把邻接于

顶点

v

的顶点数目或边数目称为顶点

v

的

出度

。

4

、已知 一个图的邻接矩阵表示，计算第

j

个顶点的入度的方法是

将第

j

列的数相加

， 计算

第

j

个顶点的出度的方法是

将第

j

行的数相加

。

5

、若将图中的每条边都赋予一个权 ，则称这种带权的图为

网络

。

6

、无论 是有向图还是无向图，顶点数

n

、边数

e

和各顶点的度

D(v

i

)

之间的关系为：

D(Vi)=2e e=n(n-1)/2

。

7

、

若路径 上第一个顶点

v

1

与最后一个顶点

v

m

重合

,

则称这样的简单路径为

回路或环

。

8

、

如果图中任意一对顶点都是连通的

,

则称此图是

连通图

< br>；非连通图的极大连通子图叫做

连通分量

。

9

、

创建一个邻接矩阵图的复杂度是

0(n 2 )

；创建一个链接表图的复杂度是

O

（

< br>n+e

）

< br>三、已知一个无向图如下图所示，试给出该图的邻接矩阵和邻接表存储示意图（分别用矩

< br>阵和数组链表图表示）

，并编程分别实现该图的邻接矩阵表示和邻接表表示，要求 编写两种

表示方法的存储结构、相关基本操作，并在主函数中创建该图。

A. n-1

B. n+1

C. n

D. n+e

6

、下列说法正确的是

C

。

A.

有向图的邻接矩阵一定是不对称的

B.

有向图的邻接矩阵一定是对称的

C.

无向图的邻接矩阵一定是对称的

D.

无向图的邻接矩阵可以不对称

邻接矩阵

:

邻接表存储示意图

:

邻接矩阵表示：

#include

using namespace std;

typedef char VertexData;

typedef int EdgeData;

typedef struct{

VertexData vexlist[NumVertices];

EdgeData edge[NumVertices][NumVertices];

int n;

int e;

} MTGraph;

void IniMGraph(MTGraph *G)

{

}

void NewNode(MTGraph *G

, VertexData v)

{

for(int i=0; i

G->n=0;

G->e=0;

for(int j=0; j

G->edge[i][j]=0;

}

G->vexlist[G->n]=v;

G->n++;

void DelNode(MTGraph *G

, int m)

{

}

void SetSucc(MTGraph *G

, int v1, int v2, EdgeData w)

{

}

if(!IsEdge(G

, v1, v2))

{

}

G->edge[v1][v2]=w;

G->edge[v2][v1]=w;

G->e++;

G->n--;

for(i=m; in-1; i++)

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

G->edge[j][i]=G->edge[j][i+1];

for(i=m; in-1; i++)

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

G->edge[i][j]=G->edge[i+1][j];

for(i=0; in; i++)

{

}

if(G->edge[i][m]!=0)

G->e--;

for(i=m; in-1; i++)

G->vexlist[i]=G->vexlist[i+1];

int i, j;

if(G->n==0 || m>=NumVertices)

return;

void DelSucc(MTGraph *G

, int v1, int v2)

{

}

BOOLEAN IsEdge(MTGraph *G, int v1, int v2)

{

}

void CreateMGraph (MTGraph *G)

{

for (k=0; ke; k++) {

for (i=0; in; i++)

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

G->edge[i][j]=0;

cout<<

输入顶点的字符

:

for (i=0; in; i++)

int i, j, k, w;

cout<<

输入顶点数和边数

:

cin>>G->n>>G-> e;

if(v1>=0 && v1n && v2>=0 && v2n && v1!=v2)

if(G->edge[v1][v2]!=0)

else

return FALSE;

return TRUE;

if(IsEdge(G

, v1, v2))

{

}

G->edge[v1][v2]=0;

G->edge[v2][v1]=0;

G->e--;

return FALSE;

cin>>G->vexlist[i];

cout<<

输入一条边的两个顶点

:

cin>>i>>j>>w;

G-> edge[i][j]=w;

G-> edge[j][i]=w;

}

}

void CreateMGraph(MTGraph *G

, VertexData V[], EdgeData E[][NumVertices], int n)

{

}

void PrintMT(MTGraph *G)

{

}

cout<<'t';

for(int i=0; in; i++)

{

}

cout<

for(i=0; in; i++)

{

}

cout<vexlist[i]<<'t';

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

cout<edge[i][j]<<'t';

cout<vexlist[i]<<'t';

int i, j;

G->n=n;

for (i=0; i

G->vexlist[i]=V[i];

for (i=0; in; i++)

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

G->edge[i][j]=0;

for(i=0; i

for(j=i; j

{

}

if(E[i][j]!=0)

{

}

G-> edge[i][j]=E[i][j];

G-> edge[j][i]=E[i][j];

G->e++;

cout<

void main()

{

MTGraph G;

IniMGraph(&G);

VertexData v[6]={'v1', 'v2', 'v3', 'v4', 'v5','v6'};

EdgeData e[6][NumVertices]={

CreateMGraph(&G

, v, e, 6);

NewNode(&G

, 'v1');

NewNode(&G

, 'v2');

NewNode(&G

, 'v3');

NewNode(&G

, 'v4');

NewNode(&G

, 'v5');

NewNode(&G

, 'v6');

SetSucc(&G

, 0, 1, 1);

SetSucc(&G

, 0, 3, 1);

SetSucc(&G

, 1, 3, 1);

SetSucc(&G

, 1, 2, 1);

SetSucc(&G

, 2, 3, 1);

PrintMT(&G);

cout<

DelSucc(&G

, 1, 3);

PrintMT(&G);

cout<

DelNode(&G

, 2);

}

邻接表表示：

#include

using namespace std;

typedef char VertexData;

typedef int EdgeData;

{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}};

typedef struct node {

int adjvex;

EdgeData cost;

struct node *next;

} EdgeNode;

typedef struct {

VertexData vertex;

EdgeNode * firstedge;

} VertexNode;

typedef struct {

VertexNode vexlist[NumVertices+1];

int n, e;

} AdjGraph;

void IniADJGraph(AdjGraph *G)

{

}

BOOLEAN NewNode(AdjGraph *G

, VertexData v)

{

if(G->n

{

for(int i=1; i

{

}

if(G->vexlist[i].vertex==freever)

{

}

G->vexlist[i].vertex=v;

G->vexlist[i].firstedge=NULL;

G->n++;

return TRUE;

G->e=0;

G->n=0;

for(int i=1; i

{

}

G->vexlist[i].vertex=freever;

G->vexlist[i].firstedge=NULL;

}

}

return FALSE;

void DelNode(AdjGraph *G

, int m)

{

}

if(G->vexlist[m].vertex!=freever)

{

}

G->vexlist[m].vertex=freever;

EdgeNode *p=G->vexlist[m].firstedge;

while(p!=NULL)

{

}

G->vexlist[m].firstedge=NULL;

DelSucc(G

, m, p->adjvex);

p=G->vexlist[m].firstedge;

BOOLEAN SetSucc(AdjGraph *G

, int v1, int v2, EdgeData w)

{

if(G->vexlist[v1].vertex!=freever && G->vexlist[v2].vertex!=freever )

{

EdgeNode *p=G->vexlist[v1].firstedge;

if(IsEdge(G

, v1, v2))

DelSucc(G

, v1, v2);

p = new EdgeNode;

p->adjvex = v2;

p->cost = w;

p->next = G->vexlist[v1].firstedge;

G->vexlist[v1].firstedge = p;

p = new EdgeNode;

p->adjvex = v1;

p->cost = w;

p->next = G->vexlist[v2].firstedge;

G->vexlist[v2].firstedge = p;

}

return FALSE;

G->e++;

return TRUE;

}

void DelSucc(AdjGraph *G

, int v1, int v2)

{

if(IsEdge(G

, v1, v2))

{

EdgeNode *p=G->vexlist[v1].firstedge, *p1;

if(p->adjvex==v2)

{

}

else

{

}

p=G->vexlist[v2].firstedge;

if(p->adjvex==v1)

{

}

else

{

p1=p;

G->vexlist[v2].firstedge=p->next;

delete p1;

do

{

p1=p->next;

if(p1==NULL)

break;

p1=p;

G->vexlist[v1].firstedge=p->next;

G->e--;

delete p1;

if(p1->adjvex==v2)

{

}

p=p->next;

p->next=p1->next;

delete p1;

G->e--;

}while(p!=NULL);

do

{

p1=p->next;

if(p1==NULL)

break;

if(p1->adjvex==v1)

{

p->next=p1->next;

delete p1;

}

p=p->next;

}while(p!=NULL);

}

}

}

BOOLEAN IsEdge(AdjGraph *G, int v1, int v2)

{

EdgeNode *p=G->vexlist[v1].firstedge;

if(p==NULL)

return FALSE;

while(1)

{

if(p->adjvex==v2)

{

return TRUE;

}

p=p->next;

if(p==NULL)

return FALSE;

}

return FALSE;

}

void CreateADJGraph (AdjGraph *G)

{

cout<<

输入顶点数和边数

:

cin >> G->n >> G->e;

for ( int i = 1; i <= G->n; i++)

{

cout<<

输入第

个顶点信息

:

cin >> G->vexlist[i].vertex;

G->vexlist[i].firstedge = NULL;

}

for ( i = 1; i <= G->e; i++)

{

int tail, head;

EdgeData weight;

cout<<

输入第

条边的起始点、终止点以及权重

:

cin >> tail >> head >> weight;

EdgeNode * p = new EdgeNode;

p->adjvex = head;

p->cost = weight;

p->next = G->vexlist[tail].firstedge;

G->vexlist[tail].firstedge = p;

p = new EdgeNode;

p->adjvex = tail;

p->cost = weight;

p->next = G->vexlist[head].firstedge;

G->vexlist[head].firstedge = p;

}

}

void CreateADJGraph(AdjGraph *G

, VertexData V[], EdgeData E[][NumVertices], int n)

{

G->n=n;

for ( int i = 1; i <= n; i++)

{

G->vexlist[i].vertex=V[i-1];

G->vexlist[i].firstedge = NULL;

}

for ( i = 1; i <=n; i++)

for(int j=i+1; j<=n; j++)

{

if(E[i-1][j-1]!=0)

{

EdgeNode * p = new EdgeNode;

p->adjvex = j;

p->cost = E[i-1][j-1];

}

}

}

p->next = G->vexlist[i].firstedge;

G->vexlist[i].firstedge = p;

p = new EdgeNode;

p->adjvex = i;

p->cost = E[i-1][j-1];

p->next = G->vexlist[j].firstedge;

G->vexlist[j].firstedge = p;

G->e++;

void PrintADJ(AdjGraph *G)

{

EdgeNode * p;

int i, j;

EdgeData result[NumVertices][NumVertices]={0};

VertexData ver[NumVertices];

cout<<'t';

for(i=1; i

{

}

cout<

cout<vexlist[i].vertex<<'t';

ver[i]=G->vexlist[i].vertex;

for(i=1; i

{

}

for(i=1; i

{

cout<

for(j=1; j

{

p=G->vexlist[i].firstedge;

while(p!=NULL)

{

}

result[i][p->adjvex]=p->cost;

p=p->next;