|
目录
//1、含邻接矩阵的图结构
//2、创建邻接矩阵
//3、打印邻接矩阵
//4、邻接表的图结构
//5、创建邻接表
//6、打印邻接表
//7、深度优先搜索
//8、广度优先搜索
//9、带主函数完整测试源码
//1、含邻接矩阵的图结构
用邻接矩阵来表示图：
//定义邻接矩阵的图结构
typedef struct graph {
elemtype data[N + 1];//存放顶点，不使用data[0]存放
int side[N + 1][N + 1];//邻接矩阵，同上
}graph;
//2、创建邻接矩阵
邻接矩阵是用来表示边的，0表示没有边，1表示有边，值为1的数组下标分别为边的起始和结尾序号：
//创建邻接矩阵
void Create1(graph* g,int sum) {
int i, j;
//初始化矩阵;
for (i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
g->side[i][j] = 0;//0表示没有边，1表示右边
}
}
//输入边的信息
printf("分别输入%d条边的始尾：\n",sum);
for (int k = 1; k <= sum; k++) {
scanf("%d %d", &i, &j);
g->side[i][j] = 1;//无向图的边是双向的
g->side[j][i] = 1;
}
}
//3、打印邻接矩阵
//打印邻接矩阵
void Print1(graph g) {
for (int i = 1; i <= N; i++) {//控制行
for (int j = 1; j <= N; j++) {//控制列
printf("%d ", g.side[i][j]);
}
printf("\n");//换行
}
}
//4、邻接表的图结构
//定义邻接表结构
typedef struct Linkgraph {
elemtype data;//顶点值
int index;//下标值
struct Linkgraph* next;//邻接点
}*Linkgraph;
//5、创建邻接表
先把每个顶点给放在一个数组里，然后把各顶点的邻接点以链表形式连在其后：
//创建邻接表
void Create2(Linkgraph arr[],graph* g) {//arr是邻接表的顶点数组，g是图
//先存放每个顶点的值和序号
for (int i = 1; i <= N; i++) {
arr[i] = (Linkgraph)malloc(sizeof(struct Linkgraph));//不初始化就报错
arr[i]->data = g->data[i];//先存顶点
arr[i]->index = i;//给每个顶点排号
arr[i]->next = NULL;//因为还不知道该顶点的邻接点是谁所以给空
}
//然后输入边
int i, j, sum;
Linkgraph new;//新的邻接表结点，用来连接邻接点
printf("输入边的条数：");
scanf("%d", &sum);
if (sum > E)
printf("输入错误！");
else {
printf("分别输入%d条边的始尾序号：\n", sum);
for (int k = 1; k <= sum; k++) {
scanf("%d %d", &i, &j);//输入边，也就是两个顶点的下标值
new = (Linkgraph)malloc(sizeof(struct Linkgraph));
new->index = j;//先给邻接点排号
new->data=arr[j]->data;//再给新节点赋值让他去连上前一个顶点
new->next = arr[i]->next;//这里是头插法，尾插法需要头节点
arr[i]->next = new;//
//无向图，所以两遍
new = (Linkgraph)malloc(sizeof(struct Linkgraph));
new->index = i;
new->data = arr[i]->data;
new->next = arr[j]->next;
arr[j]->next = new;
}
}
}
//6、打印邻接表
打印出每个顶点和他的邻接点
//打印邻接表
void Print2(Linkgraph arr[]) {
printf("顶点--->邻接点\n");
for (int i = 1; i <= N; i++) {//控制顶点
Linkgraph p = arr[i];//这里主要是方便后面的书写
printf("%c：\t", p->data);
while (p->next) {//这里循环退出时就代表他没有邻接点了
p = p->next;//找到他 的邻接点
printf("%c ", p->data);
}
printf("\n");
}
}
//7、深度优先搜索
深度优先就是一条路走到黑，用递归一直访问没有被访问过的顶点，直到把所有顶点都访问了：
//深度优先搜索
int visited[N + 1];//辅助数组，代表顶点的访问状态，访问过了为1，没访问为0
//先初始化这个辅助数组
void InitVisited() {
for (int i = 1; i <= N; i++) {
visited[i] = 0;
}
}
void DFS(graph* g,int i) {
printf("%c ", g->data[i]);
visited[i] = 1;//标记被访问过了
for (int j = 1; j <= N; j++) {
if (g->side[i][j] && !visited[j])//判断两顶点是否存在边并且另一顶点是否被访问过了
DFS(g, j);
}
}
//8、广度优先搜索
广度优先类似于树的层序遍历：
//广度优先搜索
void BFS(graph* g, int i) {
printf("%c ", g->data[i]);
int Queue[N + 1];//辅助队列
int front, rear;//队首队尾指针
front = rear = 0;
visited[i] = 1;//标记被访问过了
Queue[++rear] = i;//入队，把顶点的下标值入队
while (front < rear) {
i = Queue[++front];//出队，找到当前顶点的下标值
for (int j = 1; j <= N; j++) {
if (g->side[i][j] && !visited[j]) {//判断两顶点是否存在边并且另一顶点是否被访问过了
printf("%c ", g->data[j]);
visited[j] = 1;//标记被访问过了
Queue[++rear] = j;//入队，把顶点的下标值入队
}
}
}
}
//9、带主函数完整测试源码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#define N 4//图的最大顶点数
#define E N*(N-1)/2//无向图的最大边数
#define elemtype char //顶点元素类型
#define max 32727
//无向图
//定义邻接矩阵的图结构
typedef struct graph {
elemtype data[N + 1];//存放顶点，不使用data[0]存放
int side[N + 1][N + 1];//邻接矩阵，同上
}graph;
//初始化顶点信息
void Init(graph* g) {
//先存好顶点信息
for (int i = 1; i <= N; i++) {
scanf("%c", &g->data[i]);
getchar();
}
}
//创建邻接矩阵
void Create1(graph* g,int sum) {
int i, j;
//初始化矩阵;
for (i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
g->side[i][j] = 0;//0表示没有边，1表示右边
}
}
//输入边的信息
printf("分别输入%d条边的始尾：\n",sum);
for (int k = 1; k <= sum; k++) {
scanf("%d %d", &i, &j);
g->side[i][j] = 1;//无向图的边是双向的
g->side[j][i] = 1;
}
}
//打印邻接矩阵
void Print1(graph g) {
for (int i = 1; i <= N; i++) {//控制行
for (int j = 1; j <= N; j++) {//控制列
printf("%d ", g.side[i][j]);
}
printf("\n");//换行
}
}
//定义邻接表结构
typedef struct Linkgraph {
elemtype data;//顶点值
int index;//下标值
struct Linkgraph* next;//邻接点
}*Linkgraph;
//创建邻接表
void Create2(Linkgraph arr[],graph* g) {//arr是邻接表的顶点数组，g是图
//先存放每个顶点的值和序号
for (int i = 1; i <= N; i++) {
arr[i] = (Linkgraph)malloc(sizeof(struct Linkgraph));//不初始化就报错
arr[i]->data = g->data[i];//先存顶点
arr[i]->index = i;//给每个顶点排号
arr[i]->next = NULL;//因为还不知道该顶点的邻接点是谁所以给空
}
//然后输入边
int i, j, sum;
Linkgraph new;//新的邻接表结点，用来连接邻接点
printf("输入边的条数：");
scanf("%d", &sum);
if (sum > E)
printf("输入错误！");
else {
printf("分别输入%d条边的始尾序号：\n", sum);
for (int k = 1; k <= sum; k++) {
scanf("%d %d", &i, &j);//输入边，也就是两个顶点的下标值
new = (Linkgraph)malloc(sizeof(struct Linkgraph));
new->index = j;//先给邻接点排号
new->data=arr[j]->data;//再给新节点赋值让他去连上前一个顶点
new->next = arr[i]->next;//这里是头插法，尾插法需要头节点
arr[i]->next = new;//
//无向图，所以两遍
new = (Linkgraph)malloc(sizeof(struct Linkgraph));
new->index = i;
new->data = arr[i]->data;
new->next = arr[j]->next;
arr[j]->next = new;
}
}
}
//打印邻接表
void Print2(Linkgraph arr[]) {
printf("顶点--->邻接点\n");
for (int i = 1; i <= N; i++) {//控制顶点
Linkgraph p = arr[i];//这里主要是方便后面的书写
printf("%c：\t", p->data);
while (p->next) {//这里循环退出时就代表他没有邻接点了
p = p->next;//找到他 的邻接点
printf("%c ", p->data);
}
printf("\n");
}
}
void menu() {
printf("================\n");
printf("1、邻接矩阵\n");
printf("2、邻 接 表\n");
printf("================\n");
}
//深度优先搜索
int visited[N + 1];//辅助数组，代表顶点的访问状态，访问过了为1，没访问为0
//先初始化这个辅助数组
void InitVisited() {
for (int i = 1; i <= N; i++) {
visited[i] = 0;
}
}
void DFS(graph* g,int i) {
printf("%c ", g->data[i]);
visited[i] = 1;//标记被访问过了
for (int j = 1; j <= N; j++) {
if (g->side[i][j] && !visited[j])//判断两顶点是否存在边并且另一顶点是否被访问过了
DFS(g, j);
}
}
//广度优先搜索
void BFS(graph* g, int i) {
printf("%c ", g->data[i]);
int Queue[N + 1];//辅助队列
int front, rear;//队首队尾指针
front = rear = 0;
visited[i] = 1;//标记被访问过了
Queue[++rear] = i;//入队，把顶点的下标值入队
while (front < rear) {
i = Queue[++front];//出队，找到当前顶点的下标值
for (int j = 1; j <= N; j++) {
if (g->side[i][j] && !visited[j]) {//判断两顶点是否存在边并且另一顶点是否被访问过了
printf("%c ", g->data[j]);
visited[j] = 1;//标记被访问过了
Queue[++rear] = j;//入队，把顶点的下标值入队
}
}
}
}
int main(){
int chose = 0;
int start = 0;
int sum = 0;//边的数目
graph g;//创建一个无向图
Linkgraph arr[N + 1];//存放表头的数组,也就是存放每个结点的数组
printf("输入%d个顶点信息：", N);
Init(&g);//初始化顶点
while (1) {
menu();
scanf("%d", &chose);
switch (chose) {
case 1:
printf("输入边的条数：");
scanf("%d", &sum);
Create1(&g,sum);//创建矩阵
Print1(g);//打印邻接矩阵
InitVisited();
printf("输入起点序号：");
scanf("%d", &start);
printf("深度优先搜索遍历：\n");
DFS(&g, start);
printf("\n");
printf("广度优先搜索遍历：\n");
InitVisited();
BFS(&g, start);
printf("\n");
break;
case 2:
Create2(arr,&g);//创建邻接表
Print2(arr);
break;
default:return 0;
}
}
}
|