基于java数据结构实验 基于邻接矩阵和邻接表的深度广度优先遍历图

一、实验目的1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构；2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用；3．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。

二、实验内容实验内容1**图的遍历[问题描述]许多涉及图上操作的算法都是以图的遍历为基础的。

写一个程序，演示在连通无向图上遍历全部顶点。

[基本要求]建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。

以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。

[实现提示]设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，…，N）。

通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。

[编程思路]首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(Graph G, int v, int w)；FirstAdjVex （）函数的书写，依次递归下去，广度遍历用队列的辅助。

[程序代码]头文件：#include<stdio.h>#include<stdlib.h>#define MAX_VERTEX_NUM 30#define MAX_QUEUE_NUMBER 30#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define TRUE 1#define FALSE 0typedef int Status;typedef int InfoType;typedef int Status;/* 定义弧的结构*/typedef struct ArcNode{int adjvex; /*该边所指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边的指针*/ InfoType info; /*该弧相关信息的指针*/}ArcNode;/*定义顶点的结构*/typedef struct VNode{char data[40]; /*顶点信息*/ArcNode *firstarc; /*指向第一条依附该顶点的弧的指针*/}VNode,AdjList[MAX_VERTEX_NUM];/*定义图的结构*/typedef struct {AdjList vertices;int vexnum,arcnum; /*图的当前顶点数和弧数*/int kind; /*图的类型标志*/}Graph;/*定义队列的结构*/typedef struct{int *elem;int front, rear;}Queue;/*功能选择*/void MenuSelect(int w);/*顶点定位*/int LocateVex(Graph G,char *name);/*创建无向图*/void CreateGraph(Graph &G);/*求第一个顶点*/int FirstAdjVex(Graph G, int v);/*求下一个顶点*/int NextAdjVex(Graph G, int v, int w);/*深度递归*/void DFS(Graph G, int v) ;/*深度遍历*/void DFSTravel(Graph G,int v);/*广度遍历*/void BFSTraverse(Graph G,char *name);/*初始化队列*/Status InitQueue(Queue &Q);/*判空*/Status EmptyQueue(Queue Q);/*进队*/Status EnQueue(Queue &Q, int e);/*出队*/Status DeQueue(Queue &Q, int &e);实现文件：#include <stdio.h>#include"malloc.h"#include "tuhead.h"#include "stdlib.h"#include "string.h"bool visited[MAX_VERTEX_NUM];/************************************************************ 顶点定位************************************************************/int LocateVex(Graph G,char *name){int i;for(i=1;i<=G.vexnum;i++) //从1号位置开始存储if(strcmp(name,G.vertices[i].data)==0) //相等则找到，返回位序return i;return -1;}/************************************************************ 创建无向图************************************************************/void CreateGraph(Graph &G){ArcNode *p;char name1[10],name2[10];int i,j,k;printf(" 请输入顶点数,按回车键结束：");scanf("%d",&G.vexnum);printf(" 请输入弧数,按回车键结束：");scanf("%d",&G.arcnum);printf(" 请依次输入顶点名（用空格分开且字符小于10）,按回车键结束：\n");printf(" ");for(i=1;i<=G.vexnum;i++) //从1号位置开始存储{scanf("%s",G.vertices[i].data); //从一号位置开始初始化G.vertices[i].firstarc=NULL;}printf("\n\n\n\n");printf(" ………………………………………输入小提示………………………………………\n");printf(" &&&&1 为避免输入遗漏，最好从选择任意一点，输入所有相邻边\n");printf(" &&&&2 输入边时格式(用空格分开，即格式为顶点（空格）顶点（空格)）\n");printf(" ………………………………………输入小提示………………………………………\n\n\n\n");for(k=0;k<G.arcnum;k++){printf("请输入相邻的两个顶点,按回车键结束：");scanf("%s%s",name1,name2);i=LocateVex(G,name1); //返回位序j=LocateVex(G,name2);p=(ArcNode *)malloc(sizeof(ArcNode)); //申请边节点p->adjvex=j; //插入到邻接表中，注意此处为逆向插入到单链表中p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;//无向图，注意是对称插入结点p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=i;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;}}/************************************************************ 求第一个顶点************************************************************/int FirstAdjVex(Graph G, int v){ArcNode *p;if(v>=1 && v<=G.vexnum){p=G.vertices[v].firstarc;if(p->nextarc==NULL)return 0;elsereturn (p->nextarc->adjvex); //返回第一个顶点字符}return -1;}/************************************************************ 求下一个顶点************************************************************/int NextAdjVex(Graph G, int v, int w){ //在图G中寻找第v个顶点的相对于w的下一个邻接顶点ArcNode *p;if(v>=1 && v<=G.vexnum && w>=1 && w<=G.vexnum){p=G.vertices[v].firstarc;while(p->adjvex!=w)p=p->nextarc; //在顶点v的弧链中找到顶点wif(p->nextarc!=NULL)return 0; //若已是最后一个顶点，返回0 elsereturn(p->nextarc->adjvex); //返回下一个邻接顶点的序号}return -1;}/************************************************************ 深度递归************************************************************/void DFS(Graph G, int v){int w;ArcNode *p;visited[v]=1;printf("%s ",G.vertices[v].data); //访问第v个顶点p=G.vertices[v].firstarc; //p为依附顶点的第一条边while (p!=NULL){w=p->adjvex;if(visited[w]==0)DFS(G,w);p=p->nextarc; //下移指针}}/************************************************************ 深度遍历************************************************************/void DFSTravel(Graph G,int v){for(int i=1;i<=G.vexnum;i++)visited[i]=0;int w;ArcNode *p;visited[v]=1;printf("%s ",G.vertices[v].data); //访问第v个顶点p=G.vertices[v].firstarc;while (p!=NULL){w=p->adjvex;if(visited[w]==0)DFS(G,w);p=p->nextarc;}}/************************************************************ 初始化队列************************************************************/Status InitQueue(Queue &Q){Q.elem = new int[MAX_QUEUE_NUMBER];Q.front = Q.rear = 0;return OK；}Status EmptyQueue(Queue Q){if(Q.front==Q.rear)return 0;elsereturn 1;}/*********************************************************** * 进队列* ***********************************************************/ Status EnQueue(Queue &Q, int e){if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)Q.elem[Q.rear ] = e;else ;Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;return OK；}/*********************************************************** * 出队列* ***********************************************************/ Status DeQueue(Queue &Q, int &e){if(Q.rear != Q.front)e = Q.elem[Q.front];else ;Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;return OK；}/*********************************************************** * 广度遍历************************************************************/void BFSTraverse(Graph G,char *name){ArcNode *p;int v,w,u,k=0;Queue Q;int visited[20];for(v=1;v<=G.vexnum;v++) //初始化visited[v]=0;InitQueue(Q);for(v=LocateVex(G,name);k!=2;v=(v+1)%(G.vexnum-1)) //v为输入的字符转化的位序{if(v+1==LocateVex(G,name)) //从v开始走完图的所有顶点k++;if(visited[v]==0){visited[v]=1;printf("%s ",G.vertices[v].data); //访问第v个顶点EnQueue(Q,v); // 进队while(EmptyQueue(Q)!=0){DeQueue(Q,u); //出队p=G.vertices[u].firstarc;while(p!=NULL){w=p->adjvex; //p边的下一个顶点if(visited[w]==0){printf("%s ",G.vertices[w].data);visited[w]=1;EnQueue(Q,w);}p=p->nextarc; //下移指针}}}}}主文件：#include <stdio.h>#include"malloc.h"#include "tuhead.h"#include "stdlib.h"#include "string.h"/************************************************************ 界面控制************************************************************/void main(){printf("\n################################# 图的遍历#################################\n");printf("\n $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");printf("\n");printf(" 1 ------- 图的创建\n");printf(" 2 ------- 图的深度优先遍历\n");printf(" 3 ------- 图的广度优先遍历\n");printf(" 0 ------- 退出\n");printf("\n $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");printf("\n");printf("请输入选择的操作代码（0-3）按回车键结束\n");MenuSelect(1);}/************************************************************ 功能选择************************************************************/void MenuSelect(int w){int select,done;int v;Graph G; char name[10];while (done) {printf("input the operating code : ");scanf("%d",&select);switch(select){case 1: printf("根据要求创建图:\n ");CreateGraph(G);break;case 2: printf("请输入深度优先遍历开始点的名：");scanf("%s",name);v=LocateVex(G,name); //将输入字符找到在顶点数组name对应的序号Vprintf("深度优先遍历：");DFSTravel(G,v);printf("\n");break;case 3: printf("请输入广度优先遍历开始点的名：");scanf("%s",name);printf("广度优先遍历：");BFSTraverse(G,name);printf("\n");break;case 0: done=0; break;default: printf(" ERROR\n");}printf("\n");}}[实验数据与结果]测试数据：实验结果。

