#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#define Infinty INT_MAX
#define MAX_VERTEX_NUM 20 /*最多顶点个数*/
#define Error -1
#define OK 1
/*=====================================邻接矩阵表示法的c语言描述=================================================*/
typedef enum { DG, DN, UDG, UDN }GraphKind;/*图的种类: DG表示有向图, DN表示有向网, UDG表示无向图, UDN表示无向网*/
/*边的定义*/
typedef int AdjType; /*权值类型*/
typedef struct {
AdjType adj; /*对于无权图，用1或0表示是否相邻，对带权图，则为权值类型*/
//OtherInfo info; /*边存储的其它信息，因为此处无使用，故进行注释处理*/
} ArcNode;
/*图（邻接矩阵）的定义*/
typedef char VertexData;
typedef struct {
GraphKind kind; /*图的种类标志*/
int vexnum, arcnum; /*图的顶点数和弧数*/
VertexData vertex[MAX_VERTEX_NUM]; /*顶点向量*/
ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接矩阵*/
}AdjMatrix;
/*=====================================图（邻接矩阵表示法）的基本操作=================================================*/
/*算法7-1中需调用的LocateVex函数*/
int LocateVex(AdjMatrix* G, VertexData v) {
int j = Error, k;
for (k = 0; k < G->vexnum; k++)
if (G->vertex[k] == v) {
j = k;
break;
}
return j;
}
//算法7-1：输入n个顶点和e条边的信息，创建赋权有向图G的邻接矩阵
void CreateDN(AdjMatrix* G) {
int i, j, k;
AdjType weight;
VertexData v1, v2;
printf("请输入图的顶点数目：");
scanf("%d", &G->vexnum);
printf("请输入弧的数目：");
scanf("%d", &G->arcnum);
/*初始化邻接矩阵*/
for (i = 0; i < G->vexnum; i++)
for (j = 0; j < G->vexnum; j++)
G->arcs[i][j].adj = Infinty;
printf("请输入顶点信息（直接连续输入，不要使用空格或回车间隔，除非空格或回车是顶点存储的元素）：");
rewind(stdin); /*消除前面回车的影响*/
for (i = 0; i < G->vexnum; i++)
scanf("%c", &G->vertex[i]);
rewind(stdin);
printf("构建邻接矩阵,请输入一条弧的起点、终点与权值，例如\"a,b,10\"\n");
for (k = 0; k < G->arcnum; k++) {
printf("第%d-%d条:", G->arcnum, k + 1);
rewind(stdin);
scanf("%c,%c,%d", &v1, &v2, &weight);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
G->arcs[i][j].adj = weight;
}
}
void CreateDNG(AdjMatrix* G) {
int i, j, k;
VertexData v1, v2;
printf("请输入图的顶点数目：");
scanf("%d", &G->vexnum);
printf("请输入弧的数目：");
scanf("%d", &G->arcnum);
/*初始化邻接矩阵*/
for (i = 0; i < G->vexnum; i++)
for (j = 0; j < G->vexnum; j++)
G->arcs[i][j].adj = Infinty;
printf("请输入顶点信息（直接连续输入，不要使用空格或回车间隔，除非空格或回车是顶点存储的元素）：");
rewind(stdin); /*消除前面回车的影响*/
for (i = 0; i < G->vexnum; i++)
scanf("%c", &G->vertex[i]);
rewind(stdin);
printf("构建邻接矩阵,请输入一条弧的两端点，例如\"a,b\"\n");
for (k = 0; k < G->arcnum; k++) {
printf("第%d-%d条:", G->arcnum, k + 1);
rewind(stdin);
scanf("%c,%c", &v1, &v2);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
G->arcs[i][j].adj = 1;
}
}
void CreateUDN(AdjMatrix*G) {
int i, j, k;
AdjType weight;
VertexData v1, v2;
printf("请输入图的顶点数目：");
scanf("%d", &G->vexnum);
printf("请输入弧的数目：");
scanf("%d", &G->arcnum);
/*初始化邻接矩阵*/
for (i = 0; i < G->vexnum; i++)
for (j = 0; j < G->vexnum; j++)
G->arcs[i][j].adj = Infinty;
printf("请输入顶点信息（直接连续输入，不要使用空格或回车间隔，除非空格或回车是顶点存储的元素）：");
rewind(stdin); /*消除前面回车的影响*/
for (i = 0; i < G->vexnum; i++)
scanf("%c", &G->vertex[i]);
rewind(stdin);
printf("构建邻接矩阵,请输入一条弧的起点、终点与权值，例如\"a,b,10\"\n");
for (k = 0; k < G->arcnum; k++) {
printf("第%d-%d条:", G->arcnum, k + 1);
rewind(stdin);
scanf("%c,%c,%d", &v1, &v2, &weight);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
G->arcs[i][j].adj = weight;
G->arcs[j][i].adj = weight;
}
}
void DELDN(AdjMatrix* G){
printf("删除邻接矩阵,请输入一条弧的两端点，例如\"a,b\"\n");
VertexData v1, v2;
int i, j;
rewind(stdin);
scanf("%c,%c", &v1, &v2);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
G->arcs[i][j].adj = Infinty;
}
int main() {
AdjMatrix G;
G.kind = DN;
CreateDN(&G); /*创建赋权有向图*/
//CreateDN(&G); /*创建赋权无向图*/
//CreateDN_C(&G); /*创建不带权的有向图*/
int i, j;
printf("输出图的顶点：\n");
for (i = 0; i < G.vexnum; i++)
printf("%c", G.vertex[i]);
printf("\n");
printf("输出图的邻接矩阵：\n");
for (i = 0; i < G.vexnum; i++) {
for (j = 0; j < G.vexnum; j++)
printf("%14d", G.arcs[i][j].adj);
printf("\n");
}
DELDN(&G);//删除路径
printf("删除后图的邻接矩阵：\n");
for (i = 0; i < G.vexnum; i++) {
for (j = 0; j < G.vexnum; j++)
printf("%14d", G.arcs[i][j].adj);
printf("\n");
}
}
原文：https://www.cnblogs.com/1388h26/p/12951637.html