设图结点的元素类型为char，建立一个不少于8个顶点的带权无向图G，实现以下图的各种基本操作的程序： ① 用邻接矩阵作为储结构存储图G并输出该邻接矩阵； ② 用邻接链表作为储结构存储图G并输出该邻接链表； ③ 按DFS算法输出图G中顶点的遍历序列； ④ 按BFS算法输出图G中顶点的遍历序列； ⑤主函数通过函数调用实现以上各项操作。

以下是该图的邻接矩阵和邻接链表：

邻接矩阵：
  A B C D E F G H
A 0 1 1 0 0 0 0 0
B 1 0 1 1 0 0 0 0
C 1 1 0 1 1 0 0 0
D 0 1 1 0 1 1 0 0
E 0 0 1 1 0 1 1 0
F 0 0 0 1 1 0 0 1
G 0 0 0 0 1 0 0 1
H 0 0 0 0 0 1 1 0

邻接链表：
A -> B -> C
B -> A -> C -> D
C -> A -> B -> D -> E
D -> B -> C -> E -> F
E -> C -> D -> F -> G
F -> D -> E -> H
G -> E -> H
H -> E -> F

其中，权重均为1。

以下是完整的程序：

相关问题

设图结点的元素类型为char,建立一个不少于8个顶点的带权无向图G,实现以下图的各种基本操作的程序: ① 用邻接矩阵作为储结构存储图G并输出该邻接矩阵; ② 用邻接链表作为储结构存储图G并输出该邻接链表; ③ 按DF

S算法从图的第一个结点开始遍历整个图，并输出遍历结果；④ 按BFS算法从图的第一个结点开始遍历整个图，并输出遍历结果。

以下是程序实现：

#include<iostream>
#include<queue>
using namespace std;

const int MAX_SIZE = 8; // 图的最大结点数
char vertex[MAX_SIZE] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}; // 图的结点元素
int edge[MAX_SIZE][MAX_SIZE] = { // 图的邻接矩阵
    {0, 1, 1, 0, 0, 0, 0, 0},
    {1, 0, 1, 1, 0, 0, 0, 0},
    {1, 1, 0, 1, 1, 0, 0, 0},
    {0, 1, 1, 0, 1, 1, 0, 0},
    {0, 0, 1, 1, 0, 1, 1, 0},
    {0, 0, 0, 1, 1, 0, 0, 1},
    {0, 0, 0, 0, 1, 0, 0, 1},
    {0, 0, 0, 0, 0, 1, 1, 0}
};

struct EdgeNode { // 图的邻接链表结点
    int adjvex; // 邻接点在vertex数组中的下标
    EdgeNode* next; // 指向下一个邻接点的指针
};

struct VertexNode { // 图的邻接链表的头结点
    char data; // 结点元素
    EdgeNode* firstedge; // 指向第一个邻接点的指针
};

VertexNode adjList[MAX_SIZE]; // 图的邻接链表

bool visited[MAX_SIZE]; // 标记结点是否被访问过

void createAdjList() { // 创建图的邻接链表
    for(int i = 0; i < MAX_SIZE; i++) {
        adjList[i].data = vertex[i];
        adjList[i].firstedge = NULL;
        for(int j = 0; j < MAX_SIZE; j++) {
            if(edge[i][j] == 1) {
                EdgeNode* e = new EdgeNode();
                e->adjvex = j;
                e->next = adjList[i].firstedge;
                adjList[i].firstedge = e;
            }
        }
    }
}

void printAdjMatrix() { // 输出图的邻接矩阵
    for(int i = 0; i < MAX_SIZE; i++) {
        for(int j = 0; j < MAX_SIZE; j++) {
            cout << edge[i][j] << " ";
        }
        cout << endl;
    }
}

void printAdjList() { // 输出图的邻接链表
    for(int i = 0; i < MAX_SIZE; i++) {
        EdgeNode* e = adjList[i].firstedge;
        cout << adjList[i].data << " ";
        while(e != NULL) {
            cout << vertex[e->adjvex] << " ";
            e = e->next;
        }
        cout << endl;
    }
}

