图的基本操作与实现的课程设计报告

x

的顶点，则删除该结点及与之相关连的边，并作

DFS

遍

历

(

执行操作

3)

；

< br>否则输出信息“无

x”

(6)

判断图

G

是否是连通图，输出信息

“YES” / “NO”；

(7)

如果选用的存储结构是邻接矩阵

,

则用邻接矩阵的信息 生成图

G

的邻接表，即复制图

G, < /p>

然再执行操作

(2);

反之亦然。

第

1. 2

节主要难点

(1)

自选存储结构创建一个图：通 过用户从键盘敲入的两个数值分别确定图的顶点数和边

数，选 择邻接矩阵存储结构将图的结点信息存储在一个顺序表中，图的边信息存储在一个二维

数组中。

(2)

求每个顶点的度

:

1.

邻接 矩阵存储结构下求每个顶点的度：利用图的邻接矩阵，每个顶点所在行和所在列的

边的权值如果存在则该顶点的度

+1,

依次 算出每个顶点的度，并且记录在一个数组中输出。

2.

邻接表存储结构下求每个顶点的 度：定义一个邻接边指针循环指向顶点的邻接边单链表

头结点 ，当结点不空时，该顶点的出度

+1,

邻接边弧头结点的入度< /p>

+1,

依次求出每个顶点的出度

和入度之和就为该顶点的度。

(3)

图的深度优先遍历：采取邻接 矩阵结构，指定任意顶点

x

为初始顶点

1.

访问结点

V

并标记结点

V

己访问；

2.

查找结点

v

的第一个邻接结点

w

；

3.

若结点

v

的邻接结点

w

存在，则继续执行，否则算法结束；

4.

若结点

w

尚未被访问，则递归访问结点

w

；< /p>

5.

查找结 点

v

的

w

邻接 结点的下一个邻接结点

w,

转到步骤

3 o

(4)

图的广度优先遍历：采取 邻接矩阵结构，指定任意顶点

x

为初始顶点，利用顺序循环队< /p>

列以保持访问过的结点的顺序

1.

首先访问初始结点

v

并标记结点

v

为已访问；

2.

结点

v

入队列；

3.

当队列非空时则继续执行，否则算法结束；

4.

出队列取得队头结点

；

5.

查找

u

的第一个邻接结点

w

；

6.

若

< br>u

的邻接结点

w

不存在则转到步 骤

3,

否则循环执行下列步骤：

6.1

若结点

w

尚 未被访问，则访问结点

w

并标记结点

w

为已访问；

6.

2

结点

w

入队列；

6. 3

查找结点

u

< br>的

w

邻接结点的下一个邻接结点

w,

转到步骤

6 o

(5)

判断有向图的强连通性：采取 邻接表结构，在图中寻找一个包含所有顶点且首尾相连的

环，若这样的环存在，则该图为强连通图，否则不为强连通图。

(6)

用邻接矩阵的信息生成邻接表 ：定义一个邻接表的边信息结构体，将邻接矩阵的边信息

转换成邻接表的边信息存储到邻接边的单链表中。

第二章系统流程图

第三章数据结构和算法

(1)

有向图顶点的数据类型

DataType

定义如下：

typedef int DataType

；

(2)

邻接矩阵存储结构下图的结构体定义如下：

typedef struct

{

SeqList Vertices

；

int edge[MaxVertices][MaxVertices]

int numOfEdges

；

}AdjMGraph

；

(3)

邻接矩阵存储结构下图的边信息结构体定义如下：

typedef struct

{

int row

；

int col

；

int weight

；

}RowColWeight

；

(4)

邻接表存储结构下图的结构体定义如下：

typedef struct Node

{

int dest

；

struct Node *next

；

}Edge

；

typedef struct

{

DataType data

；

int sorce

；

Edge *adj

；

}AdjLHeight

；

typedef struct

{

AdjLHeight a[MaxVertices]

；

int numOfVerts

；

int numOfEdges

；

}AdjLGraph

；

(5)

邻接表存储结构下图的边信息结构体定义如下：

typedef struct

{

int row

；

int col

；

}RowCol

；

(6)

顺序循环队列的结构体定义如下：

typedef struct

{

DataType queue[MaxQueueSize]

；

int rear

；

int front

；

int count

；

}SeqCQueue

；

(7)

顺序表的结构体定义如下：

typedef struct

