96.png

    1. /*
    2.     写出从图的邻接表表示转换成邻接矩阵表示的算法
    3.     分析：
    4.         我们之前也写过邻接矩阵的存储方式，在这里我们就只需要去遍历邻接表中的每一个顶点，
    5.         并根据边的信息，将数据填入邻接矩阵中即可
    6. */
    7. //分别写出邻接表和邻接矩阵两种方式的结构体
    8. //结构体的构建一定要和创建邻接表、创建邻接矩阵里的一模一样，不然会有问题，把我整惨了
    9. #include <stdio.h>
    10. #include <stdlib.h>
    11. #define MAXSIZE 100
    12. typedef struct Graph {
    13.     char Vertex[MAXSIZE];//顶点数组
    14.     int Edge[MAXSIZE][MAXSIZE];
    15.     int numV, numE;//顶点、边数量
    16. }adjMatrix;//邻接矩阵
    19. //邻接表存储的图
    20. typedef struct EdgeNode {//边表结点
    21.     int index;//该边所指向的顶点的位置,在顶点数组里面的位置信息
    22.     int weight;//权值
    23.     EdgeNode *next;//下一个邻接边
    24. }EdgeNode;
    26. typedef struct VertexNode {//顶点表节点
    27.     char info;//顶点信息
    28.     EdgeNode *firstEdge;//指向第一条依附该顶点的边的指针
    29. }VertexNode, Adjlist[MAXSIZE];
    31. typedef struct {
    32.     Adjlist adjlist;//顶点数组
    33.     int numE, numV;//边数、顶点数
    34. }ALGraph;
    35. void edgeIput(ALGraph *alG, adjMatrix *amG, int index, int *visited) {
    36.     visited[index] = 1;//标记为已访问
    37.     for (EdgeNode *p = alG->adjlist[index].firstEdge; p; p = p->next) {
    38.         amG->Edge[index][p->index] = p->weight;//边信息存入邻接矩阵
    39.         if (!visited[p->index])
    40.             edgeIput(alG, amG, p->index, visited);
    41.     }
    42. }
    43. void transform(ALGraph *alG, adjMatrix *amG) {//开始进行转换
    45.     amG->numE = alG->numE;
    46.     amG->numV = alG->numV;
    47.     for (int v = 0; v < amG->numV; v++) {
    48.         amG->Vertex[v] = alG->adjlist[v].info;//顶点信息存入邻接矩阵
    49.     }
    50.     //初始化图
    51.     for (int i = 0; i < amG->numV; i++) {
    52.         for (int j = 0; j < amG->numV; j++) {
    53.             i == j ? amG->Edge[i][j] = 0 : amG->Edge[i][j] = 32767;
    54.         }
    55.     }
    56.     for (int v = 0; v < amG->numV; v++) {
    57.         //存入边信息
    58.         EdgeNode *p = alG->adjlist[v].firstEdge;
    59.         while (p) {
    60.             amG->Edge[v][p->index] = p->weight;
    61.             p = p->next;
    62.         }
    63.     }
    64. }
    65. int main() {
    66.     ALGraph alG;
    67.     adjMatrix amG;
    68.     void createGraphInFile(ALGraph*);//声明方法
    69.     void dispGraph(adjMatrix *);
    70.     createGraphInFile(&alG);//创建图G
    71.     transform(&alG, &amG);
    72.     dispGraph(&amG);
    73.     return 0;
    74. }