无向图邻接表的深度优先遍历(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;
}