void DFS(int i) { // 深度优先遍历
    visited[i] = true;
    cout << vertex[i] << " ";
    EdgeNode* e = adjList[i].firstedge;
    while(e != NULL) {
        if(!visited[e->adjvex]) {
            DFS(e->adjvex);
        }
        e = e->next;
    }
}

void BFS(int i) { // 广度优先遍历
    queue<int> q;
    visited[i] = true;
    cout << vertex[i] << " ";
    q.push(i);
    while(!q.empty()) {
        int j = q.front();
        q.pop();
        EdgeNode* e = adjList[j].firstedge;
        while(e != NULL) {
            if(!visited[e->adjvex]) {
                visited[e->adjvex] = true;
                cout << vertex[e->adjvex] << " ";
                q.push(e->adjvex);
            }
            e = e->next;
        }
    }
}

int main() {
    createAdjList();
    cout << "邻接矩阵：" << endl;
    printAdjMatrix();
    cout << "邻接链表：" << endl;
    printAdjList();
    cout << "深度优先遍历结果：" << endl;
    for(int i = 0; i < MAX_SIZE; i++) {
        visited[i] = false;
    }
    DFS(0);
    cout << endl;
    cout << "广度优先遍历结果：" << endl;
    for(int i = 0; i < MAX_SIZE; i++) {
        visited[i] = false;
    }
    BFS(0);
    cout << endl;
    return 0;
}

用c语言：设图结点的元素类型为char，建立一个不少于8个顶点的带权无向图G，实现以下图的各种基本操作的程序： ① 用邻接矩阵作为储结构存储图G并输出该邻接矩阵； ② 用邻接链表作为储结构存储图G并输出该邻接链表； ③ 按DFS算法输出图G中顶点的遍历序列； ④ 按BFS算法输出图G中顶点的遍历序列； ⑤主函数通过函数调用实现以上各项操作。

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 8

// 邻接矩阵结构体
typedef struct {
    char vertex[MAX_VERTEX_NUM]; // 存储结点的元素类型为char
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值
    int vertexNum; // 结点数量
    int edgeNum; // 边数量
} AdjMatrix;

// 邻接链表结构体
typedef struct EdgeNode {
    int adjvex; // 邻接点的下标
    int weight; // 权值
    struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;

typedef struct {
    char vertex;
    EdgeNode *firstEdge; // 指向第一个邻接点
} VertexNode;

typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM]; // 存储结点的元素类型为char
    int vertexNum; // 结点数量
    int edgeNum; // 边数量
} AdjList;

// 创建邻接矩阵
void createAdjMatrix(AdjMatrix *G) {
    char vertex[MAX_VERTEX_NUM] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {
        {0, 1, 0, 1, 0, 0, 0, 0},
        {1, 0, 1, 1, 0, 0, 0, 0},
        {0, 1, 0, 1, 1, 1, 0, 0},
        {1, 1, 1, 0, 0, 1, 1, 0},
        {0, 0, 1, 0, 0, 1, 0, 1},
        {0, 0, 1, 1, 1, 0, 0, 1},
        {0, 0, 0, 1, 0, 0, 0, 1},
        {0, 0, 0, 0, 1, 1, 1, 0}
    };
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertex[i] = vertex[i];
        for (int j = 0; j < MAX_VERTEX_NUM; j++) {
            G->edge[i][j] = edge[i][j];
        }
    }
    G->vertexNum = MAX_VERTEX_NUM;
    G->edgeNum = 14;
}

// 输出邻接矩阵
void printAdjMatrix(AdjMatrix G) {
    printf("邻接矩阵：\n");
    printf("  ");
    for (int i = 0; i < G.vertexNum; i++) {
        printf("%c ", G.vertex[i]);
    }
    printf("\n");
    for (int i = 0; i < G.vertexNum; i++) {
        printf("%c ", G.vertex[i]);
        for (int j = 0; j < G.vertexNum; j++) {
            printf("%d ", G.edge[i][j]);
        }
        printf("\n");
    }
}

