快捷導(dǎo)航

C語言實(shí)現(xiàn)圖的遍歷之深度優(yōu)先搜索實(shí)例

更新時(shí)間：2014年09月16日 14:50:28 投稿：shichen2014

這篇文章主要介紹了C語言實(shí)現(xiàn)圖的遍歷之深度優(yōu)先搜索實(shí)例,采用不同的方法實(shí)現(xiàn)了深度優(yōu)先搜索算法,有不錯(cuò)的借鑒價(jià)值,需要的朋友可以參考下

DFS(Depth-First-Search)深度優(yōu)先搜索算法是圖的遍歷算法中非常常見的一類算法。分享給大家供大家參考。具體方法如下：

#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();
 }
}

感性的朋友可以測(cè)試運(yùn)行一下本文實(shí)例代碼以加深印象，相信本文所述對(duì)大家C程序算法設(shè)計(jì)的有一定的借鑒價(jià)值。

您可能感興趣的文章: