选存储结构,输入含n个顶点(用字符表示顶点)和e 条边的图g

对于含有n个顶点和e条边的图g，我们可以选择不同的存储结构来表示这个图。

一种常用的存储结构是邻接矩阵。邻接矩阵是一个n*n的矩阵，其中的每个元素表示图中两个顶点之间是否存在一条边。如果元素的值为1，则表示存在一条边；如果元素的值为0，则表示不存在一条边。通过这种方式，我们可以快速地判断任意两个顶点之间是否存在边，但是对于稀疏图来说会占用较多的空间。

另一种存储结构是邻接表。邻接表是由n个链表组成的数组，每个链表存储与该顶点相邻的顶点列表。通过这种方式，我们可以方便地遍历任意一个顶点的所有邻接顶点，但是判断任意两个顶点之间是否存在边的时间复杂度较高。

除了邻接矩阵和邻接表之外，我们还可以使用其他存储结构，如邻接多重表、边集数组等。邻接多重表在有向图和无向图的情况下的存储方式不同，一种常用的方式是使用双向链表来存储顶点和边。

在选择存储结构时，我们需要考虑图的规模、图的密度以及对各种操作的需求。如果图较小且稠密，邻接矩阵是一个不错的选择；如果图较大且稀疏，邻接表可能更为合适。此外，我们还可以根据具体的应用场景来选择最适合的存储结构。

相关问题

图的基本操作与实现，要求用邻接表存储结构，实现对图11-3所示的有向带权网络G的操作。 ⑴ 输入含n（1≤n≤100）个顶点（用字符表示顶点）和e条边； ⑵ 求每个顶点的出度和入度，输出结果； ⑶ 指定任意顶点x为初始顶点，对图G作DFS遍历，输出DFS顶点序列； ⑷ 指定任意顶点x为初始顶点，对图G作BFS遍历，输出BFS顶点序列； ⑸ 输入顶点x，查找图G：若存在含x的顶点，则删除该结点及与之相关联的边，并作DFS遍历；否则输出信息“无x”； ⑹ 判断图G是否是连通图，输出信息“YES”/“NO”； ⑺ 根据图G的邻接表创建图G的邻接矩阵，即复制图G。 ⑻ 找出该图的一棵最小生成树。

邻接表存储结构定义：

typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边权值类型