深度优先遍历例题摘要：一、深度优先遍历概念介绍1.定义2.特点二、深度优先遍历算法应用1.图形遍历2.搜索算法三、深度优先遍历例题解析1.题目一：二叉树的深度优先遍历1.分析2.算法实现3.答案解析2.题目二：链式广度优先遍历1.分析2.算法实现3.答案解析四、深度优先遍历实战技巧与优化1.避免回溯2.提高效率正文：一、深度优先遍历概念介绍1.定义深度优先遍历（Depth-First Traversal，简称DFT）是一种遍历树或图的算法。

它沿着一个路径一直向前，直到达到最深的节点，然后回溯到上一个节点，继续沿着另一个路径遍历。

2.特点深度优先遍历的特点是访问一个节点后，会沿着该节点的子节点继续遍历，直到没有未访问的子节点为止。

此时，遍历过程会回溯到上一个节点，继续访问其未访问的子节点。

二、深度优先遍历算法应用1.图形遍历深度优先遍历在图形处理领域有广泛应用，如图像处理中的边缘检测、图像分割等。

通过遍历图像像素点，可以发现像素点之间的关系，从而实现图像处理任务。

2.搜索算法深度优先搜索（DFS）是一种经典的搜索算法，它采用深度优先策略在树或图中寻找目标节点。

DFS算法常用于解决迷宫问题、八皇后问题等。

三、深度优先遍历例题解析1.题目一：二叉树的深度优先遍历1.分析二叉树的深度优先遍历通常采用递归或栈实现。

递归方法简单，但效率较低；栈方法效率较高，但实现较复杂。

2.算法实现（递归）```def dfs(root):if not root:returnprint(root.val, end=" ")dfs(root.left)dfs(root.right)```3.答案解析按照题目给定的二叉树，进行深度优先遍历，得到的序列为：1 2 4 5 3 6 8。

2.题目二：链式广度优先遍历1.分析链式广度优先遍历与树的同层遍历类似，采用队列实现。

队列中的元素依次为当前层的节点，每次遍历时，取出队首节点，将其相邻节点加入队列，并将其标记为已访问。

精心整理课程设计题目九：图的广度优先遍历基本要求：采用邻接表存储结构实现图的广度优先遍历。

