玩转图论:邻接矩阵在C语言中的实现与应用 - 创建、打印与深度/广度优先遍历
最编程
2024-02-20 20:58:28
...
邻接矩阵法
用一维数组图中顶点的信息,用一个二维数组存储图中边的信息(各顶点之间的邻接关系)。存储顶点之间邻接关系的二维数组称为邻接矩阵。
结点数为n的图G=(V,E)的邻接矩阵A是n*n的,将G的顶点编号为v1,v2,......vn。若(vi,vj)∈E,则A[i][j]=1,否则A[i][j]=0。
对于带权图而言,若顶点vi,vj之间有边相连,则邻接矩阵中对应项存放着该边对应的权值,若顶点vi和vj不相连,则用∞来表示这两个顶点之间不存在边
无向图的邻接矩阵表示:
有向图的邻接矩阵表示
网的邻接矩阵表示(网就是带权的图)
无向图
#include <stdio.h>
#include <string.h>
#define MaxVertexNum 100 //顶点数目最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct
{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵,边表
int vexnum, edgenum; //图的顶点数和弧数
}MGraph;
/**********创建无向图**********/
void create_Graph(MGraph *G)
{
int i, j;
int start, end; //边的起点序号、终点序号
int numV, numE;
int w; //边上的权值
printf("请输入所创建无向图的顶点数和边数(用空格隔开):");
scanf_s("%d%d", &numV, &numE);
G->vexnum=numV;
G->edgenum=numE;
printf("\n");
//图的初始化
for (i = 0; i < G->vexnum; i++)
{
for (j = 0; j < G->vexnum; j++)
{
if (i == j)
G->Edge[i][j] = 0;
else
G->Edge[i][j] = 32767;
}
}
//顶点信息存入顶点表
for (i = 0; i < G->vexnum; i++)
{
printf("请输入第%d个顶点的信息:",i+1);
scanf_s("%d", &G->Vex[i]);
}
printf("\n");
//输入无向图边的信息
for (i = 0; i < G->edgenum; i++)
{
printf("请输入边的起点序号,终点序号,权值(用空格隔开):");
scanf_s("%d%d%d", &start, &end, &w);
G->Edge[start -1][end -1] = w;
G->Edge[end - 1][start - 1] = w; //无向图具有对称性
}
}
/***********打印出邻接矩阵*********/
void print_Matrix(MGraph G)
{
int i, j;
printf("\n图的顶点为:");
for (i = 0; i < G.vexnum; i++)
printf("%d ", G.Vex[i]);
printf("\n输出邻接矩阵:\n");
printf("\t");
for (i = 0; i < G.vexnum; i++)
printf("\t%8d", G.Vex[i]);
for (i = 0; i < G.vexnum; i++)
{
printf("\n\n%8d", G.Vex[i]);
for (j = 0; j < G.vexnum; j++)
{
if (G.Edge[i][j] == 32767)
printf("\t%8s", "∞");
else
printf("\t%8d", G.Edge[i][j]);
}
printf("\n");
}
}
void main()
{
MGraph G;
create_Graph(&G);
print_Matrix(G);
system("pause");
}
运行结果如下:
有向图
代码基本是一样的,只是对称的位置上权值不一样
/***********创建有向图************/
void create_Graph2(MGraph *G)
{
int i, j;
int start, end; //边的起点序号、终点序号
int numV, numE;
int w; //边上的权值
printf("请输入所创建有向图的顶点数和边数(用空格隔开):");
scanf_s("%d%d", &numV, &numE);
G->vexnum = numV;
G->edgenum = numE;
printf("\n");
//图的初始化
for (i = 0; i < G->vexnum; i++)
{
for (j = 0; j < G->vexnum; j++)
{
if (i == j)
G->Edge[i][j] = 0;
else
G->Edge[i][j] = 32767;
}
}
//顶点信息存入顶点表
for (i = 0; i < G->vexnum; i++)
{
printf("请输入第%d个顶点的信息:", i + 1);
scanf_s("%d", &G->Vex[i]);
}
printf("\n");
//输入无向图边的信息
for (i = 0; i < G->edgenum; i++)
{
printf("请输入边的起点序号,终点序号,权值(用空格隔开):");
scanf_s("%d%d%d", &start, &end, &w);
G->Edge[start - 1][end - 1] = w; //有向图只在这里不一样
}
}
深度优先遍历
/**********深度优先遍历*********/
int visitDFS[maxSize];
void DFS(MGraph G,int i)
{
int j;
visitDFS[i] = 1;
printf("%d ", G.Vex[i]);
for (j = 0; j < G.vexnum; j++)
{
if (G.Edge[i][j] != 32767 && !visitDFS[j])
DFS(G, j);
}
}
void DFSTraverse(MGraph G)
{
int i;
for (i = 0; i < G.vexnum; i++)
visitDFS[i] = 0;
for (i = 0; i < G.vexnum; i++)
{
if (!visitDFS[i])
DFS(G, i);
}
}
深度优先遍历
/**********深度优先遍历*********/
int visitDFS[maxSize];
void DFS(MGraph G,int i)
{
int j;
visitDFS[i] = 1;
printf("%d ", G.Vex[i]);
for (j = 0; j < G.vexnum; j++)
{
if (G.Edge[i][j] != 32767 && !visitDFS[j])
DFS(G, j);
}
}
void DFSTraverse(MGraph G)
{
int i;
for (i = 0; i < G.vexnum; i++)
visitDFS[i] = 0;
for (i = 0; i < G.vexnum; i++)
{
if (!visitDFS[i])
DFS(G, i);
}
}
广度优先遍历
/**************广度优先遍历*************/
//队列
typedef struct
{
int data[maxSize];
int front, rear;
}Queue;
//初始化
void InitQueue(Queue *Q)
{
Q->front = Q->rear = 0;
}
//判断队空
int IsEmpty(Queue *Q)
{
if (Q->front == Q->rear)
return 1;
else
return 0;
}
//入队
void EnQueue(Queue *Q,int e)
{
if ((Q->rear + 1) % maxSize == Q->front)
return;
else
{
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % maxSize;
}
}
//出队
void DeQueue(Queue *Q,int *e)
{
if (Q->rear == Q->front)
return;
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % maxSize;
}
//广度优先遍历
int visitBFS[maxSize];
void BFS(MGraph G)
{
int i, j;
Queue Q;
for (i = 0; i < G.vexnum; i++)
visitBFS[maxSize] = 0;
InitQueue(&Q);
for (i = 0; i < G.vexnum; i++)
{
if (!visitBFS[i])
{
visitBFS[i] = 1;
printf("%d ", G.Vex[i]);
EnQueue(&Q, i);
while (!IsEmpty(&Q))
{
DeQueue(&Q, &i);
for (j = 0; j < G.vexnum; j++)
{
if (!visitBFS[j] && G.Edge[i][j] != 32767)
{
visitBFS[j] = 1;
printf("%d ", G.Vex[j]);
EnQueue(&Q, j);
}
}
}
}
}
}
上一篇: 导向图与非导向图:邻接矩阵与邻接列表详解
下一篇: 简单易懂:常用图形数据储存架构解析