今天学习了数据结构中的邻接表存储实现图的深度优先遍历，其中让我受益匪浅，以下是我的解题思路。
编写程序，实现由邻接表存储实现无向图的深度优先搜索遍历的功能。顶点为字符型。
输入格式:
第一行输入顶点个数及边的个数，第二行依次输入各顶点，第三行开始依次输入边的两个顶点，用空格分开。最后输入深度优先遍历的起始点。
输出格式:
输出深度优先遍历结果，空格分开，若起始点不合理，则输出error。
代码如下：（c++）
#include<iostream> #include<queue> using namespace std; struct ArcNode { int adjvex; //该弧所指向的顶点的位置 ArcNode * next; //指向下一条弧的指针 //int weight;边上是否有权 }; typedef struct VNode { int vertex; //顶点信息 ArcNode * firstarc; //指向第一条依附该顶点的弧的指针 }AdjList[20]; struct ALGraph { AdjList adjList; int vexNum; //图的顶点数 int arcNum; //图的弧数 }; bool visited[20];//设置标志数组 void CreateGraph(ALGraph & graph); void DFSTraverse(ALGraph & graph); int temp_2=1; int main() { int temp_1; ALGraph graph; CreateGraph(graph); cin>>temp_1; //cout<<temp_1; for(int i=0;i<graph.vexNum;i++) { if(temp_1==graph.adjList[i].vertex) { temp_2=0; } } if(temp_2==0) { DFSTraverse(graph); } if(temp_2==1){ cout<<"error"; } return 0; } void CreateGraph(ALGraph & graph) { cin >> graph.vexNum; cin >> graph.arcNum; for (int i = 0; i < graph.vexNum; i++) { cin >> graph.adjList[i].vertex; graph.adjList[i].firstarc = nullptr; } int h1, h2; ArcNode * temp; for (int i = 0; i < graph.arcNum; i++) { cin >> h1 >> h2; temp = new ArcNode; temp->adjvex = h2; temp->next = graph.adjList[h1].firstarc; graph.adjList[h1].firstarc = temp; temp = new ArcNode; temp->adjvex = h1; temp->next = graph.adjList[h2].firstarc; graph.adjList[h2].firstarc = temp; } } void DFS(ALGraph & graph, int v) { visited[v] = true; cout << graph.adjList[v].vertex << " "; ArcNode * p = graph.adjList[v].firstarc; while (p) { if (!visited[p->adjvex]) DFS(graph, p->adjvex); p = p->next; } } void DFSTraverse(ALGraph & graph) { for (int i = 0; i < graph.vexNum; i++)//初始化访问标志数组 visited[i] = false; for (int i = 0; i < graph.vexNum; i++) { if (!visited[i])//如果没有访问 DFS(graph, i); } }