（2）对任意给定的图（顶点数和边数自定），建立它的邻接表并输出；（3）实现图的广度优先遍历*/#include<iostream.h>#include<stdio.h>#include<malloc.h>#defineMAX_NUM20intvisited[MAX_NUM]={0};typedefintVertexType;typedefenum{DG=1,UDG}GraphKind;typedefstructArcNode{intadjvex;intweight;structArcNode*nextarc;ArcNode*info;}ArcNode;typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;GraphKindkind;}ALGraph;voidPRIN(ALGraph&G);voidCreat_adjgraph(ALGraph&G);voidbfs(ALGraph&G,intv);voidCreat_adjgraphDG(ALGraph&G);voidCreat_adjgraphUDG(ALGraph&G);voidCreat_adjgraph(ALGraph&G);voidCreat_adjgraphDG(ALGraph&G){inti,s,d;ArcNode*p=NULL,*q=NULL;G.kind=DG;printf("请输入顶点数和边数：");scanf("%d%d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;++i){printf("第%d个顶点信息：",i+1);scanf("%d",&G.vertices[i].data);G.vertices[i].firstarc=NULL;}for(i=0;i<G.arcnum;++i){printf("第%d条边的起始顶点编号和终止顶点编号：",i+1);scanf("%d%d",&s,&d);while(s<1||s>G.vexnum||d<1||d>G.vexnum){printf("编号超出范围，重新输入");scanf("%d%d",&s,&d);}s--;d--;p=new(ArcNode);p->adjvex=d;p->nextarc=G.vertices[s].firstarc;G.vertices[s].firstarc=p;}}voidCreat_adjgraphUDG(ALGraph&G){inti,s,d;ArcNode*p,*q;G.kind=UDG;printf("请输入顶点数和边数：");scanf("%d%d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;++i){printf("第%d个顶点信息：",i+1);scanf("%d",&G.vertices[i].data);G.vertices[i].firstarc=NULL;}for(i=0;i<G.arcnum;++i){printf("第%d条边的起始顶点编号和终止顶点编号：",i+1);scanf("%d%d",&s,&d);while(s<1||s>G.vexnum||d<1||d>G.vexnum){printf("编号超出范围，重新输入");scanf("%d%d",&s,&d);}s--;d--;p=new(ArcNode);p->adjvex=d;p->nextarc=G.vertices[s].firstarc;G.vertices[s].firstarc=p;q=new(ArcNode);q->adjvex=s;q->nextarc=G.vertices[d].firstarc;G.vertices[d].firstarc=q;}}voidPRIN(ALGraph&G){inti;ArcNode*p;if(G.kind==DG||G.kind==UDG){for(i=0;i<G.vexnum;++i){printf("V%d:",G.vertices[i].data);p=G.vertices[i].firstarc;while(p!=NULL){printf("%d\t",p->adjvex+1);p=p->nextarc;}printf("\n");}}}voidbfs(ALGraph&G,intv){v--;ArcNode*p;intqueue[MAX_NUM],front=0,rear=0;intw,i;for(i=0;i<G.vexnum;i++)visited[i]=0;printf("%4d",v+1);visited[v]=1;rear=(rear+1)%MAX_NUM;queue[rear]=v;while(front!=rear){front=(front+1)%MAX_NUM;w=queue[front];p=G.vertices[w].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){printf("%3d",p->adjvex+1);visited[p->adjvex]=1;rear=(rear+1)%MAX_NUM;queue[rear]=p->adjvex;}p=p->nextarc;}}printf("\n");}voidCreat_adjgraph(ALGraph&G){printf("1：有向图2：无向图\n");printf("请根据上述提示输入图的类型：");scanf("%d",&G.kind);switch(G.kind){caseDG:Creat_adjgraphDG(G);PRIN(G);break;caseUDG:Creat_adjgraphUDG(G);PRIN(G);break;default:printf("ERROR");break;}}voidmain(){ALGraphG;Creat_adjgraph(G);printf("\n");printf("广度优先搜索遍历序列为：\n");bfs(G,1);printf("\n");}。

深度优先算法和广度优先算法都是图搜索中常见的算法，它们具有不同的特点和适用场景。

在进行全面评估之前，让我们先来了解一下深度优先算法和广度优先算法的基本概念和原理。

### 1. 深度优先算法（Depth-First Search, DFS）深度优先算法是一种用于遍历或搜索树或图的算法。

其核心思想是从起始顶点出发，沿着一条路径直到末端，然后回溯，继续搜索下一条路径，直到所有路径都被探索。

在实际应用中，深度优先算法常常通过递归或栈来实现。

### 2. 广度优先算法（Breadth-First Search, BFS）广度优先算法也是一种用于遍历或搜索树或图的算法。

其核心思想是从起始顶点出发，依次遍历该顶点的所有相邻顶点，然后再以这些相邻顶点作为起点，继续遍历它们的相邻顶点，以此类推，直到所有顶点都被遍历。

在实际应用中，广度优先算法通常通过队列来实现。

### 3. 深度优先算法和广度优先算法的时间复杂度在实际应用中，我们经常需要对算法的时间复杂度进行分析。

针对深度优先算法和广度优先算法，它们的时间复杂度并不相同。

- 深度优先算法的时间复杂度：O(V + E)，其中V为顶点数，E为边数。

在最坏的情况下，如果采用邻接矩阵来表示图的话，深度优先算法的时间复杂度为O(V^2)；如果采用邻接表来表示图的话，时间复杂度为O(V + E)。

- 广度优先算法的时间复杂度：O(V + E)，其中V为顶点数，E为边数。

无论采用邻接矩阵还是邻接表表示图，广度优先算法的时间复杂度都是O(V + E)。

### 4. 个人理解和观点在实际应用中，我们在选择使用深度优先算法还是广度优先算法时，需要根据具体的问题场景来进行选择。

如果要寻找图中的一条路径，或者判断两个节点之间是否存在路径，通常会选择使用深度优先算法；如果要寻找最短路径或者进行层次遍历，通常会选择使用广度优先算法。

深度优先算法和广度优先算法都是非常重要的图搜索算法，它们各自适用于不同的场景，并且具有不同的时间复杂度。

20．给出右图所示有向图的邻接矩阵、邻接表，并给出每个顶点的入度和出度。

解：(a)邻接矩阵为： 邻接表为： 011000000010000101000011000000000010⎛⎫ ⎪ ⎪ ⎪⎪ ⎪⎪ ⎪ ⎪⎝⎭逆邻接表为：入度和出度为：(b)邻接矩阵为：0111010101110111010101110⎛⎫ ⎪ ⎪⎪ ⎪ ⎪ ⎪⎝⎭邻接表=逆邻接表为：21．对右图所示网分别给出：(1) 深度优先搜索遍历序列（分别从V1和V4开始）; （2）广度优先搜索遍历序列（分别从V1和V4开始）; （3）用普里姆算法求得最小生成树的过程； （4）用克鲁斯卡尔算法求得最小生成树的过程；解：从V1开始的深度优先搜索序列为： 1 2 4 3 5 6 7 8从V4开始的深度优先搜索序列为： 4 2 1 3 5 6 7 8 序列不唯一，可有其他形式。

