试以邻接矩阵为存储结构,写出连通图的深度优先搜索算法。
发布网友
发布时间：2022-04-25 21:00
共1个回答
热心网友
时间：2022-06-17 08:55
/* 包含图类型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是数据结束标志
参数kind=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
*/
void CreateGraph(Graph &G, VType *Vex, int VVW[], int kind)
{
int i, j, p, n, w;
n = strlen(Vex);
G.vn = n; //顶点数
G.kind = kind; //图的种类
//置顶点序列:
for (i = 0; i < n; i++)
G.v[i] = Vex[i];
//初始化邻接矩阵:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
G.w[i][j] = INVALID;
//构造邻接矩阵:
p = 0; //VVW数组元素“指针”
n = 0; //边计数器
while (VVW[p] != -1)
{//只要p未到结束位置便继续:
i = VVW[p]; //边的起点序号
j = VVW[p + 1]; //边的终点序号
w = VVW[p + 2]; //边的权
G.w[i][j] = w; //置邻接矩阵的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是无向图(网),
G.w[j][i] = G.w[i][j]; //则置(i,j)的对称位置(j,i)
n++; //边计数器加1
p += 3; //p指向下一组(Vi,Vj,Wij)
}//end while
G.en = n; //边数
}//CreateGraph
/* 返回G中顶点i的一个未曾访问过的邻接点(序号) */
int NextAdjVex(Graph &G, int i)
{
int j, a;
a = EMPTY; //邻接点序号初始为"空"
//在邻接矩阵的第v行找有效元素：
for (j = 0; j < G.vn; j++)
{
if (G.w[i][j] == INVALID) //若当前元素是无效元素,
continue; //则继续找。
if (!visited[j])
{//若当前有效元素未曾访问过,则作为邻接点a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex
/* 访问顶点i */
void visit(Graph &G, int i)
{
printf("%c", G.v[i]);
}//visit
/* 从第i个顶点出发深度优先遍历连通图G */
/* 调用DFS前可能需初始化数组visited[] */
void DFS(Graph &G, int i)
{int a;
visit(G, i); //访问i顶点
visited[i] = 1; //标注i顶点已访问
a = NextAdjVex(G, i); //找出一个i的邻接点a
while (a != EMPTY)
{//只要a存在便继续:
if (visited[a] == 0) //若a未曾访问,
DFS(G, a); //则从a出发继续进行深度优先遍历。
a = NextAdjVex(G, i); //找出i的下一个邻接点a
}//end while
}//DFS
/* 从第i个顶点出发深度优先遍历图G */
void DFSTrav(Graph &G, int i)
{int k;
//初始化各顶点的访问标志为0(未曾访问):
for (k = 0; k < G.vn; k++)
visited[k] = 0;
DFS(G, i); //从i出发遍历
//若G非连通图，执行一次DFS无法遍历所有顶点，还需用如下for对尚未访问的顶点DFS。
//若G是连通图，执行一次DFS就已遍历所有顶点，此时如下for什么也不做，因所有visited=1。
for (k = 0; k < G.vn; k++)
if (!visited[k]) DFS(G, k); //对尚未访问的顶点DFS
}//DFSTrav
//显示图的邻接矩阵
void ShowM(Graph &G)
{
int row, col, n;
n = G.vn; //顶点数
//以表格形式输出数组：
//输出表头：
printf(" ");
for(col = 0; col < n; col++)
printf("%3d",col);
printf("\n");
printf("---+");
for(col = 0; col < n; col++)
printf("---");
printf("\n");
//输出表体(矩阵元素)：
for(row = 0; row < n; row++)
{
printf("%3d|", row);
for(col = 0; col < n; col++)
{
if (G.w[row][col] == INVALID)
printf("%3c", '*');
else
printf("%3d", G.w[row][col]);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM
