图的邻接表非递归深度优先遍历C语言代码

回答1：
以下是图的邻接表非递归深度优先遍历的C语言代码：
#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 20 // 最大顶点数
#define MAX_STACK_SIZE 20 // 最大栈深度

typedef int VertexType; // 顶点的数据类型

// 定义边表结构体
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

// 定义顶点表结构体
typedef struct {
VertexType data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;

// 定义邻接表结构体
typedef struct {
VNode vertex[MAX_VERTEX_NUM]; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;

// 初始化邻接表
void init(ALGraph *G) {
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertex[i].firstarc = NULL;
}
}

// 添加边
void addEdge(ALGraph *G, int i, int j) {
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G->vertex[i].firstarc;
G->vertex[i].firstarc = p;
G->arcnum++;
}

// 非递归深度优先遍历
void DFS(ALGraph *G, int v) {
int visited[MAX_VERTEX_NUM];
int top = -1; // 栈顶指针
int stack[MAX_STACK_SIZE]; // 栈
ArcNode *p;
int i;

// 初始化visited数组
for (i = 0; i < MAX_VERTEX_NUM; i++) {
visited[i] = 0;
}

// 将起点v入栈并标记为已访问
stack[++top] = v;
visited[v] = 1;

// 遍历栈中的元素
while (top != -1) {
// 取出栈顶元素
i = stack[top--];
printf("%d ", G->vertex[i].data);

// 遍历邻接点
p = G->vertex[i].firstarc;
while (p != NULL) {
// 如果邻接点未被访问，则入栈并标记为已访问
if (visited[p->adjvex] == 0) {
stack[++top] = p->adjvex;
visited[p->adjvex] = 1;
}
p = p->nextarc;
}
}
}

int main() {
ALGraph G;
init(&amp;G);
addEdge(&amp;G, 0, 1);
addEdge(&amp;G, 0, 2);
addEdge(&amp;G, 1, 2);
addEdge(&amp;G, 2, 0);
addEdge(&amp;G, 2, 3);
addEdge(&amp;G, 3, 3);

printf("非递归深度优先遍历结果：");
DFS(&amp;G, 2);

return 0;
}
登录后复制
回答2：
下面是图的邻接表非递归深度优先遍历的C语言代码。首先，我们需要定义一个图的结构体，包含顶点数量和邻接表数组。
#include <stdio.h>
#include <stdlib.h>

// 定义图的结构体
typedef struct GraphNode{
int vertex;
struct GraphNode* next;
} GraphNode;

typedef struct Graph{
int vertices;
GraphNode** adjList;
} Graph;

// 创建图的函数
Graph* createGraph(int vertices){
Graph* graph = (Graph*) malloc(sizeof(Graph));
graph->vertices = vertices;

graph->adjList = (GraphNode**) malloc(vertices * sizeof(GraphNode*));
for(int i = 0; i < vertices; i++){
graph->adjList[i] = NULL;
}

return graph;
}

// 添加边的函数
void addEdge(Graph* graph, int src, int dest){
GraphNode* newNode = (GraphNode*) malloc(sizeof(GraphNode));
newNode->vertex = dest;
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;

// 若为无向图，则也需添加反向边
newNode = (GraphNode*) malloc(sizeof(GraphNode));
newNode->vertex = src;
newNode->next = graph->adjList[dest];
graph->adjList[dest] = newNode;
}

// 深度优先遍历函数
void DFS(Graph* graph, int startVertex){
int* visited = (int*) malloc(graph->vertices * sizeof(int));
for(int i = 0; i < graph->vertices; i++){
visited[i] = 0;
}

// 使用栈来实现非递归遍历
int stack[graph->vertices];
int top = -1;

stack[++top] = startVertex;
visited[startVertex] = 1;

while(top != -1){
int currentVertex = stack[top--];
printf("%d ", currentVertex);

GraphNode* temp = graph->adjList[currentVertex];
while(temp){
int adjVertex = temp->vertex;
if(!visited[adjVertex]){
stack[++top] = adjVertex;
visited[adjVertex] = 1;
}
temp = temp->next;
}
}
}

// 主函数
int main(){
int vertices = 6;
Graph* graph = createGraph(vertices);

addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);
addEdge(graph, 3, 5);

printf("深度优先遍历结果: ");
DFS(graph, 0);

return 0;
}
登录后复制
代码中的createGraph函数用于创建具有指定数量顶点的图。addEdge函数用于在两个顶点之间添加一条边。DFS函数用于执行深度优先遍历。在main函数中，我们创建了一个具有6个顶点的图，并添加了一些边。最后，我们调用DFS函数从第一个顶点开始进行深度优先遍历，并打印结果。
回答3：
深度优先遍历（Depth First Search，简称DFS）是图的一种遍历算法，其中邻接表是一种图的表示方式。下面是一个非递归的深度优先遍历的C语言代码：
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100

