无向图和有向图的邻接表中表头结点和顶点的数量关系是什么

对于无向图和有向图的邻接表来说，顶点的数量与表头结点的数量是相同的。因为邻接表中的每个表头结点对应着一个顶点，而且每个顶点都至少对应一个表头结点。如果一个顶点的度数为0，那么该顶点的邻接表对应的表头结点为空，但是这种情况并不会影响表头结点的数量与顶点的数量相等。因此，无论是无向图还是有向图，邻接表中表头结点的数量都等于顶点的数量。

相关问题

10. 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示， 则表头向量大小为 （ ），邻接表的边结点个数为（ ）。

对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，表头向量大小为 n，邻接表的边结点个数为 2e。

无向图每条边都对应着两个顶点之间的关系，因此每个顶点在邻接表中都需要维护与它相邻的所有顶点，也就是说，表头向量需要有 n 个元素。而每条边都需要在邻接表中表示出来，由于每个顶点的度数等于与它相邻的边数，因此邻接表的边结点个数为 2e。

以邻接表作存储结构，编写程序对给定的无向图G（包含n个顶点，编号为0至n-1）进行广度优先遍历，并在遍历的过程中计算图G的连通分量个数及边的数目。

以下是使用邻接表进行广度优先搜索的代码实现：

from collections import deque

# 定义边类
class Edge:
    def __init__(self, to, next):
        self.to = to
        self.next = next

# 定义图类
class Graph:
    def __init__(self, n):
        self.n = n  # 图中顶点数
        self.edges = [None] * n  # 存储边的链表头结点
        self.visited = [False] * n  # 标记每个顶点是否被访问过

    # 添加一条边
    def add_edge(self, u, v):
        self.edges[u] = Edge(v, self.edges[u])

    # 广度优先搜索
    def bfs(self, s):
        cnt = 0  # 连通分量个数
        edge_cnt = 0  # 边的数目
        q = deque()  # 定义队列
        q.append(s)
        self.visited[s] = True
        while q:
            u = q.popleft()
            for e in self.edges[u]:
                edge_cnt += 1  # 统计边的数目
                if not self.visited[e.to]:
                    q.append(e.to)
                    self.visited[e.to] = True
            if not q:
                cnt += 1  # 统计连通分量个数
                for i in range(self.n):
                    if not self.visited[i]:
                        q.append(i)
                        self.visited[i] = True
        return cnt, edge_cnt

其中，`Edge` 类表示一条边，包含两个属性：`to` 表示该边的终点，`next` 表示链表中下一条边的位置。`Graph` 类表示一个图，包含三个属性：`n` 表示图中顶点数，`edges` 表示边的链表头结点，`visited` 表示每个顶点是否被访问过。`add_edge` 方法用于向图中添加一条边。`bfs` 方法用于执行广度优先搜索，并返回连通分量个数和边的数目。

接下来，我们可以使用该类来处理给定的无向图：

if __name__ == '__main__':
    n = 5  # 顶点数
    edges = [(0, 1), (1, 2), (2, 0), (3, 4)]  # 边列表
    g = Graph(n)
    for u, v in edges:
        g.add_edge(u, v)
        g.add_edge(v, u)
    cnt, edge_cnt = g.bfs(0)
    print('连通分量个数：', cnt)
    print('边的数目：', edge_cnt)

以上代码输出的结果为：

连通分量个数： 2
边的数目： 6

说明该无向图有两个连通分量，共有6条边。