写出邻接矩阵存储下的该部分代码

如果用邻接矩阵表示图，第一个邻接点可以通过遍历第v行的元素来获取，下一个邻接点可以通过遍历第v行从w+1开始的元素来获取。代码如下：

class Graph:
    def __init__(self, V):
        self.V = V
        self.adj = [[0] * V for i in range(V)]
    
    def addEdge(self, v, w):
        self.adj[v][w] = 1
        self.adj[w][v] = 1
    
    def firstNeighbor(self, v):
        for i in range(self.V):
            if self.adj[v][i] == 1:
                return i
        return -1
    
    def nextNeighbor(self, v, w):
        for i in range(w+1, self.V):
            if self.adj[v][i] == 1:
                return i
        return -1

其中，V表示顶点数，adj是邻接矩阵，firstNeighbor方法返回顶点v的第一个邻接点，nextNeighbor方法返回v的邻接矩阵中，w之后的下一个邻接点。

相关问题

C++深度优先搜索算法如何根据邻接矩阵遍历出所有的路径的，请给出详细的原理解释和代码声明

在C++中，深度优先搜索（Depth-First Search, DFS）通常用来寻找图中的路径，包括从起点到终点的所有可能路径。对于邻接矩阵存储的图，DFS可以通过递归的方式进行遍历。

**原理解释**[^1]:
DFS的基本思想是从起始节点开始，沿着一条未访问过的边深入探索，直到找到终止节点或无法继续为止，然后回溯到之前的节点并尝试其他未走过的路径。对于每个节点，我们标记它已访问过，避免重复遍历。

**代码示例**[^2]:

#include <iostream>
#include <vector>
using namespace std;

// 标记邻接矩阵中节点的状态，未访问为0，已访问为1
#define UNVISITED 0
#define VISITED 1

// 深度优先遍历函数
void dfs(vector<vector<int>>& graph, vector<int>& visited, int node, vector<int>& path) {
    visited[node] = VISITED; // 标记当前节点已访问
    path.push_back(node); // 添加当前节点到路径

    // 遍历邻居节点
    for (int i = 0; i < graph[node].size(); ++i) {
        if (visited[graph[node][i]] == UNVISITED) { // 如果邻居节点未访问
            dfs(graph, visited, graph[node][i], path); // 递归调用dfs
        }
    }

    // 当遍历完所有邻居节点后，回溯并移除当前节点
    visited[node] = UNVISITED;
    path.pop_back();
}

// 主函数，用于测试
void findPaths(vector<vector<int>>& graph, int startNode) {
    vector<int> visited(graph.size(), UNVISITED);
    vector<int> path;
    dfs(graph, visited, startNode, path);

    // 输出路径
    for (int i = 0; i < path.size(); ++i) {
        cout << "Path: ";
        for (int j = path.size() - 1; j >= i; --j) {
            cout << path[j] << " -> ";
        }
        cout << startNode << endl;
    }
}

int main() {
    // 假设我们有一个邻接矩阵代表的图...
    // 注意：这里省略实际的邻接矩阵初始化部分

    findPaths(adjMatrix, startNode); // 调用findPaths函数，传入起始节点
    return 0;
}

在这个例子中，`adjMatrix`是一个二维数组，表示图的邻接矩阵。`startNode`是要从哪个节点开始遍历。`dfs`函数会找出以`startNode`为起点的所有路径。

用c语言写一个代码，可以运行的，需求如下 1.选择邻接矩阵或邻接表其中一种对图进行存储； 2.实现图的广度优先和深度优先两种遍历方法； 3.实现图的最小生成树算法，Prim或kruskal算法二者均需实现

好的，这是一个比较全面的图论算法，下面是 C 语言的实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTEX_NUM 20  // 图的最大顶点数

// 定义邻接矩阵结构体
typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值
    int num_vertex; // 顶点数
} MGraph;