（3）广度优先搜索遍历序列（分别从V1和V4开始）;解：从V1开始的广度优先搜索序列为： 1 2 3 4 5 6 7 8从V4开始的广度优先搜索序列为： 4 2 3 5 6 1 7 8 序列不唯一，可有其他形式。

（4）用普里姆算法求得最小生成树的过程； 解:{3,4}, {3,4},{4,2},{3,4},{4,2},{2,1},{3,4},{4,2},{2,1},{4,6},{3,4},{4,2},{2,1},{4,6},{6,5},{3,4},{4,2},{2,1},{4,6},{6,5},{6,8},{3,4},{4,2},{2,1},{4,6},{6,5},{6,8},{8,7}, (不唯一)（5）用克鲁斯卡尔算法求得最小生成树的过程；解： (不唯一){1},{2},{3},{4},{5},{6},{7},{8},{1},{2},{3,4},{5},{6},{7},{8},{1},{2},{3,4},{5,6},{7},{8},{1},{2},{3,4},{{5,6},{6,8}},{7},{1},{{2,4},{3,4}},{{5,6},{6,8}},{7},{{1,2},{2,4},{3,4}},{{5,6},{6,8}},{7},{{1,2},{2,4},{3,4}},{{5,6},{6,8},{8,7}},{{1,2},{2,4},{3,4},{4,6},{5,6},{6,8},{8,7}},23．给出右图所示无环图的所有拓扑有序序列。

深度优先遍历算法实现及复杂度分析深度优先遍历算法（Depth First Search, DFS）是一种常用的图遍历算法，用于查找或遍历图的节点。

本文将介绍深度优先遍历算法的实现方法，并进行对应的复杂度分析。

一、算法实现深度优先遍历算法的基本思想是从图的某个节点出发，沿着深度方向依次访问其相邻节点，直到无法继续下去，然后返回上一层节点继续遍历。

下面是深度优先遍历算法的伪代码：```1. 初始化访问标记数组visited[]，将所有节点的访问标记置为false。

2. 从某个节点v开始遍历：- 标记节点v为已访问（visited[v] = true）。

- 访问节点v的相邻节点：- 若相邻节点w未被访问，则递归调用深度优先遍历算法（DFS(w)）。

3. 遍历结束，所有节点都已访问。

```二、复杂度分析1. 时间复杂度深度优先遍历算法的时间复杂度取决于图的存储方式和规模。

假设图的节点数为V，边数为E。

- 邻接表存储方式：对于每个节点，需要访问其相邻节点。

因此，算法的时间复杂度为O(V+E)。

- 邻接矩阵存储方式：需要检查每个节点与其他节点的连通关系，即需要遍历整个邻接矩阵。

因此，算法的时间复杂度为O(V^2)。

2. 空间复杂度深度优先遍历算法使用了一个辅助的访问标记数组visited[]来记录每个节点的访问状态。

假设图的节点数为V。

- 邻接表存储方式：访问标记数组visited[]的空间复杂度为O(V)。

- 邻接矩阵存储方式：访问标记数组visited[]的空间复杂度同样为O(V)。

综上所述，深度优先遍历算法的时间复杂度为O(V+E)，空间复杂度为O(V)。

三、应用场景深度优先遍历算法在图的遍历和搜索问题中广泛应用。

以下是一些典型的应用场景：1. 连通性问题：判断图中两个节点之间是否存在路径。

2. 非连通图遍历：对于非连通图，深度优先遍历算法可以用于遍历所有连通分量。

3. 寻找路径：在图中寻找从起始节点到目标节点的路径。

数据结构课设——有向图的深度、⼴度优先遍历及拓扑排序任务：给定⼀个有向图，实现图的深度优先, ⼴度优先遍历算法，拓扑有序序列，并输出相关结果。

功能要求：输⼊图的基本信息，并建⽴图存储结构（有相应提⽰），输出遍历序列，然后进⾏拓扑排序，并测试该图是否为有向⽆环图，并输出拓扑序列。

