本文共 1461 字，大约阅读时间需要 4 分钟。

【描述】：  该graph采用邻接表存储，首先创建图，然后对其进行深度优先遍历。

【输入】：

【输出】：

0 1 3 7 4 5 2 6 

/* * 无向图的邻接表创建81 2 -10 3 4 -10 5 6 -11 7 -11 7 -12 7 -12 7 -13 4 5 6 -1*/#include
   
    #include
    
     using namespace std;#define MAX_VERTICES 50	/* 顶点最大数 */#define ElementType int	/* 元素的数据类型 */bool visited[MAX_VERTICES];	/* 记录顶点是否被访问 */typedef struct node {	/* 表节点结构体 */	ElementType vertex;	struct node *next;}NodeType,*NodePointer;NodePointer graph[MAX_VERTICES];	/* 头节点数组 */int vertices;	/* 顶点数量 */void CreateGraph(){	ElementType ch;	NodePointer pnew,qnode;	pnew = qnode = NULL;	for(int i = 0; i < vertices; i++){		cin>>ch;		if(ch == -1) continue; /*当ch 为-1是结束该vertex的创建*/		//链表的头节点		pnew = new NodeType;		pnew->vertex = ch;		pnew->next = NULL;		//将头节点存入 头节点数组		graph[i] = pnew;		//尾插法创建链表		cin>>ch;		while(ch != -1){			//申请内存、处理数据域、处理指针域			qnode = new NodeType;			qnode->vertex = ch;			qnode->next =NULL;			//插入			pnew->next = qnode;			//更新尾指针			pnew = qnode;			cin>>ch;		}	}}void dfs(int v){	NodePointer np;	//访问该vertex	visited[v] = true;	cout<
     
      <<" ";	/*	 * 图深度优先遍历	 * 1、访问该节点并且记录	 * 2、当该节点的next节点没被visited，dfs（next节点）	 * 3、当该节点的next节点都被visited，结束for，退到上一个visited的节点执行2步骤	 * 4、都被访问了，函数自然结束	 */	for(np = graph[v]; np!=NULL; np = np->next){		if(!visited[np->vertex])			dfs(np->vertex);	}}int main(){	memset(visited,false,sizeof(visited));	cout<<"输入顶点数"<
      
       >vertices;	CreateGraph();	cout<<"深度优先遍历"<
      
     
    
   

转载地址：https://lipenglin.blog.csdn.net/article/details/49947351 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！