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

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

IT人知识库 原文地址:http://www.itpeo.net/12818/432986.html





贪吃蛇游戏C++命令行版实例代码

本文实例讲述了贪吃蛇游戏C++命令行版的实现代码,是非常经典的游戏。分享给大家供大家参考。具体实现方法如下: 众所周知,... ...

C语言连续子向量的最大和及时间度量实例

本文实例分析了C语言连续子向量的最大和及时间度量,分享给大家供大家参考之用。具体方法如下: #include <... ...

C语言二叉树的非递归遍历实例分析

本文以实例形式讲述了C语言实现二叉树的非递归遍历方法。是数据结构与算法设计中常用的技巧。分享给大家供大家参考。具体方法如... ...

C语言的递归思想实例分析

本文实例分析C语言的递归思想,分享给大家供大家参考之用。具体方法如下: 通俗点来说,递归就是自己调用自己。 递归的难点一... ...

C语言创建链表错误之通过指针参数申请动态内存实例分析

本文实例讲述了C语言创建链表中经典错误的通过指针参数申请动态内存,分享给大家供大家参考之用。具体实例如下: #inc... ...

C语言实现带头结点的链表的创建、查找、插入、删除操作

本文实例讲述了C语言实现带头结点的链表的创建、查找、插入、删除操作。是数据结构中链表部分的基础操作。分享给大家供大家参考... ...

C程序读取键盘码的方法

本文以一个简单实例讲述了C程序读取键盘码的方法,分享给大家供大家参考。具体分析如下: 一般来说,键盘码在底层开发中经常会... ...

C语言中char*和char[]用法区别分析

本文实例分析了C语言中char* 和 char []的区别。分享给大家供大家参考之用。具体分析如下: 一般来说,很多人会... ...

rfedfre

Cocos2d-x中CCEditBox文本输入框的使用实例

文本输入框这个东西相信大家不论做什么游戏总会用到吧,今天我们就来看看这个东西如何使用。文本输入框同样属于扩展库中的内容,... ...

rfedfre

Cocos2d-x中使用CCScrollView来实现关卡选择实例

类似关卡选择的这种功能游戏中经常看到,比如帮助场景,选择关卡,通过滑动的方式选择一些其他的东西等等。今天我们实现关卡的选... ...

C语言实现最大间隙问题实例

本文实例展示了C语言实现最大间隙问题的方法,对于算法的设计有一定的借鉴价值。分享给大家供大家参考。具体如下: 问题描述如... ...

C语言实现最长递增子序列问题的解决方法

本文实例展示了C语言实现最长递增子序列问题的解决方法。分享给大家供大家参考。具体方法如下: 问题描述: 给定一个序列,找... ...

C语言金币阵列问题解决方法

本文实例详细讲述了C语言实现金币阵列问题的解决方法,分享给大家供大家参考。具体方法如下: 问题描述: 有m*n(1 ≤ ... ...

C语言实现计算树的深度的方法

本文实例讲述了C语言实现计算树的深度的方法。是算法设计中常用的技巧。分享给大家供大家参考。具体方法如下: /* *... ...

C语言实现找出二叉树中某个值的所有路径的方法

本文实例讲述了C语言实现找出二叉树中某个值的所有路径的方法,是非常常用的一个实用算法技巧。分享给大家供大家参考。 具体实... ...

C语言实现输入一个字符串后打印出该字符串中字符的所有排列

本文实例讲述了C语言实现输入一个字符串后打印出该字符串中字符的所有排列的方法,属于数学里的排列问题。是一个很实用的算法技... ...

C语言实现输入一颗二元查找树并将该树转换为它的镜像

本文实例讲述了C语言实现输入一颗二元查找树并将该树转换为它的镜像的方法,分享给大家供大家参考。具体实现方法如下: 采用递... ...

C语言实现输出链表中倒数第k个节点

本文实例展示了C++实现输出链表中倒数第k个节点的方法,分享给大家供大家参考之用。 运行本文所述实例可实现输入一个单向链... ...

Mac OS X 10.8 中编译APUE(Unix环境高级编程)的源代码过程

最近在温习APUE(《unix环境高级编程》),以前都是在linux下搞,现在打算在自己机器弄下,于是google了下,... ...

rfedfre

C程序实现整数的素数和分解问题

本文以实例形式讲述了C程序实现整数的素数和分解问题,分享给大家供大家参考之用。具体方法如下: 要求:对于一个给定的整数,... ...