按照惯例，先上代码，注释超详细：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#pragma warning(disable:4996)#define Max 20//定义数组元素最⼤个数（顶点最⼤个数）typedef struct node//边表结点{int adjvex;//该边所指向结点对应的下标struct node* next;//该边所指向下⼀个结点的指针}eNode;typedef struct headnode//顶点表结点{int in;//顶点⼊度char vertex;//顶点数据eNode* firstedge;//指向第⼀条边的指针，边表头指针}hNode;typedef struct//邻接表（图）{hNode adjlist[Max];//以数组的形式存储int n, e;//顶点数，边数}linkG;//以邻接表的存储结构创建图linkG* creat(linkG* g){int i, k;eNode* s;//边表结点int n1, e1;char ch;g = (linkG*)malloc(sizeof(linkG));//申请结点空间printf("请输⼊顶点数和边数：");scanf("%d%d", &n1, &e1);g->n = n1;g->e = e1;printf("顶点数：%d 边数：%d\n", g->n, g->e);printf("请输⼊顶点信息（字母）：");getchar();//因为接下来要输⼊字符串，所以getchar⽤于承接上⼀条命令的结束符for (i = 0; i < n1; i++){scanf("%c", &ch);g->adjlist[i].vertex = ch;//获得该顶点数据g->adjlist[i].firstedge = NULL;//第⼀条边设为空}printf("\n打印顶点下标及顶点数据：\n");for (i = 0; i < g->n; i++)//循环打印顶点下标及顶点数据{printf("顶点下标：%d 顶点数据：%c\n", i, g->adjlist[i].vertex);}getchar();int i1, j1;//相连接的两个顶点序号for (k = 0; k < e1; k++)//建⽴边表{printf("请输⼊对<i,j>（空格分隔）：");scanf("%d%d", &i1, &j1);s = (eNode*)malloc(sizeof(eNode));//申请边结点空间s->adjvex = j1;//边所指向结点的位置，下标为j1s->next = g->adjlist[i1].firstedge;//将当前s的指针指向当前顶点上指向的结点g->adjlist[i1].firstedge = s;//将当前顶点的指针指向s}return g;//返回指针g}int visited[Max];//标记是否访问void DFS(linkG* g, int i)//深度优先遍历{eNode* p;printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已访问过的顶点visited值改为1p = g->adjlist[i].firstedge;//p指向顶点i的第⼀条边while (p)//p不为NULL时（边存在）{if (visited[p->adjvex] != 1)//如果没有被访问DFS(g, p->adjvex);//递归}p = p->next;//p指向下⼀个结点}}void DFSTravel(linkG* g)//遍历⾮连通图{int i;printf("深度优先遍历;\n");//printf("%d\n",g->n);for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问{DFS(g, i);//调⽤DFS函数}}}void BFS(linkG* g, int i)//⼴度优先遍历{int j;eNode* p;int q[Max], front = 0, rear = 0;//建⽴顺序队列⽤来存储，并初始化printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已经访问过的改成1rear = (rear + 1) % Max;//普通顺序队列的话，这⾥是rear++q[rear] = i;//当前顶点（下标）队尾进队while (front != rear)//队列⾮空{front = (front + 1) % Max;//循环队列，顶点出队j = q[front];p = g->adjlist[j].firstedge;//p指向出队顶点j的第⼀条边while (p != NULL){if (visited[p->adjvex] == 0)//如果未被访问{printf("%c ", g->adjlist[p->adjvex].vertex);visited[p->adjvex] = 1;//将该顶点标记数组值改为1rear = (rear + 1) % Max;//循环队列q[rear] = p->adjvex;//该顶点进队}p = p->next;//指向下⼀个结点}}}void BFSTravel(linkG* g)//遍历⾮连通图{int i;printf("⼴度优先遍历：\n");for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问过{BFS(g, i);//调⽤BFS函数}}}//因为拓扑排序要求⼊度为0，所以需要先求出每个顶点的⼊度void inDegree(linkG* g)//求图顶点⼊度{eNode* p;int i;for (i = 0; i < g->n; i++)//循环将顶点⼊度初始化为0{g->adjlist[i].in = 0;}for (i = 0; i < g->n; i++)//循环每个顶点{p = g->adjlist[i].firstedge;//获取第i个链表第1个边结点指针while (p != NULL)///当p不为空（边存在）{g->adjlist[p->adjvex].in++;//该边终点结点⼊度+1p = p->next;//p指向下⼀个边结点}printf("顶点%c的⼊度为：%d\n", g->adjlist[i].vertex, g->adjlist[i].in);}void topo_sort(linkG *g)//拓扑排序{eNode* p;int i, k, gettop;int top = 0;//⽤于栈指针的下标索引int count = 0;//⽤于统计输出顶点的个数int* stack=(int *)malloc(g->n*sizeof(int));//⽤于存储⼊度为0的顶点for (i=0;i<g->n;i++)//第⼀次搜索⼊度为0的顶点{if (g->adjlist[i].in==0){stack[++top] = i;//将⼊度为0的顶点进栈}}while (top!=0)//当栈不为空时{gettop = stack[top--];//出栈,并保存栈顶元素（下标）printf("%c ",g->adjlist[gettop].vertex);count++;//统计顶点//接下来是将邻接点的⼊度减⼀，并判断该点⼊度是否为0p = g->adjlist[gettop].firstedge;//p指向该顶点的第⼀条边的指针while (p)//当p不为空时{k = p->adjvex;//相连接的顶点（下标）g->adjlist[k].in--;//该顶点⼊度减⼀if (g->adjlist[k].in==0){stack[++top] = k;//如果⼊度为0，则进栈}p = p->next;//指向下⼀条边}}if (count<g->n)//如果输出的顶点数少于总顶点数，则表⽰有环{printf("\n有回路！\n");}free(stack);//释放空间}void menu()//菜单{system("cls");//清屏函数printf("************************************************\n");printf("* 1.建⽴图 *\n");printf("* 2.深度优先遍历 *\n");printf("* 3.⼴度优先遍历 *\n");printf("* 4.求出顶点⼊度 *\n");printf("* 5.拓扑排序 *\n");printf("* 6.退出 *\n");printf("************************************************\n");}int main(){linkG* g = NULL;int c;while (1){menu();printf("请选择：");scanf("%d", &c);switch (c){case1:g = creat(g); system("pause");break;case2:DFSTravel(g); system("pause");break;case3:BFSTravel(g); system("pause");break;case4:inDegree(g); system("pause");break;case5:topo_sort(g); system("pause");break;case6:exit(0);break;}}return0;}实验⽤图:运⾏结果：关于深度优先遍历 a.从图中某个顶点v 出发，访问v 。

邻接矩阵的深度优先遍历算法简介邻接矩阵是一种常用的图表示方法，它使用一个二维数组来表示图中各个节点之间的关系。

深度优先遍历（Depth First Search，DFS）是一种常用的图遍历算法，它通过递归或栈的方式依次访问图中的所有节点。

本文将介绍邻接矩阵的深度优先遍历算法，并提供相应的代码实现。

邻接矩阵邻接矩阵是一种二维数组，它的行和列分别代表图中的各个节点。

如果两个节点之间存在边，则对应位置上的元素为1；否则为0。

对于无向图来说，邻接矩阵是对称的；而对于有向图来说，邻接矩阵不一定对称。

下面是一个示例的邻接矩阵：A B C DA 0 1 0 1B 1 0 1 1C 0 1 0 0D 1 1 0 0深度优先遍历算法算法思想深度优先遍历算法从起始节点开始，递归或使用栈的方式依次访问与当前节点相邻的未访问过的节点，直到所有节点都被访问过为止。

