还是按照习惯,先附上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;
}