实验五 图的基本操作

图 的 基 本 操作

学生学号： ************** 学生姓名: ******** 专业班级： ********

一、 算法思路

1、创建一个无向图，在创建图的时候先定义图的邻接表存储表示

2、指定的结点为起点，并用函数LocateVex(ALGraph G,int v)用于查找该

点所在位置

3、逐边输入信息，将两个顶点都要插入图中

4、深度优先遍历，使标志数组visited[]的值为0，一旦被访问，则为1

5、广度优先遍历时，先定义队列的一些相关函数，用于广度优先遍历

流程图：

开始 创建无向图 输入顶点数和边数、顶点信息 k

G.vertices[v].firstarc->adjvex（返回值） w>=0 是 p&&p->adjvex!=w 是 p=p->nextarc，p->nextarc不为空，返回return p->nextarc->adjvex 否 否 是 !visited[w] 否 广度优先遍历 所有的顶点初始化，标志为未访问，队列初始化 !visited[v] 否 是 visited[v]=1;并且v元素进队

所有的顶点初始化，标志为未访问，队列初始化 !visited[v] 否 是 visited[v]=1;并且v元素进队 否 !QueueEmpty(Q) 是 元素出队请找与该点相关的邻接点 !visited[w] visited[w]=1，元素w进队 结束

二、主要的一些函数

1、 建立无向图的邻接表存储表示：

typedef struct ArcNode {

int adjvex; struct ArcNode *nextarc;

int *info; }ArcNode;

2、typedef struct VNode

{

char data; //顶点信息

ArcNode *firstarc;//指向第一条依附该顶点的弧的指针

}VNode,AdjList[max];