邻接表实现图的深度优先遍历和广度优先遍历c语言

邻接矩阵实现图的深度优先遍历和广度优先遍历： 深度优先遍历： 1. 定义一个栈，将起始节点入栈。 2. 当栈不为空时，取出栈顶节点，访问该节点，并将其未被访问的邻居节点入栈。 3. 标记已访问的节点。 4. 重复步骤2和3，直到栈为空。 邻接矩阵实现深度优先遍历的代码： ```c #define MAX_VERTEX_NUM 100 //最大顶点数 #define INFINITY 65535 //表示无穷大 typedef struct { int vexs[MAX_VERTEX_NUM]; //顶点表 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 } MGraph; int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过 void DFS(MGraph G, int v) { visited[v] = 1; //标记节点v已被访问 printf("%d ", G.vexs[v]); //访问节点v for (int i = ; i < G.vexnum; i++) { if (G.arcs[v][i] != INFINITY && !visited[i]) { //如果节点i是节点v的邻居且未被访问 DFS(G, i); //递归访问节点i } } } void DFSTraverse(MGraph G) { for (int i = ; i < G.vexnum; i++) { visited[i] = ; //初始化visited数组 } for (int i = ; i < G.vexnum; i++) { if (!visited[i]) { //如果节点i未被访问 DFS(G, i); //从节点i开始深度优先遍历 } } } ``` 广度优先遍历： 1. 定义一个队列，将起始节点入队。 2. 当队列不为空时，取出队首节点，访问该节点，并将其未被访问的邻居节点入队。 3. 标记已访问的节点。 4. 重复步骤2和3，直到队列为空。 邻接矩阵实现广度优先遍历的代码： ```c #define MAX_VERTEX_NUM 100 //最大顶点数 #define INFINITY 65535 //表示无穷大 typedef struct { int vexs[MAX_VERTEX_NUM]; //顶点表 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 } MGraph; int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过 void BFS(MGraph G, int v) { int queue[MAX_VERTEX_NUM]; //定义队列 int front = , rear = ; //队首和队尾指针 visited[v] = 1; //标记节点v已被访问 printf("%d ", G.vexs[v]); //访问节点v queue[rear++] = v; //将节点v入队 while (front != rear) { //队列不为空时 int w = queue[front++]; //取出队首节点w for (int i = ; i < G.vexnum; i++) { if (G.arcs[w][i] != INFINITY && !visited[i]) { //如果节点i是节点w的邻居且未被访问 visited[i] = 1; //标记节点i已被访问 printf("%d ", G.vexs[i]); //访问节点i queue[rear++] = i; //将节点i入队 } } } } void BFSTraverse(MGraph G) { for (int i = ; i < G.vexnum; i++) { visited[i] = ; //初始化visited数组 } for (int i = ; i < G.vexnum; i++) { if (!visited[i]) { //如果节点i未被访问 BFS(G, i); //从节点i开始广度优先遍历 } } } ``` 邻接表实现图的深度优先遍历和广度优先遍历： 深度优先遍历： 1. 定义一个栈，将起始节点入栈。 2. 当栈不为空时，取出栈顶节点，访问该节点，并将其未被访问的邻居节点入栈。 3. 标记已访问的节点。 4. 重复步骤2和3，直到栈为空。 邻接表实现深度优先遍历的代码： ```c #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, arcnum; //图的当前顶点数和弧数 } ALGraph; int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过 void DFS(ALGraph G, int v) { visited[v] = 1; //标记节点v已被访问 printf("%d ", G.vertices[v].data); //访问节点v ArcNode *p = G.vertices[v].firstarc; while (p) { if (!visited[p->adjvex]) { //如果节点p->adjvex未被访问 DFS(G, p->adjvex); //递归访问节点p->adjvex } p = p->nextarc; } } void DFSTraverse(ALGraph G) { for (int i = ; i < G.vexnum; i++) { visited[i] = ; //初始化visited数组 } for (int i = ; i < G.vexnum; i++) { if (!visited[i]) { //如果节点i未被访问 DFS(G, i); //从节点i开始深度优先遍历 } } } ``` 广度优先遍历： 1. 定义一个队列，将起始节点入队。 2. 当队列不为空时，取出队首节点，访问该节点，并将其未被访问的邻居节点入队。 3. 标记已访问的节点。 4. 重复步骤2和3，直到队列为空。 邻接表实现广度优先遍历的代码： ```c #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, arcnum; //图的当前顶点数和弧数 } ALGraph; int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过 void BFS(ALGraph G, int v) { int queue[MAX_VERTEX_NUM]; //定义队列 int front = , rear = ; //队首和队尾指针 visited[v] = 1; //标记节点v已被访问 printf("%d ", G.vertices[v].data); //访问节点v queue[rear++] = v; //将节点v入队 while (front != rear) { //队列不为空时 int w = queue[front++]; //取出队首节点w ArcNode *p = G.vertices[w].firstarc; while (p) { if (!visited[p->adjvex]) { //如果节点p->adjvex未被访问 visited[p->adjvex] = 1; //标记节点p->adjvex已被访问 printf("%d ", G.vertices[p->adjvex].data); //访问节点p->adjvex queue[rear++] = p->adjvex; //将节点p->adjvex入队 } p = p->nextarc; } } } void BFSTraverse(ALGraph G) { for (int i = ; i < G.vexnum; i++) { visited[i] = ; //初始化visited数组 } for (int i = ; i < G.vexnum; i++) { if (!visited[i]) { //如果节点i未被访问 BFS(G, i); //从节点i开始广度优先遍历 } } } ```

