试以邻接矩阵为存储结构,写出连通图的深度优先搜索算法。

来源:百度知道 编辑:UC知道 时间:2024/05/14 15:58:40
高分求解!!!!!!!

/* MGraph.cc: 图的邻接矩阵存储表示和实现 */
/* 包含图类型Graph定义;创建图;深度优先遍历;广度优先遍历 */
/* 用到引用型参数,在TC下无法通过编译,VC等C++编译器可通过 */

#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX

#define VType char //顶点值类型
#define EType int //边权值类型
#define MAXVNUM 50 //最大顶点个数
#define DIGRAPH 0 //有向图(网)
#define UNDIGRAPH 1 //无向图(网)
#define INVALID INT_MAX //无效权值(最大整数表示无穷大)
#define EMPTY -1 //"空"顶点序号

//定义邻接矩阵表示的图类型Graph:
typedef struct
{
VType v[MAXVNUM]; //顶点序列(顶点编号从0开始)
EType w[MAXVNUM][MAXVNUM]; //邻接矩阵
int vn, en; //顶点数,边数
int kind; //图的种类:=DIGRAPH表示有向图(网),=UNDIGRAPH表示无向图(网)
}Graph;

int visited[MAXVNUM]; //访问标志数组(=1已访问,=0未访问)。遍历时用到的全局量。

/* 创建图G
参数Vex是存放顶点序列的数组
参数VVW是整数数组,以{Vi,Vj,Wij,...,-1}的形式依次存放各边的起止点序号(Vi,Vj)和权(Wij),-1是数据结束标志<