无向图邻接表的深度优先遍历(DFS)

 邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表（n个顶点建立n个单链表）

 

头文件:Graph.h

#ifndef GRAPH_H
#define GRAPH_H
#define MAXSIZE 50
typedef char VertexType;  //顶点数据类型
typedef int EdgeType; //边权值类型
typedef struct edgenode{
int adjvex;//当前节点的下标值
EdgeType weight;//边的权值
struct edgenode* next;  //边表的域,指向下一个边表节点
}EdgeNode;
typedef struct vertexnode{
VertexType data;        //顶点的数据
EdgeNode *pAdjNext;     //顶点的域,指向边表节点
}VertexNode,Vertex[MAXSIZE];
typedef struct graph{
Vertex Vertexes;   //顶点节点
int NumVertexes,NumEdges;
}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[MAXSIZE];
void CreateGraph(Graph *G)
{
EdgeNode *e = NULL;
printf("请输入图的顶点数和边数:\n");
scanf("%d%d",&G->NumVertexes,&G->NumEdges);
printf("请输入图的顶点信息:\n");
for(int i = 0;i < G->NumVertexes;++i)
{
fflush(stdin);
scanf("%c",&G->Vertexes[i].data);
G->Vertexes[i].pAdjNext = NULL;
}
for(int k = 0;k < G->NumEdges;++k)
{
int i,j,w;
e = (EdgeNode*)malloc(sizeof(EdgeNode));
if(!e)
exit(OVERFLOW);
printf("请输入边的链接信息(vi,vj)及权值:\n");
fflush(stdin);
scanf("%d%d%d",&i,&j,&w);
e->adjvex = j;
e->weight = w;
e->next = G->Vertexes[i].pAdjNext; //建立链表
G->Vertexes[i].pAdjNext = e;
//由于是无向图,存在反向链接
e = (EdgeNode*)malloc(sizeof(EdgeNode));
if(!e)
exit(OVERFLOW);
e->adjvex = i;
e->weight = w;
e->next = G->Vertexes[j].pAdjNext;
G->Vertexes[j].pAdjNext = e;
}
}
void DFSTraverse(Graph *G)
{
for(int i = 0;i < G->NumVertexes;++i) //初始化图的各个顶点为false,未访问过
visited[i] = false;
for(int i = 0;i < G->NumVertexes;++i) 
if(!visited[i])   //选取一个未访问过的顶点进行深度优先遍历,如果是连通图DFS只执行一次
DFS(G,i);
}
void DFS(Graph *G,int i)
{
visited[i] = true;
printf("%c ",G->Vertexes[i].data);
EdgeNode *p = G->Vertexes[i].pAdjNext; 
while(p)
{
if(!visited[p->adjvex]) //如果边表结点没有被访问过,则递归调用DFS
DFS(G,p->adjvex);
p = p->next;
}
}

测试文件main.cpp

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