// 边表结点
typedef struct EdgeNode {
    int adjvex; // 邻接点编号
    EdgeType weight; // 边权值
    struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;

// 顶点表结点
typedef struct VertexNode {
    VertexType data; // 顶点数据
    EdgeNode *firstEdge; // 指向第一个邻接点
} VertexNode, AdjList[MAXVEX];

// 邻接表存储结构
typedef struct {
    AdjList adjList; // 邻接表
    int numVertexes, numEdges; // 顶点数和边数
} GraphAdjList;

辅助函数：

// 返回顶点在邻接表中的位置
int LocateVex(GraphAdjList G, VertexType v) {
    for (int i = 0; i < G.numVertexes; i++) {
        if (G.adjList[i].data == v) {
            return i;
        }
    }
    return -1;
}

// 深度优先搜索遍历
void DFS(GraphAdjList G, int i, bool visited[]) {
    visited[i] = true;
    printf("%c", G.adjList[i].data);
    EdgeNode *p = G.adjList[i].firstEdge;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 广度优先搜索遍历
void BFS(GraphAdjList G, int i, bool visited[]) {
    int queue[MAXVEX], front = 0, rear = 0;
    printf("%c", G.adjList[i].data);
    visited[i] = true;
    queue[rear++] = i;
    while (front != rear) {
        int j = queue[front++];
        EdgeNode *p = G.adjList[j].firstEdge;
        while (p) {
            if (!visited[p->adjvex]) {
                printf("%c", G.adjList[p->adjvex].data);
                visited[p->adjvex] = true;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

// 删除结点及其相关联的边
void DeleteVex(GraphAdjList *G, VertexType v) {
    int i = LocateVex(*G, v);
    if (i == -1) {
        printf("无%c\n", v);
        return;
    }
    EdgeNode *p = G->adjList[i].firstEdge;
    while (p) {
        int j = p->adjvex;
        EdgeNode *q = G->adjList[j].firstEdge, *r = NULL;
        while (q) {
            if (q->adjvex == i) {
                if (r == NULL) {
                    G->adjList[j].firstEdge = q->next;
                } else {
                    r->next = q->next;
                }
                free(q);
                G->numEdges--;
                break;
            }
            r = q;
            q = q->next;
        }
        p = p->next;
    }
    G->numVertexes--;
    for (int j = i; j < G->numVertexes; j++) {
        G->adjList[j] = G->adjList[j+1];
    }
    for (int j = 0; j < G->numVertexes; j++) {
        EdgeNode *p = G->adjList[j].firstEdge;
        while (p) {
            if (p->adjvex > i) {
                p->adjvex--;
            }
            p = p->next;
        }
    }
}

// 连通性检查
bool DFS2(GraphAdjList G, int i, bool visited[]) {
    visited[i] = true;
    EdgeNode *p = G.adjList[i].firstEdge;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS2(G, p->adjvex, visited);
        }
        p = p->next;
    }
    return true;
}

bool IsConnected(GraphAdjList G) {
    bool visited[MAXVEX] = { false };
    DFS2(G, 0, visited);
    for (int i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}

// 边的最小堆
typedef struct {
    int u, v; // 边的两个顶点
    EdgeType w; // 边的权值
} Edge;

typedef struct {
    Edge data[MAXEDGE];
    int size;
} MinHeap;

void Insert(MinHeap *H, Edge e) {
    H->data[++H->size] = e;
    int i = H->size;
    while (i > 1 && H->data[i].w < H->data[i/2].w) {
        Edge tmp = H->data[i];
        H->data[i] = H->data[i/2];
        H->data[i/2] = tmp;
        i /= 2;
    }
}

Edge Delete(MinHeap *H) {
    Edge ret = H->data[1];
    H->data[1] = H->data[H->size--];
    int i = 1;
    while (i*2 <= H->size) {
        int child = i*2;
        if (child < H->size && H->data[child+1].w < H->data[child].w) {
            child++;
        }
        if (H->data[child].w < H->data[i].w) {
            Edge tmp = H->data[child];
            H->data[child] = H->data[i];
            H->data[i] = tmp;
            i = child;
        } else {
            break;
        }
    }
    return ret;
}

操作实现：

⑴ 输入含n（1≤n≤100）个顶点（用字符表示顶点）和e条边；

void CreateGraph(GraphAdjList *G) {
    printf("输入顶点数和边数：");
    scanf("%d%d", &G->numVertexes, &G->numEdges);
    getchar(); // 读取多余的换行符
    printf("输入顶点：");
    for (int i = 0; i < G->numVertexes; i++) {
        scanf("%c", &G->adjList[i].data);
        G->adjList[i].firstEdge = NULL;
    }
    getchar(); // 读取多余的换行符
    printf("输入边（<vi,vj,w>）：");
    for (int k = 0; k < G->numEdges; k++) {
        VertexType vi, vj;
        EdgeType w;
        scanf("<%c,%c,%d>", &vi, &vj, &w);
        getchar(); // 读取多余的换行符
        int i = LocateVex(*G, vi), j = LocateVex(*G, vj);
        EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->weight = w;
        e->next = G->adjList[i].firstEdge;
        G->adjList[i].firstEdge = e;
    }
}

⑵ 求每个顶点的出度和入度，输出结果；

void PrintInAndOutDegree(GraphAdjList G) {
    int inDegree[MAXVEX] = { 0 }, outDegree[MAXVEX] = { 0 };
    for (int i = 0; i < G.numVertexes; i++) {
        EdgeNode *p = G.adjList[i].firstEdge;
        while (p) {
            outDegree[i]++;
            inDegree[p->adjvex]++;
            p = p->next;
        }
    }
    printf("顶点 出度 入度\n");
    for (int i = 0; i < G.numVertexes; i++) {
        printf("%c %d %d\n", G.adjList[i].data, outDegree[i], inDegree[i]);
    }
}

⑶ 指定任意顶点x为初始顶点，对图G作DFS遍历，输出DFS顶点序列；

void DFSTraverse(GraphAdjList G, VertexType v) {
    bool visited[MAXVEX] = { false };
    int i = LocateVex(G, v);
    DFS(G, i, visited);
}

⑷ 指定任意顶点x为初始顶点，对图G作BFS遍历，输出BFS顶点序列；

void BFSTraverse(GraphAdjList G, VertexType v) {
    bool visited[MAXVEX] = { false };
    int i = LocateVex(G, v);
    BFS(G, i, visited);
}

⑸ 输入顶点x，查找图G：若存在含x的顶点，则删除该结点及与之相关联的边，并作DFS遍历；否则输出信息“无x”；

void DeleteVexAndDFS(GraphAdjList *G, VertexType v) {
    DeleteVex(G, v);
    bool visited[MAXVEX] = { false };
    if (LocateVex(*G, v) != -1) {
        printf("DFS遍历序列：");
        int i = 0;
        while (visited[i]) i++;
        DFS(*G, i, visited);
    }
}

⑹ 判断图G是否是连通图，输出信息“YES”/“NO”；

void PrintConnected(GraphAdjList G) {
    if (IsConnected(G)) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
}

⑺ 根据图G的邻接表创建图G的邻接矩阵，即复制图G。

void CreateMGraph(GraphAdjList G, EdgeType (*matrix)[MAXVEX]) {
    for (int i = 0; i < G.numVertexes; i++) {
        for (int j = 0; j < G.numVertexes; j++) {
            matrix[i][j] = INFINITY;
        }
        EdgeNode *p = G.adjList[i].firstEdge;
        while (p) {
            matrix[i][p->adjvex] = p->weight;
            p = p->next;
        }
    }
}

⑻ 找出该图的一棵最小生成树。

void MiniSpanTree_Kruskal(GraphAdjList G) {
    Edge edges[MAXEDGE];
    int k = 0;
    for (int i = 0; i < G.numVertexes; i++) {
        EdgeNode *p = G.adjList[i].firstEdge;
        while (p) {
            if (i < p->adjvex) {
                edges[k].u = i;
                edges[k].v = p->adjvex;
                edges[k].w = p->weight;
                k++;
            }
            p = p->next;
        }
    }
    MinHeap H = { 0 };
    for (int i = 0; i < k; i++) {
        Insert(&H, edges[i]);
    }
    int parent[MAXVEX];
    for (int i = 0; i < G.numVertexes; i++) {
        parent[i] = i;
    }
    int count = 0;
    while (count < G.numVertexes-1 && H.size > 0) {
        Edge e = Delete(&H);
        int u = e.u, v = e.v;
        while (parent[u] != u) {
            u = parent[u];
        }
        while (parent[v] != v) {
            v = parent[v];
        }
        if (u != v) {
            printf("%c-%c ", G.adjList[e.u].data, G.adjList[e.v].data);
            parent[v] = u;
            count++;
        }
    }
}

完整代码：

使用c语言编写代码：要求建立一个无向图，采用邻接矩阵做为存储结构。输入信息为：第一行给出图的顶点数n和边数e。第二行给出n个字符，表示n个顶点的数据元素的值。后面是e行，给出每一条边的两个顶点的值(顶点之间无空格)。 输出每个顶点的值以及各顶点的邻接点的值。

下面是一个使用C语言编写的建立无向图，并采用邻接矩阵做为存储结构的示例代码，可以满足您的要求：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct {
    char data; // 顶点的数据元素的值
} VertexType; // 顶点类型

typedef struct {
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵，存储边
    int n, e; // 顶点数和边数
    VertexType vertex[MAX_VERTEX_NUM]; // 存储顶点的数据元素的值
} MGraph; // 图的邻接矩阵存储类型

void CreateMGraph(MGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &(G->n), &(G->e));
    getchar(); // 读取回车符

    printf("请输入%d个顶点的数据元素的值：", G->n);
    for(int i=0; i<G->n; i++) {
        scanf("%c", &(G->vertex[i].data));
        getchar(); // 读取回车符
    }

    // 初始化邻接矩阵，所有元素都为0
    for(int i=0; i<G->n; i++) {
        for(int j=0; j<G->n; j++) {
            G->edges[i][j] = 0;
        }
    }

    // 添加边，将相邻节点之间的元素标记为1
    printf("请依次输入每条边的两个顶点的值：\n");
    char v1, v2;
    int i, j;
    for(int k=0; k<G->e; k++) {
        scanf("%c%c", &v1, &v2);
        getchar(); // 读取回车符
        // 查找v1和v2在vertex数组中的位置
        for(i=0; i<G->n; i++) {
            if(v1 == G->vertex[i].data) {
                break;
            }
        }
        for(j=0; j<G->n; j++) {
            if(v2 == G->vertex[j].data) {
                break;
            }
        }
        G->edges[i][j] = 1;
        G->edges[j][i] = 1; // 无向图，矩阵对称
    }
}

void PrintMGraph(MGraph G) {
    printf("图的邻接矩阵为：\n");
    for(int i=0; i<G.n; i++) {
        printf("%c: ", G.vertex[i].data); // 输出顶点的数据元素的值
        for(int j=0; j<G.n; j++) {
            if(G.edges[i][j] == 1) {
                printf("%c ", G.vertex[j].data); // 输出邻接点的数据元素的值
            }
        }
        printf("\n");
    }
}

int main() {
    MGraph G;
    CreateMGraph(&G);
    PrintMGraph(G);
    return 0;
}

在上面的代码中，我们首先定义了一个MGraph类型的结构体，里面包含了邻接矩阵、顶点数、边数和顶点的数据元素的值等成员。然后，我们定义了CreateMGraph和PrintMGraph两个函数，分别用于创建图和输出图的邻接矩阵。在CreateMGraph函数中，我们先读取顶点数和边数，并读取每个顶点的数据元素的值。然后，我们初始化邻接矩阵，将所有元素都赋值为0。接着，我们逐个添加边，将相邻节点之间的元素标记为1，以便构建无向图。在PrintMGraph函数中，我们首先输出每个顶点的数据元素的值，然后输出该顶点的邻接点的数据元素的值。

最后，我们在main函数中调用CreateMGraph和PrintMGraph函数，以便创建图并输出邻接矩阵。