// 创建邻接链表
void createAdjList(AdjList *G) {
    char vertex[MAX_VERTEX_NUM] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
    int adjList[MAX_VERTEX_NUM][3] = {
        {1, 1, 3},
        {0, 1, 2},
        {1, 1, 3},
        {0, 1, 1},
        {2, 1, 3},
        {2, 1, 4},
        {3, 1, 7},
        {4, 1, 6}
    };
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertex[i].vertex = vertex[i];
        G->vertex[i].firstEdge = NULL;
    }
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        int adjvex = adjList[i][0];
        int weight = adjList[i][1];
        EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = adjvex;
        e->weight = weight;
        e->next = G->vertex[i].firstEdge;
        G->vertex[i].firstEdge = e;
    }
    G->vertexNum = MAX_VERTEX_NUM;
    G->edgeNum = 14;
}

// 输出邻接链表
void printAdjList(AdjList G) {
    printf("邻接链表：\n");
    for (int i = 0; i < G.vertexNum; i++) {
        printf("%c -> ", G.vertex[i].vertex);
        EdgeNode *e = G.vertex[i].firstEdge;
        while (e != NULL) {
            printf("%c(%d) ", G.vertex[e->adjvex].vertex, e->weight);
            e = e->next;
        }
        printf("\n");
    }
}

// DFS遍历邻接矩阵
void DFS_Matrix(AdjMatrix G, int i, int *visited) {
    visited[i] = 1;
    printf("%c ", G.vertex[i]);
    for (int j = 0; j < MAX_VERTEX_NUM; j++) {
        if (G.edge[i][j] == 1 && visited[j] == 0) {
            DFS_Matrix(G, j, visited);
        }
    }
}

// DFS遍历邻接链表
void DFS_List(AdjList G, int i, int *visited) {
    visited[i] = 1;
    printf("%c ", G.vertex[i].vertex);
    EdgeNode *e = G.vertex[i].firstEdge;
    while (e != NULL) {
        if (visited[e->adjvex] == 0) {
            DFS_List(G, e->adjvex, visited);
        }
        e = e->next;
    }
}

// BFS遍历邻接矩阵
void BFS_Matrix(AdjMatrix G, int i, int *visited) {
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    visited[i] = 1;
    printf("%c ", G.vertex[i]);
    queue[rear++] = i;
    while (front != rear) {
        int j = queue[front++];
        for (int k = 0; k < MAX_VERTEX_NUM; k++) {
            if (G.edge[j][k] == 1 && visited[k] == 0) {
                visited[k] = 1;
                printf("%c ", G.vertex[k]);
                queue[rear++] = k;
            }
        }
    }
}

// BFS遍历邻接链表
void BFS_List(AdjList G, int i, int *visited) {
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    visited[i] = 1;
    printf("%c ", G.vertex[i].vertex);
    queue[rear++] = i;
    while (front != rear) {
        int j = queue[front++];
        EdgeNode *e = G.vertex[j].firstEdge;
        while (e != NULL) {
            if (visited[e->adjvex] == 0) {
                visited[e->adjvex] = 1;
                printf("%c ", G.vertex[e->adjvex].vertex);
                queue[rear++] = e->adjvex;
            }
            e = e->next;
        }
    }
}

int main() {
    AdjMatrix G_Matrix;
    createAdjMatrix(&G_Matrix);
    printAdjMatrix(G_Matrix);
    printf("\n");
    
    AdjList G_List;
    createAdjList(&G_List);
    printAdjList(G_List);
    printf("\n");
    
    int visited[MAX_VERTEX_NUM] = {0};
    printf("DFS遍历邻接矩阵：");
    DFS_Matrix(G_Matrix, 0, visited);
    printf("\n");
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        visited[i] = 0;
    }
    printf("DFS遍历邻接链表：");
    DFS_List(G_List, 0, visited);
    printf("\n");
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        visited[i] = 0;
    }
    printf("BFS遍历邻接矩阵：");
    BFS_Matrix(G_Matrix, 0, visited);
    printf("\n");
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        visited[i] = 0;
    }
    printf("BFS遍历邻接链表：");
    BFS_List(G_List, 0, visited);
    printf("\n");
    return 0;
}