C语言实现图的遍历之深度优先搜索实例_C/C++

DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法。分享给大家供大家参考。具体方法如下：

				?

									#include <iostream>

									#include <algorithm>

									#include <iterator>

									using namespace std;  

									#define MAX_VERTEX_NUM 10

									struct Node

									{

									 int adjvex;

									 struct Node *next;

									 int info;

									};

									typedef struct VNode

									{

									 char data;

									 Node *first;

									}VNode, AdjList[MAX_VERTEX_NUM];

									struct Graph 

									{

									 AdjList vertices;

									 int vexnum, arcnum;

									};

									int visited[MAX_VERTEX_NUM];

									int locateVex(Graph G, char u)

									{

									 int i;

									 for (i = 0; i < G.vexnum; i++)

									 {

									 if (u == G.vertices[i].data)

									  return i;

									 }

									 if (i == G.vexnum)

									 {

									 printf("Error u!\n");

									 exit(1);

									 }

									 return 0;

									}

									void createGraph(Graph &G)

									{

									 int i, j, k, w;

									 char v1, v2, enter;

									 Node *p;

									 printf("input vexnum & arcnum:\n");

									 scanf("%d", &G.vexnum);

									 scanf("%d", &G.arcnum);

									 printf("input vertices:\n");

									 for (i = 0; i < G.vexnum; i++)

									 {

									 scanf("%c%c", &enter, &G.vertices[i].data);

									 G.vertices[i].first = NULL;

									 }

									 printf("input Arcs(v1, v2, w):\n");

									 for (k = 0; k < G.arcnum; k++)

									 {

									 scanf("%c%c", &enter, &v1);

									 scanf("%c%c", &enter, &v2);

									 scanf("%d", &w);

									 i = locateVex(G, v1);

									 j = locateVex(G, v2);

									 p = (Node *)malloc(sizeof(Node));

									 p->adjvex = j;

									 p->info = w;

									 p->next = G.vertices[i].first;

									 G.vertices[i].first = p;

									 }

									}

									void DFS(Graph &G, int v)

									{

									 Node *p;

									 printf("%c", G.vertices[v].data);

									 visited[v] = 1;

									 p = G.vertices[v].first;

									 while (p)

									 {

									 if (!visited[p->adjvex])

									  DFS(G, p->adjvex);

									 p = p->next;

									 }

									}

									void DFSTranverse(Graph &G)

									{

									 for (int v = 0; v < G.vexnum; v++)

									 visited[v] = 0;

									 for (int v = 0; v < G.vexnum; v++)

									 {

									 if (!visited[v])

									  DFS(G, v);

									 }

									}

									int main()

									{

									 Graph G;

									 createGraph(G);

									 DFSTranverse(G);

									}

再换一种方式来写DFS。具体代码如下：

				?

									#include <iostream>

									#include <string>

									using namespace std;

									#define MAXLEN 10

									struct Node

									{

									 int data;

									 Node *next;

									};

									struct Link

									{

									 int count;

									 string name;

									 Node *head;

									};

									struct Graph

									{

									 Link link[MAXLEN];

									 int vexnum;

									 int arcnum;

									};

									int findIndex(Graph &G, string name)

									{

									 int index = -1;

									 for (int i = 0; i < G.vexnum; i++)

									 {

									 if (G.link[i].name == name)

									 {

									  index = i;

									  break;

									 }

									 }

									 if (index == -1)

									 cout << "error" << endl;

									 return index;

									}

									void constructGraph(Graph &G)

									{

									 cout << "construct graph yooo" << endl;

									 cout << "enter vexnum" << endl;

									 cin >> G.vexnum;

									 string array[] = {"v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8"};

									 const int size = sizeof array / sizeof *array;

									 for (int i = 0; i < G.vexnum; i++)

									 {

									 G.link[i].name = array[i];

									 G.link[i].head = NULL;

									 }

									 string leftName;

									 string rightName;

									 cout << "enter a pair" << endl;

									 cin >> leftName >> rightName;

									 while (leftName != "end" && rightName != "end")

									 {

									 int leftIndex = findIndex(G, leftName);

									 int rightIndex = findIndex(G, rightName);

									 Node *node = new Node;

									 node->data = rightIndex;

									 node->next = NULL;

									 node->next = G.link[leftIndex].head;

									 G.link[leftIndex].head = node;

									 cout << "enter a pair" << endl;

									 cin >> leftName >> rightName;

									 }

									}

									bool flag[MAXLEN];

									void DFSTranverse(Graph &G, int num)

									{

									 cout << G.link[num].name << " ";

									 flag[num] = true;

									 Node *head = G.link[num].head;

									 while (head != NULL)

									 {

									 int index = head->data;

									 if (!flag[index])

									  DFSTranverse(G, index);

									 head = head->next;

									 }

									}

									void main()

									{

									 Graph G;

									 constructGraph(G);

									 for (int i = 0; i < MAXLEN; i++)

									 flag[i] = false;

									 DFSTranverse(G, 0);

									}

DFS的迭代遍历算法如下：

				?

									void DFS(Graph &G)

									{

									 stack<int> istack;

									 istack.push(0);

									 cout << G.link[0].name << " ";

									 flag[0] = true;

									 while (!istack.empty())

									 {

									 int index = istack.top();

									 Node *head = G.link[index].head;

									 while (head != NULL && flag[head->data] == true)

									  head = head->next;

									 if (head != NULL)

									 {

									  index = head->data;

									  if (!flag[index])

									  {

									  cout << G.link[index].name << " ";

									  flag[index] = true;

									  istack.push(index);

									  }

									 }

									 else

									  istack.pop();

									 }

									}