// 定义图的邻接表节点
typedef struct ArcNode {
int adjvex; // 邻接顶点的下标
struct ArcNode *nextarc; // 指向下一个邻接表节点的指针
} ArcNode;

// 定义图的顶点节点
typedef struct VNode {
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接表节点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 定义图
typedef struct {
AdjList vertices; // 顶点数组
int vexnum; // 顶点数
} Graph;

// 非递归DFS遍历
void DFS(Graph G, int v) {
int visited[MAX_VERTEX_NUM] = {0}; // 记录顶点是否被访问过的数组
ArcNode *stack[MAX_VERTEX_NUM]; // 用数组实现栈
int top = -1; // 栈顶指针
int i;

printf("DFS遍历顺序: ");
stack[++top] = &amp;(G.vertices[v]); // 将起始顶点的邻接表节点入栈
visited[v] = 1; // 标记起始顶点已经被访问
while (top != -1) { // 栈不为空时
ArcNode *p = stack[top--]; // 弹出栈顶元素
printf("%d ", p->data); // 访问该顶点
for (ArcNode *q = p->firstarc; q != NULL; q = q->nextarc) { // 遍历该顶点的邻接点
if (visited[q->adjvex] == 0) { // 若邻接点未被访问过
stack[++top] = &amp;(G.vertices[q->adjvex]); // 入栈
visited[q->adjvex] = 1; // 标记已访问
}
}
}
}

int main() {
Graph G;

G.vexnum = 4; // 假设有4个顶点
for (int i = 0; i < G.vexnum; i++) {
G.vertices[i].data = i; // 顶点数据
G.vertices[i].firstarc = NULL; // 初始化邻接表节点指针为空
}

// 添加边
ArcNode *arc0 = (ArcNode *)malloc(sizeof(ArcNode));
arc0->adjvex = 1;
arc0->nextarc = NULL;
G.vertices[0].firstarc = arc0;

ArcNode *arc1 = (ArcNode *)malloc(sizeof(ArcNode));
arc1->adjvex = 2;
arc1->nextarc = NULL;
G.vertices[1].firstarc = arc1;

ArcNode *arc2 = (ArcNode *)malloc(sizeof(ArcNode));
arc2->adjvex = 3;
arc2->nextarc = NULL;
G.vertices[2].firstarc = arc2;

// 顶点0的邻接点为1
// 顶点1的邻接点为2
// 顶点2的邻接点为3

DFS(G, 0);

return 0;
}
登录后复制
此代码采用邻接表的形式存储图，并使用非递归的深度优先遍历算法遍历图中的顶点和边。首先定义了邻接表节点和顶点节点的数据结构，然后定义了图的数据结构，包括顶点数组和顶点数。接下来，使用非递归的深度优先遍历算法实现了DFS()函数，在DFS()函数中，使用栈来记录待访问的节点，并使用visited数组来标记节点是否被访问过。最后，在主函数中创建了一个具有4个顶点的图，并添加了相应的边，然后调用DFS()函数进行遍历。