图的深度优先遍历，基于邻接链表的非递归实现

r囧r小猫 2022-09-20 15:12 93阅读 0赞

![SouthEast][]

测试数据基于上图，新增4->1的路径。程序存在内存泄漏。

使用时可以修改depth\_first\_search第二个参数，指定开始遍历的结点，只适用与连通图。如果错误，欢迎指正！！

\#include <iostream>

\#include <stack>  
  
  
using namespace std;  
  
  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
\* 图的深度优先遍历  
\* 基于邻接链表的非递归实现  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
  
  
typedef char vertex\_t; //结点数据类型  
  
  
//边结点  
typedef struct \_tag\_edge\_node\_t  
\{  
int node\_num; //边终点所在数组序号  
\_tag\_edge\_node\_t\* next\_node; //下一条边  
\}edge\_node\_t;  
  
  
//顶点结点  
typedef struct \_tag\_head\_node\_t  
\{  
vertex\_t data; //结点数据  
edge\_node\_t\* first\_edge; //第一条边  
\}head\_node\_t;  
  
  
\#define MAX\_NUMBER 20 //图中最大结点数目  
  
  
//图结构  
typedef struct \_tag\_graph\_t  
\{  
head\_node\_t head\_data\[MAX\_NUMBER\]; //顶点数组  
unsigned int head\_node\_count; //顶点数目  
\}graph\_t;  
  
  
void create\_adjacency\_list(graph\_t\* graph)  
\{  
edge\_node\_t\* p\_edge = NULL;  
if (graph == NULL)  
return;  
  
  
graph->head\_node\_count = 6;  
for (unsigned int i = 0; i < graph->head\_node\_count; ++i)  
\{  
graph->head\_data\[i\].data = 'A' + i;  
graph->head\_data\[i\].first\_edge = NULL;  
\}  
  
  
graph->head\_data\[0\].first\_edge = new edge\_node\_t;  
p\_edge = graph->head\_data\[0\].first\_edge;  
p\_edge->node\_num = 2;  
  
p\_edge->next\_node = new edge\_node\_t;  
p\_edge = p\_edge->next\_node;  
p\_edge->node\_num = 4;  
  
  
p\_edge->next\_node = new edge\_node\_t;  
p\_edge = p\_edge->next\_node;  
p\_edge->node\_num = 5;  
p\_edge->next\_node = NULL;  
  
  
graph->head\_data\[1\].first\_edge = new edge\_node\_t;  
graph->head\_data\[1\].first\_edge->node\_num = 2;  
graph->head\_data\[1\].first\_edge->next\_node = NULL;  
  
  
graph->head\_data\[2\].first\_edge = new edge\_node\_t;  
graph->head\_data\[2\].first\_edge->node\_num = 3;  
graph->head\_data\[2\].first\_edge->next\_node = NULL;  
  
  
graph->head\_data\[3\].first\_edge = new edge\_node\_t;  
graph->head\_data\[3\].first\_edge->node\_num = 5;  
graph->head\_data\[3\].first\_edge->next\_node = NULL;  
  
  
graph->head\_data\[4\].first\_edge = new edge\_node\_t;  
graph->head\_data\[4\].first\_edge->node\_num = 1;  
graph->head\_data\[4\].first\_edge->next\_node =  
new edge\_node\_t;  
  
  
p\_edge = graph->head\_data\[4\].first\_edge->next\_node;  
p\_edge->node\_num = 3;  
p\_edge->next\_node = new edge\_node\_t;  
  
  
p\_edge = p\_edge->next\_node;  
p\_edge->node\_num = 5;  
p\_edge->next\_node = NULL;  
\}  
  
  
void depth\_first\_search(graph\_t\* graph, int start\_pos)  
\{  
stack<int> visit\_node;  
bool is\_visit\[MAX\_NUMBER\]; //访问标志数组  
for (int i = 0; i < MAX\_NUMBER; ++i)  
is\_visit\[i\] = false;  
  
  
cout<<graph->head\_data\[start\_pos\].data<<endl;  
is\_visit\[start\_pos\] = true;  
visit\_node.push(start\_pos); //将第一个元素压栈  
while (!visit\_node.empty())  
\{  
int num = visit\_node.top();  
edge\_node\_t\* next = graph->head\_data\[num\].first\_edge;  
for (; next != NULL; next = next->next\_node) //存在边，且该边的终点未被访问  
\{  
if (!is\_visit\[next->node\_num\])  
\{  
cout<<graph->head\_data\[next->node\_num\].data<<endl;  
is\_visit\[next->node\_num\] = true;  
visit\_node.push(next->node\_num);  
break;  
\}  
\}  
if (next == NULL) //以该结点为起点的所有终点访问完毕  
visit\_node.pop();  
\}  
\}  
  
  
int main(int argc, char\* argv\[\])  
\{  
graph\_t graph;  
create\_adjacency\_list(&graph);  
depth\_first\_search(&graph, 0);  
return 0;

[SouthEast]: /images/20220828/ab7e881b01e84419b1533773f7b2ffae.png