{

DataType list [MaxSize]

；

int size

；

JSeqList

；

第四章核心代码分析

源程序存放在八 个文件夹中，文件

SeqList.h

是顺序表的结构体定义和 操作函数，文件

SeqCQueue.

h

是顺序循环队列的结构体定义和操作函数，文件

AdjM Graph.

h

是邻接矩阵存储结构

下图的结构体定义和操作函数，文件

AdjMGraphCre ate.

h

是邻接矩阵存储结构下图的创建函数

,

文件

AdjLGraph. h

是邻接表存储结构下图的结构体定义和操作函数，文件

AdjLGraphCr eate. h

是

邻接表存储结构下图的创建函数，文件

AdjMGraphTraverse. h

是邻接矩阵存储结构下图的深

度优

先遍历和广度优先遍历操作函数，文件图的基本操作与实现

.< /p>

c

是主函数。

(1)

/*

文件

SeqList. h */

typedef struct

DataType list [MaxSize]: int size;

JSeqList;

void Listinitiate(SeqList *L)

L->size=0;

}

int ListLength(SeqList L)

{

return L. size;

)

int Listinsert (SeqList *L, int i, DataType x)

{

int j;

if(L->size>=MaxSize)

{

printfC

数组已满无法插入！

n

return 0;

)

else if(i<0||i>L->size)

(

printf

(”参数不合法

！

n

return 0;

)

else

(

for (j=L->size;j>i;i

—

)L->list[j]=L->list[j-1];

L->list[i]=x;

L->size++;

retxirn 1;

)

}

int ListDelete(SeqList *L)int i, DataType *x)

{

int j

；

if(L->size<=0)

(

printf r

顺序表己空无数据元素可删！

n

return 0;

)

else if(i<0||i>L->size-l)

printf

(

参数

i

不合法

!

rT);

return 0;

}

else

{

*x=L->list[i];

for(j=i+l;j<=L->size~l;j++)L->list[j-l]=L->list[j] ;

L->size

—

;

return 1;

)

}

int ListGet(SeqList L, int i, DataType *x)

{

if (i<0||i>L. size-1)

{

printfC

参数

i

不合法！

n

return 0;

)

else

(

*x=L. list[i];

return 1;

}

}

(2)

/

*

文件

SeqCQueue. h */

typedef struct

{

DataType queue[MaxQueueSize];

int rear;

int front;

int count;

}SeqCQueue;

void Queueinitiate(SeqCQueue *Q)

{

Q->rear=0;

Q-

〉

front =0;

Q->count =0;

}

int QueueNotEmpty(SeqCQueue Q)

{

if(Q. count 1=0) return 1;

else return 0;

}

int QueueAppend(SeqCQueue *Q, DataType x)

{

if(Q->count>0&&Q->rear==Q->front)

{

printfC

队列已满无法插入 !”)；

return 0;

)

else

(

Q->queue [Q->rear]=x;

Q->rear =(Q->rear +1)%MaxQueueSize;

Q->count ++;

return 1;

}

)

int QueueDelete(SeqCQueue *Q, DataType *d)

{

if(Q->count ==0)

(

printfC

队列己空无数据出 队列

!

n

；

)

else

(

*d=Q->queue[Q->front];

Q->front=(Q->front+l)%MaxQueueSize;

Q->count

—

;

return 1;

}

)

return 0;

int QueueGet(SeqCQueue Q, DataType*d)

{

if (Q. count ==0)

{

printfC

队列已 空无数据出队列

!

n

return 0;

}

else

*d=Q. queue [Q. front ]; return 1;

}

(3)

/*

文件

AdjMGraph. h*/

#include*SeqList. h” typedef struct {

SeqList Vertices;

〃存放结点的顺序表

int edge [MaxVertices] [MaxVertices];

〃存放边的邻接矩阵

int numOfEdges;

〃边的条数

} AdjMGraph;

〃边的结构体定义

void Initiate (AdjMGraph *G, int n)

//

初始化

{ int i, j;

for(i=0;i

for(j=0;j

(

if(i=j)

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

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

}

G->numOfEdges=O;

〃边的条数置为

0

Listinitiate (&G->Vertices);

//

顺序表初始化

}

void InsertVertex(AdjMGraph *G, DataType vertex)

〃在图

G

中插入结点

vertex {

Listinsert (&G->Vertices, G->Vertices. size, vertex);

〃顺序表尾插入

}

void InsertEdge(AdjMGraph *G, int vl, int v2, int weight)

//