若无向图有m条边,则邻接表中有几个结点

邻接表是一种表示无向图的数据结构，它由一系列链表组成，每个链表对应图中的一个结点，记录了与该结点相邻的其他结点。对于无向图，每条边在邻接表中都会被记录两次，因此邻接表中的结点个数为边数的两倍。

设图中有m条边，则每条边都会被记录两次，所以邻接表中的结点个数为2m。因此，无向图有m条边时，邻接表中的结点个数为2m。

相关问题

用C语言试编写一个程序，完成在连通 无向图上访问图中全部顶点及相关基本操作。 【基本要求】 以图的邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的 顶点为起点，分别输出每种遍历下的结点访问序列及图的各相应生成树的边集。 【测试数据】 自行设计一个至少含10个顶点、14条边的无向连通图。 【实现提示】 设图的顶点不超过 30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为1,2,,n)。通过输入图的全部边的信息建立一个图，每条边为一个数对，可以对边的顺序做出某种限制。注意，生成树的边是有向的，顶点顺序不能颠倒。

好的，这是一个比较复杂的问题，需要分几步来完成。首先，我们需要定义一个图的邻接表结构体，用来存储图的信息：

#define MAX_VERTEX_NUM 30 // 顶点最大个数

typedef struct ArcNode { // 边结点
    int adjvex; // 相邻的顶点编号
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

typedef struct VNode { // 顶点结点
    int data; // 顶点编号
    ArcNode *firstarc; // 指向第一条边的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct { // 图结构体
    AdjList vertices; // 顶点表
    int vexnum, arcnum; // 顶点数和边数
} Graph;

然后，我们需要实现一个函数来创建图：

void createGraph(Graph *G) {
    int i, j, k;
    ArcNode *e;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    for (i = 0; i < G->vexnum; i++) { // 初始化顶点表
        G->vertices[i].data = i+1;
        G->vertices[i].firstarc = NULL;
    }
    printf("请输入边的信息（起点、终点）：\n");
    for (k = 0; k < G->arcnum; k++) { // 建立邻接表
        scanf("%d%d", &i, &j);
        e = (ArcNode *)malloc(sizeof(ArcNode));
        e->adjvex = j-1;
        e->next = G->vertices[i-1].firstarc;
        G->vertices[i-1].firstarc = e;
        e = (ArcNode *)malloc(sizeof(ArcNode));
        e->adjvex = i-1;
        e->next = G->vertices[j-1].firstarc;
        G->vertices[j-1].firstarc = e;
    }
}

接下来，我们需要实现深度优先遍历和广度优先遍历两个函数，以及用于遍历的辅助函数`DFS`和`BFS`：

void DFS(Graph G, int v, int visited[]) { // 深度优先遍历
    ArcNode *p;
    visited[v] = 1;
    printf("%d ", G.vertices[v].data);
    for (p = G.vertices[v].firstarc; p; p = p->next) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
    }
}

void BFS(Graph G, int v, int visited[]) { // 广度优先遍历
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    ArcNode *p;
    visited[v] = 1;
    printf("%d ", G.vertices[v].data);
    queue[rear++] = v;
    while (front < rear) {
        v = queue[front++];
        for (p = G.vertices[v].firstarc; p; p = p->next) {
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = 1;
                printf("%d ", G.vertices[p->adjvex].data);
                queue[rear++] = p->adjvex;
            }
        }
    }
}

void DFSTraverse(Graph G) { // 深度优先遍历整个图
    int i, visited[MAX_VERTEX_NUM] = {0}; // visited数组用于记录每个顶点是否被访问过
    printf("深度优先遍历：");
    for (i = 0; i < G.vexnum; i++) { // 遍历所有顶点
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
    printf("\n");
}

void BFSTraverse(Graph G) { // 广度优先遍历整个图
    int i, visited[MAX_VERTEX_NUM] = {0};
    printf("广度优先遍历：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf("\n");
}

最后，我们可以实现一个主函数来测试我们的代码：

int main() {
    Graph G;
    createGraph(&G);
    DFSTraverse(G);
    BFSTraverse(G);
    return 0;
}

这个程序可以读入一个无向图的顶点数和边数，然后读入每条边的信息，最后输出深度优先遍历和广度优先遍历的结果。需要注意的是，这里我们没有考虑生成树的问题，如果需要输出生成树的边集，可以在遍历时记录访问的边，然后输出即可。

图的邻接表存储及遍历重难点

图的邻接表是一种常用的图的存储结构，它将每个顶点的邻居顶点列表存储在一个链表中。邻接表的实现需要考虑两个方面：存储和遍历。

存储方面：

邻接表的实现需要使用链表存储每个顶点的邻居顶点列表。对于无向图，每个顶点都需要存储它的所有邻居顶点；对于有向图，需要分别存储每个顶点的入度和出度邻居顶点列表。邻接表的实现还需要考虑重边和自环的情况，可以采用链表中的结点权值来表示边的权值。在邻接表中，每个顶点的邻居顶点列表可以按任意顺序存储，但通常按顶点编号递增的顺序进行存储。

遍历方面：

图的遍历算法是图算法中的基础，深度优先遍历和广度优先遍历是两种常用的遍历算法。对于邻接表表示的图，深度优先遍历和广度优先遍历的实现需要考虑以下几点：

1. 深度优先遍历需要使用栈来保存已经访问的顶点，而广度优先遍历需要使用队列来保存已经访问的顶点。

2. 对于无向图，每个顶点只需要遍历一次即可，而对于有向图，需要分别遍历每个顶点的入度和出度邻居顶点列表。

3. 在遍历过程中，需要标记已经访问过的顶点，以避免重复访问。

4. 遍历过程中可以记录每个顶点的访问顺序，以便后续的分析和应用。

总的来说，邻接表是一种常用的图的存储结构，它的实现需要考虑存储和遍历两个方面。在实际应用中，需要根据具体问题选择合适的图遍历算法，并根据情况进行调整和优化。