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

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

相关问题

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

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

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

用DEVC++写一个程序，依次从有向图中的每个顶点深度优先搜索遍历操作；邻接表作为存储结构。算法思想： (1) 定义图的链式存储结构； (2) 创建有向图，采用邻接表表示（调用CreateUDG函数实现），具体实现如下： 输入图的顶点数和边数； 依次输入顶点的信息存入顶点表中，每个表头结点的指针域初始化为NULL； 构造邻接表；（需调用LocateVex函数获取顶点在顶点表中的下标） (3) 依次从每个顶点进行深度优先搜索，并输出访问序列（调用DFSTraverse函数实现；另需调用相关函数实现获取第一个和下一个邻接点的操作）。 注意： 顶点数据仅为1个数字或1个字符； 顶点表数组下标从0开始； 在每个顶点的边表中插入结点时，确保此顶点的各邻接点域的值从大到小排序。 输入说明： 第一行输入图的顶点数n和边数m； 第二行依次输入n个顶点的数据； 接下来m行的每行输入一条边的信息。 输出说明： 输出n行，每行输出从第i(0≤i＜n)个顶点深度优先搜索的访问序列，序列中的连通分量用{}括起来，无空格间隔，{}为英文半角的符号。

很高兴为您提供代码实现，以下是DEVC++实现的代码：

#include <iostream>
using namespace std;

#define MAX_VERTEX_NUM 20

typedef char VertexType;
typedef struct ArcNode{
    int adjvex;                 //邻接点在顶点表中的位置
    struct ArcNode *nextarc;    //指向下一个邻接点的指针
}ArcNode;

typedef struct VNode{
    VertexType data;            //顶点信息
    ArcNode *firstarc;          //指向第一个邻接点的指针
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList vertices;           //邻接表
    int vexnum, arcnum;         //图的当前顶点数和边数
}ALGraph;

int LocateVex(ALGraph G, VertexType x){
    for(int i=0; i<G.vexnum; i++){
        if(G.vertices[i].data == x){
            return i;
        }
    }
    return -1;
}

void CreateALGraph(ALGraph &G){
    cout << "请输入顶点数和边数：" << endl;
    cin >> G.vexnum >> G.arcnum;
    cout << "请输入" << G.vexnum << "个顶点的信息：" << endl;
    for(int i=0; i<G.vexnum; i++){
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc = NULL;
    }
    for(int k=0; k<G.arcnum; k++){
        VertexType v1, v2;
        cout << "请输入一条边依附的两个顶点：" << endl;
        cin >> v1 >> v2;
        int i = LocateVex(G, v1);
        int j = LocateVex(G, v2);
        if(i==-1 || j==-1){
            cout << "输入顶点信息有误，请重新输入！" << endl;
            k--;
        }else{
            ArcNode *p = new ArcNode;
            p->adjvex = j;
            p->nextarc = G.vertices[i].firstarc;
            G.vertices[i].firstarc = p;
        }
    }
}

int visited[MAX_VERTEX_NUM];    //全局数组，记录顶点的访问情况

void DFS(ALGraph G, int v){
    visited[v] = 1;
    cout << G.vertices[v].data;
    ArcNode *p = G.vertices[v].firstarc;
    while(p != NULL){
        int w = p->adjvex;
        if(visited[w] == 0){
            DFS(G, w);
        }
        p = p->nextarc;
    }
}

void DFSTraverse(ALGraph G){
    cout << "深度优先搜索遍历序列：" << endl;
    for(int i=0; i<G.vexnum; i++){
        visited[i] = 0;
    }
    for(int i=0; i<G.vexnum; i++){
        if(visited[i] == 0){
            cout << "{";
            DFS(G, i);
            cout << "}" << endl;
        }
    }
}

int main(){
    ALGraph G;
    CreateALGraph(G);
    DFSTraverse(G);
    return 0;
}

其中，CreateALGraph函数实现了有向图的邻接表存储结构的构造；LocateVex函数用于获取顶点在顶点表中的下标；DFS函数实现了深度优先搜索遍历操作；DFSTraverse函数依次从每个顶点进行深度优先搜索，并输出访问序列，其中使用visited数组记录顶点的访问情况。最后，在主函数中调用CreateALGraph函数和DFSTraverse函数完成程序的执行。