DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法。分享给大家供大家参考。具体方法如下：
#include
#include
#include
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
#include
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 next = NULL;
node->next = G.link[leftIndex].head;
G.link[leftIndex].head = node;
cout leftName >> rightName;
}
}
bool flag[MAXLEN];
void DFSTranverse(Graph &G, int num)
{
cout 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 istack;
istack.push(0);
cout next;
if (head != NULL)
{
index = head->data;
if (!flag[index])
{
cout