DFS

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef int VertexType;
#define MaxVertexNum 100

// 需要设计两种结点结构类型：一是定点表的顶点，二是单链表的结点
typedef struct ArcNode{  // 边表结点
	int adjvex;  // 该弧所指向的顶点的位置
	struct ArcNode *next;  // 指向下一条弧的指针
}ArcNode;

typedef struct VNode{  // 顶点表结点
	VertexType data;  // 顶点信息
	ArcNode *firstedge;  // 单链表头指针
}VNode, AdjList[MaxVertexNum];

typedef struct{
	AdjList vertices;  // 邻接表
	int vexnum, arcnum;  // 图的顶点数和弧数
}ALGraph;

/*
创建邻接表函数，参数为一个邻接表变量
该函数将提示用户输入创建一个邻接表所需要的关键信息，
包括图中结点个数，边的条数，每个结点存储的数据，每条边两边结点的索引值
*/
void CreateAL(ALGraph *g){
	int end;
	int start;
	cout << "请输入结点数和边数: ";
	cin >> g->vexnum >> g->arcnum;
	cout << "请输入每个顶点保存的数据: " << endl;
	for (int i = 0; i < g->vexnum; i++){  // vexnum 图的顶点数
		cout << "vertex" << i << ":";
		cin >> g->vertices[i].data;  // 给每一个顶点赋值
		g->vertices[i].firstedge = NULL;  // 初始化时一定要让每个顶点的指针为空，否则为野指针
	}
	cout << "请输入每条边的两个顶点在数组中的的下标(中间用空格分隔)" << endl;

	for (int j = 0; j < g->arcnum; j++){   // arcnum 图的弧数
		cout << "请输入第" << j << "条边" << endl;
		cin >> start >> end;  // 接收从start ----> end
		ArcNode *node = (ArcNode *)malloc(sizeof(ArcNode));  // 边表结点
		node->adjvex = end;  // 该弧所指向的顶点的位置
		node->next = g->vertices[start].firstedge;  // 头插法插入边结点
		g->vertices[start].firstedge = node;  // 顶点的firstedge为node
	}
}

/*
打印链表函数，接收一个邻接表指针变量，和边表结点指针变量
该函数专门用于打印邻接表中链表的结点数据
*/
void PrintLink(ALGraph *g, ArcNode *next){
	while (next != NULL){
		cout << g->vertices[next->adjvex].data << " ";
		next = next->next;
	}
	cout << endl;
}

/*
打印创建好的邻接表函数，接收一个邻接表指针变量
该函数将打印每个顶点以及与其相连的顶点中保存的数据
*/
void disp(ALGraph *g){
	cout << "邻接表为: " << endl;
	for (int i = 0; i < g->vertices[i].data; i++){
		cout << g->vertices[i].data << " ";
		PrintLink(g, g->vertices[i].firstedge);
	}
}

// -------------------------------------------------------
//上面部分是邻接表，下面是BFS代码
bool visited[MaxVertexNum];
void Init_visited(bool visited[], int len){
	for (int i = 0; i < len; ++i){
		visited[i] = false;
	}
}

void DFS(ALGraph *g, int v){
	ArcNode *p = NULL;  // 工作指针
	printf("%d ", g->vertices[v].data);
	visited[v] = true;
	p = g->vertices[v].firstedge;
	while (p != NULL){
		if (!visited[p->adjvex]){
			DFS(g, p->adjvex);
		}
		p = p->next;
	}
}

int main(void){
	ALGraph* g = (ALGraph*)malloc(sizeof(ALGraph));//创建邻接表
	CreateAL(g);//屏幕打印邻接表
	disp(g);
	cout << "深度度优先遍历打印树： ";	
	Init_visited(visited, MaxVertexNum);
	DFS(g, 0);
	system("pause");
	return 0;
}

这里我输入的是无向图，也可以输入有向图那就是5 6