还是按照习惯,先附上PPT讲解,文章后面是代码部分。
邻接表的表示方法不唯一,而且所占空间较多,所以一定要够稀疏才合算。
#include<iostream> using namespace std; #include<stdlib.h> #define MAXN 100 int G[MAXN][MAXN], Nv, Ne; void BuildGraph() { int i, j, v1, v2, w; cout << "请输入需要插入的顶点数:"; cin>>Nv;//初始化定点数 // 初始化图 for (i = 0;i < Nv;i++) for (j = 0;j < Nv;j++) G[i][j] = 0; cout << "请输入需要插入的边数:"; cin >> Ne; // 插入边 for (i = 0;i < Ne;i++) { cout << "请输入需要连接的两个顶点的编号以及权重(可设置为1):"; cin >> v1 >> v2 >> w; G[v1][v2] = w; G[v2][v1] = w; } } // 遍历图 void print() { int i, j; for (i = 0;i < Nv;i++) { for (j = 0;j < Nv;j++) cout << G[i][j] << ' '; cout << endl; } } int main() { BuildGraph(); print(); return 0; }
//02 图的邻接表表示法 #include<stdio.h> using namespace std; #include<stdlib.h> #pragma warning(disable:4996) #define MaxVertexNum 100 typedef struct AdjVNode* AdjList; struct AdjVNode { int weight; // 权值 int adjv; // 下标 AdjList next; // 其后一个 }; AdjList Graph[MaxVertexNum]; int Ne, Nv; // 建图 void BuildGraph() { int i; int v1, v2, w; AdjList NewNode; scanf("%d", &Nv); for (i = 0;i < Nv;i++) { Graph[i] = (AdjList)malloc(sizeof(struct AdjVNode)); Graph[i]->adjv = i; Graph[i]->next = NULL; } scanf("%d", &Ne); for (i = 0;i < Ne;i++) { scanf("%d %d %d", &v1, &v2, &w); NewNode = (AdjList)malloc(sizeof(struct AdjVNode)); NewNode->adjv = v1; NewNode->weight = w; NewNode->next = Graph[v2]->next; Graph[v2]->next = NewNode; NewNode = (AdjList)malloc(sizeof(struct AdjVNode)); NewNode->adjv = v2; NewNode->weight = w; NewNode->next = Graph[v1]->next; Graph[v1]->next = NewNode; } } void print() { AdjList tmp; int i; for (i = 0;i < Nv;i++) { tmp = Graph[i]; while (tmp) { printf("%d ", tmp->adjv); tmp = tmp->next; } printf("\n"); } } int main() { BuildGraph(); print(); return 0; }