在C语言中，我们可以使用邻接表数据结构来表示图，并通过递归实现深度优先搜索（DFS）和广度优先搜索（BFS）。这里提供一个基本的代码示例： 首先，我们需要定义一个结构体来表示节点及其相邻节点： ```c typedef struct { int vertex; // 节点值 struct AdjListNode* adjList; // 邻接列表指针 } Node; // 邻接链表节点结构 typedef struct AdjListNode { int neighbor; struct AdjListNode* next; } AdjListNode; ``` 接着创建邻接表函数并填充图数据： ```c void createAdjacencyList(Node** nodes, int vertices, int edges[]) { for (int i = 0; i < vertices; ++i) { nodes[i].adjList = NULL; } for (int i = 0; i < edges.length(); i += 2) { Node* src = nodes[edges[i]]; Node* dst = nodes[edges[i+1]]; AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode)); newNode->neighbor = dst->vertex; newNode->next = src->adjList; src->adjList = newNode; } } ``` 深度优先搜索（DFS）代码： ```c void dfs(Node* node, int visited[], int source) { visited[node->vertex] = 1; printf("%d ", node->vertex); AdjListNode* temp = node->adjList; while (temp != NULL) { if (visited[temp->neighbor] == 0) { dfs(nodes + temp->neighbor, visited, source); } temp = temp->next; } } void dfsTraversal(Node** nodes, int vertices, int start) { int visited[vertices] = {0}; dfs(nodes + start, visited, start); } ``` 广度优先搜索（BFS）代码： ```c void bfs(Node* root, int visited[]) { queue_t* q = createQueue(); enqueue(q, root); while (!isEmpty(q)) { Node* node = dequeue(q); visited[node->vertex] = 1; printf("%d ", node->vertex); AdjListNode* adj = node->adjList; while (adj != NULL) { Node* neighbor = nodes + adj->neighbor; if (visited[neighbor->vertex] == 0) { enqueue(q, neighbor); } adj = adj->next; } } destroyQueue(q); } void bfsTraversal(Node** nodes, int vertices, int start) { int visited[vertices] = {0}; bfs(nodes + start, visited); } ``` 以上代码是一个简化的版本，实际使用时还需要处理内存分配、错误检查等细节。运行DFS或BFS时，你需要传入节点数组`nodes`、顶点数`vertices`以及起始节点`start`。