深度优先遍历详解-CSDN博客

本文链接：https://blog.csdn.net/aston5128/article/details/53870874

深度优先法遍历图

深度优先法听起来挺高大上的，不过千万别害怕，想象你在一个存在若干分叉路口的一条路上，你想走完所有的地方，当你遇到一个路口的时候，你随便选择一条路，然后遇到下一个路口，你继续随便选择一条，直到你到了目的地你才原路返回到次一级的路口并且选择另外一条路，重复这样的一种操作，直到遍历完所有的目的地。

//DFS
#include<iostream>
using namespace std;
const int max_n = 9;
bool visited[max_n];
struct node {
  int data;
  node *next;
};
node head_node[max_n];
void SetHeadNode() {
  for (int i = 1; i < max_n; ++i) {
    head_node[i].data = i;
    head_node[i].next = NULL;
  }
}
bool CanGraph(int x, int y) {
  if (x == y) {
    cout << "禁止自身循环！" << endl;
    return false;
  } else if (x >= 9 || y >= 9) {
    cout << "超出节点最大范围！" << endl;
    return false;
  } else {
    return true;
  }
}
void Graph(int x, int y) {
  if (!CanGraph(x, y)) return;
  node *p, *node_p = new node;
  if (node_p == NULL) {
    cout << "创建节点失败！" << endl;
    return;
  }
  node_p->data = y;
  node_p->next = NULL;
  for (p = &head_node[x]; p->next != NULL; p = p->next);
  p->next = node_p;
}
void PrintGraph() {
  for (int i = 1; i < max_n; ++i) {
    for (node *p = &head_node[i]; p != NULL; p = p->next) cout << p->data << "->";
    cout << "NULL" << endl;
  }
}
//深度优先遍历
void Dfs(int data) {
  visited[data] = true;
  cout << data << "->";
  for (node *p = head_node[data].next; p != NULL; p = p->next) {
    if (visited[p->data] == false) Dfs(p->data);
  }
}
int main() {
  int x, y;
  SetHeadNode();
  while (cin >> x >> y, x != -1 || y != -1) Graph(x, y);
  PrintGraph();
  Dfs(1);
  cout << "NULL" << endl;
}