数据结构图结构

数据结构---图

1.1 图的定义

在图的定义头文件中，可以看到一个结构体，这个结构体中含有如下的几项

1、vertex【】数组，这个数组是用记录途中的所有的顶点的。edge这个二维数组是用来描述图，整个结构体就是邻接矩阵，而在结构体中还有一个n这个n是实际上图中存在的顶点数，也就是数组中的实际元素。

1.2 图的创建

在图的创建函数中，要创建结构体，并为其赋值（初始化）。

首先看以下main

函数中是怎么调用图的构建函数的：图的创建函数图的创建对图的结构体的成员进行了初始化。

1.2 图的第一邻接点查找函数

图的第一邻接查找函数很简单就是遍历一下邻接矩阵的第u行，查找一下1出现的第一的位

置。

1.3 图的下一个邻接点查找函数

这个函数，就是第u个点的w之后的一个顶点的下标。

1.4 图的深度优先遍历（DFS）

深度优先遍历，是利用递归函数，其实深度优先遍历就是二叉树的前序遍历，思想：访问第一个顶点，然后在判断顶点的第一邻接点是否被遍历了，如果没有被遍历，就调用自己函数

来处理，如何被遍历了，就调用下一个邻接点查找函数。循环判断的条件是，看查询出来的邻接点是否已经循环完了，就是到达最后一个了。

如何存在邻接点，就判断是否被遍历过，如何没有，就递归调用自己依次处理当前顶点的其

他邻接点，知道将全部的邻接点都访问过了。

1.5 图的广度优先遍历

图的广度优先遍历，利用二叉树的 层遍历的思想，是把图也按照数的一定结构进行遍历

，所以广度优先遍历也同样的用到了队列（FIFO）结构，来存储被访问过的数据。

广度优先遍历，是判断队列是否为空来控制大循环，而在内部还要有一个小的循环来控

制，访问每一层的顶点（即当前的v顶点）。

而内部的循环的控制条件是，判断出队列的顶点还有没有邻接点没有被遍历。如何有，

则进入循环，并判断这个邻接点是否被访问过（通过标志位）。如果没有被访问，就访问，并置标志位为1，并入队列（以便本次循环之后在新的一轮中遍历它的邻接点）。如果被访

#include "stdlib.h"

#include "stdio.h"

#include "malloc.h"

#define INFINITY 32767

#define MAX_VERTEX_NUM 20

typedef enum{FALSE,TRUE}visited_hc;

typedef enum{DG,DN,UDG,UDN}graphkind_hc;

typedef struct arccell_hc

{int adj;

int *info;

}arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{char vexs[MAX_VERTEX_NUM];

adjmatrix_hc arcs;

int vexnum,arcnum;

graphkind_hc kind;

}mgraph_hc;

typedef struct arcnode_hc

{int adjvex;

struct arcnode_hc *nextarc;

int *info;

}arcnode_hc;

typedef struct vnode_hc

{char data;

arcnode_hc *firstarc;

}vnode_hc,adjlist_hc[MAX_VERTEX_NUM];

typedef struct

{adjlist_hc vertices;

int vexnum,arcnum;

graphkind_hc kind;

}algraph_hc;

int locatevex_hc(mgraph_hc*g,char v)

{int i,k=0;

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

if(g->vexs[i]==v){k=i;i=g->vexnum;}

return(k);}

mgraph_hc*createudg_hc()

1.在一个无向图中,所有顶点的度数之和等于所有边数的 () 倍.

2.在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的 () 倍.

3.一个有N个顶点的无向图最多有 () 条边.

4.具有6个顶点的无向图至少应有 () 条边才能确保是一个连通图.

5.已知一有向图的邻接表存储结构如图:

(1)从顶点v1出发,深度优先遍历所得到的顶点序列是 () ;广度优先遍历得到的顶点序列是()

.

6.一个图中包含k个连通分量,若按深度优先搜索方法访问所有顶点,则必须调用 ()

次深度优先遍历算法.

7.已知一个图的邻接矩阵表示,计算第i个接点的入度的方法是 () ;出度的方法 .

8.对n个顶点的连通图来说,它的生成树一定有 ()

条边.

9.设有向图如图所示:写出所有的拓扑序列 () ;添加边 ( ) 后,则仅可能有唯一的拓扑序列.

幻灯片5

10如图所示无向图,(1)给出邻接矩阵和邻接表;(2)在给定的邻接表上,给出从顶点1出发的深度优先搜索序列和广度优先搜索序列.

幻灯片6

11.使用普里姆算法构造出如图所示的一棵最小生成树.

幻灯片7

12.使用克鲁斯卡算法构造出如图所示的图的一棵最小生成树.

幻灯片8

13.给出一个以下带权图的邻接矩阵表示:

(1)写出从顶点1出发的深度优先搜索序列,并判断该图是否为连通图;

(2)给出图的带权邻接表;

(3)给出按普里姆算法构造最小生成树(森林)的图.

幻灯片9

实验7 无向图

一、问题描述

创建一个无向图，实现图的深度优先遍历和广度优先遍历等功能。

二、需求分析

1、 简述程序的基本功能

本程序可以直接进行对图中元素的输入、输出、插入顶点、删除顶点、插入边、删除边、寻找邻接点以及深度优先遍历和广度优先遍历等功能。

2、 输入的形式和输入值的范围

提供了一个功能选择界面，可以输入0~9进行功能的选择。

3、 输出的形式

用户选择1选项时，程序会输出图的顶点数目和边的数目以及各条边顶点及权值；

用户选择2选项时，程序会提示输入创建图的顶点数和边数，然后逐个输入顶点，以及各条边；

用户选择3选项时，程序会提示输入顶点，然后输出该顶点的第一个邻接顶点；

用户选择4选项时，程序会提示输入顶点以及当前的邻接顶点，然后输出该顶点的下一个邻接顶点；

用户选择5选项时，程序会提示输入所要插入边的顶点以及权重；

用户选择6选项时，程序会提示输入所要插入的顶点；

用户选择7选项时，程序会提示输入所要删除的边的两个顶点；

用户选择8选项时，程序会提示输入所要删除的顶点

用户选择9选项时，程序提示输入遍历的起始顶点，然后输出深度遍历的结果；

用户选择0选项时，程序提示输入遍历的起始顶点，然后输出广度遍历的结果；

用户选择q选项时，程序结束。

4、 测试数据要求

1） 、选择选项时，不论输入几个字符，只读取第一个字符；

2） 、选择选项时，输入的字符不能过多，若输入过多的字符就会出现异常；

3） 、输入顶点时，每个元素只能是一个字符，输入多个字符会出错；

4） 、在查找、插入、删除顶点或边时，会有容错提示；

5） 、在查找和删除顶点或边时，若没有此元素，会给出提示；

三、概要设计

1、 抽象数据类型

在该程序中，定义了一个类模板template class Graph，在该类中有*Vertices、**Edge、numEdges、numVertices和maxVertices五个私有成员分别表示该类的顶点集、边集、现有边数、现有顶点数和顶点最大数目；自己定义了构造函数Graph(int size)和析构函数~Graph()，还有对图进行输入、输出、查找邻接点、插入顶点或边、删除顶点或边以及两种遍历等操作的函数；并在主函数中对该类模板进行实例化。