【数据结构——图】图的邻接矩阵和邻接表的存储（头歌实践教学平台习题）【合集】

 if (g.edges[i][j]!=INF)
     printf("%d ",g.edges[i][j]);
 else
     printf("%s ","∞");

     for (int i=0;i<G->n;i++)
     {
         p=G->adjlist[i].firstarc;
         printf("%3d: ",i);
         while (p!=NULL)
         {
             printf("%3d[%d]→",p->adjvex,p->weight);
             p=p->nextarc;
         }
         printf("∧\n");
     }

6 10 0 5 32767 7 32767 32767 32767 0 4 32767 32767 32767 8 32767 0 32767 32767 9 32767 32767 5 0 32767 6 32767 32767 32767 5 0 32767 3 32767 32767 32767 1 0

边(0,5)权为:3

边(5,4)权为:1

边(0,1)权为:5 

边(1,2)权为:4

边(4,3)权为:5

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
const int MAX_VERTICES = 6; // 最大顶点数
const int INF = 32767;      // 表示无穷大

// 邻接矩阵表示的图
struct GraphMatrix {
  int n;                     // 顶点数
  vector<vector<int>> edges; // 邻接矩阵
};

// 邻接表的边节点
struct ArcNode {
  int adjvex;       // 邻接点在图中的位置
  int weight;       // 边的权重
  ArcNode *nextarc; // 指向下一条边
};

// 邻接表
struct VNode {
  int data;          // 顶点信息
  ArcNode *firstarc; // 指向第一条边
};

struct GraphList {
  int n;                 // 顶点数
  vector<VNode> adjlist; // 邻接表
};

// 输入邻接矩阵并构建图
void inputGraphMatrix(GraphMatrix &g) {
  cin >> g.n; // 读入顶点数
  int e;      // 边数
  cin >> e;   // 读入边数
  g.edges.resize(g.n, vector<int>(g.n, INF));

  for (int i = 0; i < g.n; ++i) {
    g.edges[i][i] = 0; // 对角线元素为0
  }

  // 读入邻接矩阵
  for (int i = 0; i < g.n; ++i) {
    for (int j = 0; j < g.n; ++j) {
      cin >> g.edges[i][j];
    }
  }
}

// 输出邻接矩阵
void printGraphMatrix(const GraphMatrix &g) {
  cout << "(1)图G的邻接矩阵:" << endl;
  for (int i = 0; i < g.n; ++i) {
    for (int j = 0; j < g.n; ++j) {
      if (g.edges[i][j] == INF) {
        cout << "∞ ";
      } else {
        cout << g.edges[i][j] << " ";
      }
    }
    cout << endl;
  }
}

// 构建邻接表
void buildGraphList(const GraphMatrix &gm, GraphList &gl) {
  gl.n = gm.n;
  gl.adjlist.resize(gl.n);

  for (int i = 0; i < gm.n; ++i) {
    gl.adjlist[i].data = i;           // 存储顶点
    gl.adjlist[i].firstarc = nullptr; // 初始化第一条边
  }

  // 从邻接矩阵构建邻接表
  for (int i = 0; i < gm.n; ++i) {
    for (int j = 0; j < gm.n; ++j) {
      if (gm.edges[i][j] != INF && gm.edges[i][j] != 0) {
        ArcNode *arc = new ArcNode(); // 动态分配新边
        arc->adjvex = j;              // 指向邻接点
        arc->weight = gm.edges[i][j]; // 边的权重
        arc->nextarc = nullptr;       // 初始化下一条边为nullptr

        // 将新节点插入已排序的链表中
        if (gl.adjlist[i].firstarc == nullptr ||
            gl.adjlist[i].firstarc->adjvex > j) {
          arc->nextarc = gl.adjlist[i].firstarc; // 插入到链表头
          gl.adjlist[i].firstarc = arc;
        } else {
          ArcNode *p = gl.adjlist[i].firstarc;
          while (p->nextarc != nullptr && p->nextarc->adjvex < j) {
            p = p->nextarc; // 寻找插入位置
          }
          arc->nextarc = p->nextarc; // 插入
          p->nextarc = arc;
        }
      }
    }
  }
}

// 输出邻接表
void printGraphList(const GraphList &gl) {
  cout << "(2)图G的邻接表:" << endl;
  for (int i = 0; i < gl.n; ++i) {
    cout << "  " << i << ": ";
    ArcNode *p = gl.adjlist[i].firstarc;
    while (p != nullptr) {
      cout << "  " << p->adjvex << "[" << p->weight << "]→";
      p = p->nextarc;
    }
    cout << "∧" << endl;
  }
}

int main() {
  GraphMatrix gm;
  inputGraphMatrix(gm);
  printGraphMatrix(gm);

  GraphList gl;
  buildGraphList(gm, gl);
  printGraphList(gl);

  return 0;
}