算法步骤1.创建一个栈，并将起始节点入栈；2.创建一个数组，用于记录已经访问过的节点；3.当栈不为空时，执行以下操作：–从栈顶弹出一个节点，标记为已访问，并输出该节点；–遍历该节点的邻居节点，如果邻居节点未被访问，则将其入栈；4.重复步骤3，直到栈为空。

算法实现def dfs(adj_matrix, start_node):stack = [start_node]visited = [False] * len(adj_matrix)while stack:node = stack.pop()visited[node] = Trueprint(node)for i in range(len(adj_matrix)):if adj_matrix[node][i] == 1 and not visited[i]:stack.append(i)示例假设有以下图的邻接矩阵：A B C DA 0 1 0 1B 1 0 1 1C 0 1 0 0D 1 1 0我们以A作为起始节点进行深度优先遍历，那么遍历的顺序将会是A、B、C、D。

算法设计：深度优先遍历和广度优先遍历实现深度优先遍历过程1、图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。

它是许多图的算法的基础。

深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。

它们对无向图和有向图均适用。

注意：以下假定遍历过程中访问顶点的操作是简单地输出顶点。

2、布尔向量visited[0．．n-1]的设置图中任一顶点都可能和其它顶点相邻接。

在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。

为了避免重复访问同一个顶点，必须记住每个已访问的顶点。

为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。

--------------------------深度优先遍历(Depth-First Traversal)1．图的深度优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。

在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。

若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。

若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。

采用的搜索方法的特点是尽可能先对纵深方向进行搜索。

这种搜索方法称为深度优先搜索(Depth-First Search)。

相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

2、深度优先搜索的过程设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。

若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。

广度优先算法和深度优先算法
广度优先算法和深度优先算法是最常用的两种图遍历算法，它们都能
够遍历整个图的节点，但在具体应用场景中选择哪种算法需要根据实
际需求来判断。

广度优先算法（BFS）将当前节点的所有邻居节点都遍历一遍后再遍历下一层，可以确保找到最短路径。

具体实现方式是使用一个队列来存
储被访问过但还未被遍历过的节点，同一层的节点都在队列中，不同
层的节点通过队列的先进先出特性被访问。

BFS遍历图通常需要记录
每个节点是否被访问过，以防止重复遍历。

深度优先算法（DFS）是一种递归算法，从某一节点出发一直向下遍
历到底（即遍历到一个叶子节点），然后返回到上一层节点继续遍历，直到遍历完整个图。

DFS相较于BFS具有更好的空间复杂度，但不能
保证找到最短路径。

DFS遍历图时通常需要记录每个节点是否被访问过，并保证不重复访问。

广度优先算法和深度优先算法在选择上需要根据具体算法应用需求。

如果需要找到最短路径，则选择广度优先算法，如果需要搜索所有可
能路径，则选择深度优先算法。

例如，在迷宫的寻找最短路径场景中，BFS可以从迷宫入口出发，按照层级一层一层的向外扩展搜索，最终
一定能够找到终点，但会消耗较大的空间；而DFS则可以搜索所有可能的路径，但不能确保找到最短路径。

综上所述，广度优先算法和深度优先算法都各有优缺点，在选择上需要根据实际应用场景判断。

深度遍历和广度遍历例题深度遍历（Depth-First Search，DFS）和广度遍历（Breadth-First Search，BFS）是图遍历算法中常用的两种方法。

下面我将为你提供一个例题，并从多个角度进行全面的回答。

例题，给定一个无向图，使用深度遍历和广度遍历两种方法遍历该图，并输出遍历的结果。

首先，我们需要明确一下图的表示方式。

常用的图表示方法有邻接矩阵和邻接表，这里我们选择使用邻接表表示图。

假设我们有如下无向图：A./ \。

B---C.\ /。

D.邻接表表示如下：A: B, C.B: A, C, D.C: A, B, D.D: B, C.接下来，我们来进行深度遍历。

深度遍历的基本思想是从起始节点开始，尽可能深地访问每个节点，直到无法继续深入为止，然后回溯到上一个节点，继续访问其他未访问的节点。

从节点A开始进行深度遍历，访问顺序为A-B-C-D。

具体步骤如下：1. 将节点A标记为已访问。

2. 访问与节点A相邻的未被访问的节点，即节点B和节点C。

3. 选择其中一个节点（这里选择节点B），将其标记为已访问，并继续深度遍历该节点。

4. 对节点B进行相同的操作，访问与节点B相邻的未被访问的节点，即节点A、节点C和节点D。

5. 选择其中一个节点（这里选择节点C），将其标记为已访问，并继续深度遍历该节点。

6. 对节点C进行相同的操作，访问与节点C相邻的未被访问的节点，即节点A、节点B和节点D。

7. 选择其中一个节点（这里选择节点D），将其标记为已访问，并继续深度遍历该节点。

8. 由于节点D没有未被访问的相邻节点，回溯到节点C。

9. 由于节点C也没有未被访问的相邻节点，回溯到节点B。

10. 由于节点B还有一个未被访问的相邻节点（节点A），将其标记为已访问，并继续深度遍历该节点。

11. 由于节点A没有未被访问的相邻节点，回溯到节点B。

12. 由于节点B没有未被访问的相邻节点，回溯到节点A。

13. 完成深度遍历。

邻接表的深度遍历邻接表是一种表示图的数据结构，深度遍历是一种图遍历的算法。

下面是邻接表的深度遍历的一般步骤：1.初始化：建立一个布尔类型的数组，用于标记节点是否已经被访问。

2.选择起始节点：从图中选择一个未被访问的节点作为起始节点。

3.深度优先遍历：对于选定的起始节点，进行深度优先遍历。

具体步骤如下：•将当前节点标记为已访问。

•访问当前节点，并执行相应的操作。

•对于当前节点的所有未访问邻接节点，递归调用深度遍历函数。

4.迭代：重复步骤3，直到所有节点都被访问。