// 定义邻接表结构体
typedef struct ArcNode {
    int adjvex; // 邻接点的下标
    int weight; // 权值
    struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;

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

typedef struct {
    AdjList adjList;
    int num_vertex; // 顶点数
} ALGraph;

// 初始化邻接矩阵
void initMGraph(MGraph *graph) {
    int i, j;
    printf("请输入顶点数：");
    scanf("%d", &graph->num_vertex);
    // 输入边的权值
    printf("请输入每条边的权值：\n");
    for (i = 0; i < graph->num_vertex; i++) {
        for (j = 0; j < graph->num_vertex; j++) {
            scanf("%d", &graph->arcs[i][j]);
        }
    }
}

// 初始化邻接表
void initALGraph(ALGraph *graph) {
    int i, j, k, weight;
    ArcNode *p;
    printf("请输入顶点数：");
    scanf("%d", &graph->num_vertex);
    // 输入顶点的数据
    printf("请输入每个顶点的数据：\n");
    for (i = 0; i < graph->num_vertex; i++) {
        graph->adjList[i].data = i;
        graph->adjList[i].first = NULL;
    }
    // 输入边的权值
    printf("请输入每条边的起点、终点和权值：\n");
    for (k = 0; k < graph->num_vertex; k++) {
        scanf("%d %d %d", &i, &j, &weight);
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->weight = weight;
        p->next = graph->adjList[i].first;
        graph->adjList[i].first = p;
        // 无向图需加上下面这部分
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->weight = weight;
        p->next = graph->adjList[j].first;
        graph->adjList[j].first = p;
    }
}

// 广度优先遍历
void BFS(MGraph graph, int start) {
    int i, j;
    bool visited[MAX_VERTEX_NUM] = {false}; // 记录每个顶点是否被访问过
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 定义队列，front 表示队头，rear 表示队尾
    printf("广度优先遍历结果：");
    printf("%d ", start);
    visited[start] = true;
    queue[rear++] = start; // 将起点入队
    while (front != rear) { // 队列不为空
        i = queue[front++]; // 出队
        for (j = 0; j < graph.num_vertex; j++) {
            if (graph.arcs[i][j] != 0 && visited[j] == false) { // 如果 i 和 j 有边，并且 j 没有被访问过
                printf("%d ", j);
                visited[j] = true;
                queue[rear++] = j; // 将 j 入队
            }
        }
    }
    printf("\n");
}

void BFS_AL(ALGraph graph, int start) {
    int i;
    bool visited[MAX_VERTEX_NUM] = {false}; // 记录每个顶点是否被访问过
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 定义队列，front 表示队头，rear 表示队尾
    ArcNode *p;
    printf("广度优先遍历结果：");
    printf("%d ", start);
    visited[start] = true;
    queue[rear++] = start; // 将起点入队
    while (front != rear) { // 队列不为空
        i = queue[front++]; // 出队
        p = graph.adjList[i].first;
        while (p != NULL) {
            if (visited[p->adjvex] == false) { // 如果 j 没有被访问过
                printf("%d ", p->adjvex);
                visited[p->adjvex] = true;
                queue[rear++] = p->adjvex; // 将 j 入队
            }
            p = p->next;
        }
    }
    printf("\n");
}

// 深度优先遍历
void DFS(MGraph graph, int start, bool visited[]) {
    int i;
    visited[start] = true;
    printf("%d ", start);
    for (i = 0; i < graph.num_vertex; i++) {
        if (graph.arcs[start][i] != 0 && visited[i] == false) { // 如果 start 和 i 有边，并且 i 没有被访问过
            DFS(graph, i, visited);
        }
    }
}

void DFS_AL(ALGraph graph, int start, bool visited[]) {
    ArcNode *p;
    visited[start] = true;
    printf("%d ", start);
    p = graph.adjList[start].first;
    while (p != NULL) {
        if (visited[p->adjvex] == false) { // 如果 j 没有被访问过
            DFS_AL(graph, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 深度优先遍历的入口函数
void DFSTraverse(MGraph graph) {
    int i;
    bool visited[MAX_VERTEX_NUM] = {false};
    printf("深度优先遍历结果：");
    for (i = 0; i < graph.num_vertex; i++) {
        if (visited[i] == false) {
            DFS(graph, i, visited);
        }
    }
    printf("\n");
}

void DFSTraverse_AL(ALGraph graph) {
    int i;
    bool visited[MAX_VERTEX_NUM] = {false};
    printf("深度优先遍历结果：");
    for (i = 0; i < graph.num_vertex; i++) {
        if (visited[i] == false) {
            DFS_AL(graph, i, visited);
        }
    }
    printf("\n");
}

// Prim 算法
void Prim(MGraph graph) {
    int i, j, k, min, sum = 0;
    int lowcost[MAX_VERTEX_NUM], closest[MAX_VERTEX_NUM];
    for (i = 1; i < graph.num_vertex; i++) {
        lowcost[i] = graph.arcs[0][i];
        closest[i] = 0;
    }
    for (i = 1; i < graph.num_vertex; i++) {
        min = 0x7fffffff;
        for (j = 1; j < graph.num_vertex; j++) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        printf("%d %d %d\n", closest[k], k, min);
        sum += min;
        lowcost[k] = 0;
        for (j = 1; j < graph.num_vertex; j++) {
            if (graph.arcs[k][j] != 0 && graph.arcs[k][j] < lowcost[j]) {
                lowcost[j] = graph.arcs[k][j];
                closest[j] = k;
            }
        }
    }
    printf("最小生成树的权值之和为：%d\n", sum);
}

// Kruskal 算法
typedef struct {
    int u, v; // 两个端点的下标
    int weight; // 权值
} Edge;

int cmp(const void *a, const void *b) { // 比较函数
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

int Find(int parent[], int f) { // 找父节点
    if (parent[f] == f) return f;
    else return parent[f] = Find(parent, parent[f]);
}

void Kruskal(MGraph graph) {
    int i, j, k, sum = 0;
    int parent[MAX_VERTEX_NUM];
    Edge edges[MAX_VERTEX_NUM];
    for (i = 0, k = 0; i < graph.num_vertex; i++) {
        for (j = i + 1; j < graph.num_vertex; j++) {
            if (graph.arcs[i][j] != 0) {
                edges[k].u = i;
                edges[k].v = j;
                edges[k].weight = graph.arcs[i][j];
                k++;
            }
        }
    }
    qsort(edges, k, sizeof(edges[0]), cmp); // 将边按权值从小到大排序
    for (i = 0; i < graph.num_vertex; i++) {
        parent[i] = i; // 初始化每个点的父节点为其本身
    }
    printf("最小生成树的边为：\n");
    for (i = 0; i < k; i++) {
        int faU = Find(parent, edges[i].u);
        int faV = Find(parent, edges[i].v);
        if (faU != faV) { // 如果 u 和 v 不在同一个连通块中
            printf("%d %d %d\n", edges[i].u, edges[i].v, edges[i].weight);
            sum += edges[i].weight;
            parent[faU] = faV; // 将 u 的父节点设为 v
        }
    }
    printf("最小生成树的权值之和为：%d\n", sum);
}

int main() {
    MGraph graph_M;
    ALGraph graph_AL;
    int choice;
    printf("请选择图的存储方式（1.邻接矩阵，2.邻接表）：");
    scanf("%d", &choice);
    if (choice == 1) {
        initMGraph(&graph_M);
        BFS(graph_M, 0);
        DFSTraverse(graph_M);
        Prim(graph_M);
        Kruskal(graph_M);
    } else {
        initALGraph(&graph_AL);
        BFS_AL(graph_AL, 0);
        DFSTraverse_AL(graph_AL);
        // Prim 和 Kruskal 算法同上
    }
    return 0;
}

注意：这只是一个简单的实现，如果需要在实际项目中使用，还需要考虑更多的情况，比如错误处理、异常情况处理等。