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

Alicia ·

更新时间:2024-11-13

· 798 次阅读

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

感性的朋友可以测试运行一下本文实例代码以加深印象，相信本文所述对大家C程序算法设计的有一定的借鉴价值。

您可能感兴趣的文章:C语言使用深度优先搜索算法解决迷宫问题(堆栈)C语言使用广度优先搜索算法解决迷宫问题（队列）C语言按关键字搜索文件夹中文件的方法C语言内嵌汇编API内存搜索引擎实例c语言全盘搜索指定文件的实例代码使用C语言实现模糊搜索功能

遍历 C语言深度优先搜索

1024 个赞