下面是一个深度遍历的伪代码示例，假设图用邻接表表示：# 定义图的邻接表表示graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F', 'G'],'D': ['B'],'E': ['B', 'H'],'F': ['C'],'G': ['C'],'H': ['E']}# 定义深度遍历函数def dfs(node, visited):if node not in visited:print(node)visited.add(node)for neighbor in graph[node]:dfs(neighbor, visited)# 初始化已访问节点的集合visited_set = set()# 选择起始节点start_node = 'A'# 调用深度遍历函数dfs(start_node, visited_set)这个示例中，图用字典表示，每个节点对应一个键，对应的值是一个列表，包含与该节点邻接的节点。

Java实现⽆向图的建⽴与遍历⼀、基于邻接矩阵表⽰法的⽆向图 邻接矩阵是⼀种利⽤⼀维数组记录点集信息、⼆维数组记录边集信息来表⽰图的表⽰法，因此我们可以将图抽象成⼀个类，点集信息和边集信息抽象成类的属性，就可以在Java中描述出来，代码如下：1class AMGraph{23private String[] vexs = null; //点集信息45private int[][] arcs = null; //边集信息67 } 每⼀个具体的图，就是该类的⼀个实例化对象，因此我们可以在构造函数中实现图的创建，代码如下：1public AMGraph(int vexNum,int arcNum) { //输⼊点的个数和边的个数23this.vexs = new String[vexNum];4this.arcs = new int[vexNum][vexNum];56 System.out.print("请依次输⼊顶点值，以空格隔开：");7 Scanner sc = new Scanner(System.in);8for(int i = 0; i < vexNum; i++) { //根据输⼊建⽴点集9this.vexs[i] = sc.next();10 }1112for(int i = 0; i < vexNum; i++) { //初始化边集13for(int j = 0; j < vexNum; j++) {14this.arcs[i][j] = 0; //0表⽰该位置所对应的两顶点之间没有边15 }16 }1718 start:for(int i = 0; i < arcNum; i++) { //开始建⽴边集1920 sc = new Scanner(System.in);21int vex1Site = 0;22int vex2Site = 0;23 String vex1 = null;24 String vex2 = null;2526 System.out.print("请输⼊第" + (i+1) + "条边所依附的两个顶点，以空格隔开：");27 vex1 = sc.next();28 vex2 = sc.next();29for(int j = 0; j < this.vexs.length; j++) { //查找输⼊的第⼀个顶点的位置30if (this.vexs[j].equals(vex1)) {31 vex1Site = j;32break;33 }34if (j == this.vexs.length - 1) {35 System.out.println("未找到第⼀个顶点，请重新输⼊！");36 i--;37continue start;38 }39 }40for (int j = 0; j < this.vexs.length; j++) { //查找输⼊的第⼆个顶点的位置41if(this.vexs[j].equals(vex2)) {42 vex2Site = j;43break;44 }45if (j == this.vexs.length - 1) {46 System.out.println("未找到第⼆个顶点，请重新输⼊！");47 i--;48continue start;49 }50 }51if(this.arcs[vex1Site][vex2Site] != 0) { //检测该边是否已经输⼊52 System.out.println("该边已存在！");53 i--;54continue start;55 }else {56this.arcs[vex1Site][vex2Site] = 1; //1表⽰该位置所对应的两顶点之间有边57this.arcs[vex2Site][vex1Site] = 1; //对称边也置158 }59 }60 System.out.println("基于邻接矩阵的⽆向图创建成功！");61 sc.close();62 } 创建好图后，我们还要实现图的遍历。

深度优先遍历例题摘要：1.深度优先遍历基本概念2.深度优先遍历算法实现3.深度优先遍历应用实例正文：【1.深度优先遍历基本概念】深度优先遍历（Depth-First Traversal，简称DFT）是一种遍历树或图的算法。

该算法从某个起始节点开始，沿着树或图的深度优先地访问相邻节点，直到无法继续访问为止。

然后回溯到上一个节点，继续访问其他相邻节点。

重复这个过程，直到访问完所有的节点。

深度优先遍历的特点是简单易懂，实现起来较为直观。

其缺点是可能会出现重复访问节点的情况，尤其是在存在环的情况下。

【2.深度优先遍历算法实现】下面是一个使用递归方法实现的深度优先遍历算法：```void DFS(int node, vector<vector<int>>& adj, vector<bool>& visited) {// 标记当前节点已访问visited[node] = true;// 在此处执行对当前节点的操作（例如输出节点值）// 遍历当前节点的相邻节点for (int neighbor : adj[node]) {// 如果相邻节点未被访问，则继续深度优先遍历if (!visited[neighbor]) {DFS(neighbor, adj, visited);}}}```【3.深度优先遍历应用实例】深度优先遍历广泛应用于各种图算法中，例如寻找连通分量、拓扑排序、寻找最短路径等。

下面是一个简单的实例，展示如何使用深度优先遍历寻找一个无向图中的连通分量：```int main() {int n;cin >> n;vector<vector<int>> adj(n);for (int i = 0; i < n; i++) {cin >> adj[i].size();for (int j = 0; j < adj[i].size(); j++) {cin >> adj[i][j];}}vector<bool> visited(n, false);vector<int> dfn(n, -1);bool connected = true;for (int i = 0; i < n; i++) {if (!visited[i]) {DFS(i, adj, visited);dfn[i] = i;connected = connected && (i == dfn[i]);}}if (!connected) {cout << "The graph is not connected." << endl;} else {cout << "The number of connected components is " << dfn.size() << "." << endl;}return 0;}```这个实例中，我们使用深度优先遍历遍历整个图，标记每个节点的访问情况。

visited
4
5
f
^
对应的邻接表
终点2作为下次的始点， 由于1点已访问过，跳过， 找到4，记标识，送输出， 4有作为新的始点重复上 述过程
1 2 4
5
输出数组 resu
3．邻接表深度优先遍历的实现
template <class TElem, class TEdgeElem>long DFS2(TGraphNodeAL<TElem, TEdgeElem> *nodes,long n,long v0, char *visited, long *resu,long &top) {//深度优先遍历用邻接表表示的图。nodes是邻接表的头数组，n 为结点个数（编号为0~n）。 //v0为遍历的起点。返回实际遍历到的结点的数目。 //visited是访问标志数组，调用本函数前，应为其分配空间并初 始化为全0(未访问) //resu为一维数组，用于存放所遍历到的结点的编号，调用本函 数前，应为其分配空间 long nNodes, i; TGraphEdgeAL<TEdgeElem> *p; nNodes=1;
1 2
4
图 20-1有向图
5
3
1 2 3 4 5
1 0 1 0 1 0
2 1 0 0 0 0
3 0 0 0 0 0
4 0 1 0 0 0
5 1 0 1 0 0
1 2 3 4 5
1 1 0 1 1
1 2 4 5
所示图的邻接矩阵g
访问标识数组 visited
输出数组 resu
例如从1点深度优先遍历，先把1设置访问标志，并置入输出数组resu，然后从邻接 矩阵的第一行，扫描各列，找到最近的邻接点2，将其设置访问标志，并进入输出数 组，接着从邻接矩阵的2行扫描，找到第一个构成边的点是1，检查访问标识数组， 发现1已经访问过，跳过，找第二个构成边 的点4，设置访问标识，进入输出数组， 再从邻接矩阵的第4行扫描，寻找构成边的点，除1外在无其他点，返回2行，继续 寻找，也无新点，返回1，找到5，将5置访问标志，进入输出数组，1行再无其他新 点，遍历结束，返回遍历元素个数为4 。

深度优先遍历算法和广度优先遍历算法实验小结一、引言在计算机科学领域，图的遍历是一种基本的算法操作。

深度优先遍历算法（Depth First Search，DFS）和广度优先遍历算法（Breadth First Search，BFS）是两种常用的图遍历算法。

它们在解决图的连通性和可达性等问题上具有重要的应用价值。

本文将从理论基础、算法原理、实验设计和实验结果等方面对深度优先遍历算法和广度优先遍历算法进行实验小结。

二、深度优先遍历算法深度优先遍历算法是一种用于遍历或搜索树或图的算法。

该算法从图的某个顶点开始遍历，沿着一条路径一直向前直到不能再继续前进为止，然后退回到上一个节点，尝试下一个节点，直到遍历完整个图。

深度优先遍历算法通常使用栈来实现。

以下是深度优先遍历算法的伪代码：1. 创建一个栈并将起始节点压入栈中2. 将起始节点标记为已访问3. 当栈不为空时，执行以下步骤：a. 弹出栈顶节点，并访问该节点b. 将该节点尚未访问的邻居节点压入栈中，并标记为已访问4. 重复步骤3，直到栈为空三、广度优先遍历算法广度优先遍历算法是一种用于遍历或搜索树或图的算法。

该算法从图的某个顶点开始遍历，先访问起始节点的所有相邻节点，然后再依次访问这些相邻节点的相邻节点，依次类推，直到遍历完整个图。

广度优先遍历算法通常使用队列来实现。

以下是广度优先遍历算法的伪代码：1. 创建一个队列并将起始节点入队2. 将起始节点标记为已访问3. 当队列不为空时，执行以下步骤：a. 出队一个节点，并访问该节点b. 将该节点尚未访问的邻居节点入队，并标记为已访问4. 重复步骤3，直到队列为空四、实验设计本次实验旨在通过编程实现深度优先遍历算法和广度优先遍历算法，并通过对比它们在不同图结构下的遍历效果，验证其算法的正确性和有效性。

具体实验设计如下：1. 实验工具：使用Python编程语言实现深度优先遍历算法和广度优先遍历算法2. 实验数据：设计多组图结构数据，包括树、稠密图、稀疏图等3. 实验环境：在相同的硬件环境下运行实验程序，确保实验结果的可比性4. 实验步骤：编写程序实现深度优先遍历算法和广度优先遍历算法，进行多次实验并记录实验结果5. 实验指标：记录每种算法的遍历路径、遍历时间和空间复杂度等指标，进行对比分析五、实验结果在不同图结构下，经过多次实验，分别记录了深度优先遍历算法和广度优先遍历算法的实验结果。

因此访问顺序是：A => C => D => F => B => G => E
2.2.2 有向图的广广度优先搜索
下面面以“有向图”为例例，来对广广度优先搜索进行行行演示。还是以上面面的图G2为例例进行行行说明。
第1步：访问A。 第2步：访问B。 第3步：依次访问C,E,F。 在访问了了B之后，接下来访问B的出边的另一一个顶点，即C,E,F。前 面面已经说过，在本文文实现中，顶点ABCDEFG按照顺序存储的，因此会先访问C，再依次访 问E,F。 第4步：依次访问D,G。 在访问完C,E,F之后，再依次访问它们的出边的另一一个顶点。还是按 照C,E,F的顺序访问，C的已经全部访问过了了，那么就只剩下E,F；先访问E的邻接点D，再访 问F的邻接点G。
if(mVexs[i]==ch)
return i;
return -1;
}
/* * 读取一一个输入入字符
*/
private char readChar() {
char ch='0';
do {
try {
ch = (char)System.in.read();
} catch (IOException e) {
数据结构与算法（13）：深度优先搜索和 广广度优先搜索
BFS和DFS是两种十十分重要的搜索算法，BFS适合查找最优解，DFS适合查找是否存在解(或者说 能找到任意一一个可行行行解)。用用这两种算法即可以解决大大部分树和图的问题。
一一、深度优先搜索（DFS）
1.1 介绍
图的深度优先搜索（Depth First Search），和树的先序遍历比比较类似。 它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点V出发，首首先访问该顶点， 然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至至图中所有和V有路路径相通 的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一一个未被访问的顶点作起始点，重 复上述过程，直至至图中所有顶点都被访问到为止止。 显然，深度优先搜索是一一个递归的过程。