有权无向图的邻接表用代码如何表示

邻接表是一种常用的图存储方式，可以用链表实现。对于一个有权无向图，邻接表的代码表示如下：

#include <iostream>
#include <vector>

using namespace std;

// 定义边结构体
struct Edge {
    int to;     // 目标节点
    int weight; // 边权重
};

// 定义邻接表
vector<Edge> graph[N];

// 添加边
void addEdge(int u, int v, int w) {
    graph[u].push_back(Edge{v, w});
    graph[v].push_back(Edge{u, w});
}

int main() {
    return 0;
}

其中，`addEdge` 函数用于添加一条边，`graph` 是一个长度为 N 的向量，每个元素存储与该节点相邻的边列表。每个边结构体包含目标节点和边的权重。对于有向图，只需要在添加边时只添加一条即可。

相关问题

c语言实现1）由给定的顶点和边的信息构造图的邻接矩阵存储； （2）对该图进行深度优先搜索，输出搜索得到的结点序列； （3）以邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树。

好的，我来逐个回答你的问题。

1. 由给定的顶点和边的信息构造图的邻接矩阵存储

邻接矩阵是一种常用的图的存储方式，它可以用一个二维数组来表示图中各个节点之间的关系。邻接矩阵的实现过程如下：

1. 创建一个二维数组，数组大小为 n*n（n为顶点数）；
2. 初始化数组元素为0，表示各个顶点之间没有边相连；
3. 遍历每条边，将边的两个顶点在邻接矩阵中对应位置的元素设为1（或者边的权值，如果是有权图）。

下面是一个简单的示例代码：

#define MAX_VERTEX_NUM 100 //最大顶点数
typedef struct {
    char vexs[MAX_VERTEX_NUM]; //顶点表
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
    int vexnum, arcnum; //顶点数、边数
} MGraph;

void CreateMGraph(MGraph *G) {
    int i, j, k;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息：");
    for (i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->vexs[i]);
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = 0; //初始化邻接矩阵
        }
    }
    printf("请输入边的信息：\n");
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入第%d条边(Vi,Vj)的下标i和下标j，以及权值w：", k + 1);
        scanf("%d%d%d", &i, &j, &G->arcs[i][j]);
        G->arcs[j][i] = G->arcs[i][j]; //无向图，对称赋值
    }
}

2. 对该图进行深度优先搜索，输出搜索得到的结点序列

深度优先搜索（DFS）是一种经典的图遍历算法，其基本思想是从某个顶点开始，沿着一条路径一直走到底，直到不能再走为止，然后回退到上一个未访问的节点，继续走其它的路径，直到所有的节点都被访问过为止。DFS可以用递归或者栈来实现。

下面是一个简单的DFS代码实现，其中visit数组用于记录每个节点是否被访问过：

#define MAX_VERTEX_NUM 100 //最大顶点数
typedef struct {
    char vexs[MAX_VERTEX_NUM]; //顶点表
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
    int vexnum, arcnum; //顶点数、边数
} MGraph;

int visit[MAX_VERTEX_NUM]; //访问标志数组

void DFS(MGraph G, int v) {
    int i;
    visit[v] = 1; //标记该节点已访问
    printf("%c ", G.vexs[v]); //输出节点
    for (i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i] == 1 && visit[i] == 0) { //如果节点i与节点v相邻且未被访问
            DFS(G, i); //递归访问节点i
        }
    }
}

void DFSTraverse(MGraph G) {
    int v;
    for (v = 0; v < G.vexnum; v++) {
        visit[v] = 0; //初始化访问标记数组
    }
    for (v = 0; v < G.vexnum; v++) {
        if (visit[v] == 0) { //如果节点未被访问
            DFS(G, v); //从该节点开始DFS
        }
    }
}

3. 以邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树

最小生成树是一种重要的图论问题，它是指在一个带权无向图中，找出一棵包含所有顶点且边权值之和最小的生成树。克鲁斯卡尔算法是一种常用的解决最小生成树问题的贪心算法，其基本思想是按照边权值从小到大的顺序依次加入到生成树中，如果加入该边不会形成环，则将该边加入生成树中，否则舍弃该边。

下面是一个简单的克鲁斯卡尔算法的代码实现，其中使用了并查集来判断是否形成环：

#define MAX_VERTEX_NUM 100 //最大顶点数
#define MAX_EDGE_NUM 100 //最大边数
typedef struct {
    int u, v, w; //边的起点、终点、权重
} Edge;

typedef struct {
    char data; //节点信息
    struct EdgeNode *firstedge; //指向第一条依附该节点的边
} VertexNode;

typedef struct EdgeNode {
    int adjvex; //该边的邻接点编号
    int weight; //该边的权重
    struct EdgeNode *next; //指向下一条依附该节点的边
} EdgeNode;

typedef struct {
    VertexNode adjlist[MAX_VERTEX_NUM]; //邻接表
    int vexnum, edgenum; //顶点数、边数
} Graph;

int father[MAX_VERTEX_NUM]; //并查集数组

int Find(int x) { //查找x所在集合的代表元素
    if (x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y) { //合并两个集合
    int fx = Find(x);
    int fy = Find(y);
    if (fx != fy) {
        father[fx] = fy;
    }
}

void CreateGraph(Graph *G) {
    int i, j, k, w;
    Edge e[MAX_EDGE_NUM];
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->edgenum);
    printf("请输入顶点信息：");
    for (i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->adjlist[i].data);
        G->adjlist[i].firstedge = NULL;
        father[i] = i; //初始化并查集数组
    }
    printf("请输入边的信息：\n");
    for (k = 0; k < G->edgenum; k++) {
        printf("请输入第%d条边(Vi,Vj)的下标i和下标j，以及权值w：", k + 1);
        scanf("%d%d%d", &i, &j, &w);
        e[k].u = i;
        e[k].v = j;
        e[k].w = w;
    }
    //按照边权值从小到大排序
    for (i = 0; i < G->edgenum - 1; i++) {
        for (j = i + 1; j < G->edgenum; j++) {
            if (e[i].w > e[j].w) {
                Edge tmp = e[i];
                e[i] = e[j];
                e[j] = tmp;
            }
        }
    }
    //依次加入边，判断是否形成环
    for (k = 0; k < G->edgenum; k++) {
        i = Find(e[k].u);
        j = Find(e[k].v);
        if (i != j) { //不形成环
            printf("(%c,%c) ", G->adjlist[e[k].u].data, G->adjlist[e[k].v].data);
            Union(i, j); //合并两个集合
        }
    }
}