无向图邻表矩阵深度优先遍历(DFS)

头文件Graph.h

#ifndef GRAPH_H
#define GRAPH_H
#define MAXVEX 10
typedef char VertexType; //顶点的数据元素
typedef int EdgeType; //边表节点的权值
typedef struct Node{
VertexType Vertex[MAXVEX];  //顶点表
EdgeType Edge[MAXVEX][MAXVEX]; //邻接矩阵,看作边表
int NumVertex,NumEdge; //图的顶点数和边数
}Graph;
void CreateGraph(Graph *G);
void DFS(Graph *G,int i);
void DFSTraverse(Graph *G);
#endif //GRAPH_H

实现文件Graph.cpp

#include "Graph.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
bool visited[MAXVEX];
void CreateGraph(Graph *G)
{
printf("请输入顶点数和边数:\n");
scanf("%d%d",&G->NumVertex,&G->NumEdge);
printf("请输入顶点信息:\n");
for(int i = 0;i < G->NumVertex;++i)
{
fflush(stdin);
scanf("%c",&G->Vertex[i]);
}
for(int i = 0;i < G->NumVertex;++i) //初始化图
for(int j = 0;j < G->NumVertex;++j)
G->Edge[i][j] = 0;
int i,j;
for(int k = 0;k < G->NumEdge;++k)
{
printf("请输入边的链接信息(vi,vj):\n");
fflush(stdin);
scanf("%d%d",&i,&j);
G->Edge[i][j] = 1;
G->Edge[j][i] = G->Edge[i][j]; //无向图存在反向链接
}
}
void DFSTraverse(Graph *G)
{
for(int i = 0;i < MAXVEX;++i) //初始化每个节点为都未访问过
visited[i] = false;
for(int i = 0;i < G->NumVertex;++i)
if(!visited[i])  //选取一个未访问过的顶点进行深度优先搜索,如果是连通图则只执行一次
DFS(G,i);
}
void DFS(Graph *G,int i)
{
visited[i] = true;
printf("%c ",G->Vertex[i]);
for(int j = 0;j < G->NumVertex;++j)
if(G->Edge[i][j] == 1 && !visited[j])
DFS(G,j);
}

测试文件main.cpp

#include "Graph.h"
int main()
{
Graph G;
CreateGraph(&G);
DFSTraverse(&G);
return 0;
}