代码参照了严蔚敏、吴伟民编写的数据结构（C语言版）。
部分内容参考了这位大佬：
https://blog.csdn.net/jeffleo/article/details/53326648
所有代码采用C语言编写。讲解请查看注释。
头文件及宏定义
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INFINITY 0//最大值0，即两个顶点之间没有弧时的权值
#define MAX_VERTEX_NUM 20//最大顶点个数
#define OK 1
#define Fail 0
#define False 0
#define True 1
#define Error 0;
typedef定义数据类型和结构体
typedef int VRType;
typedef int Status;
typedef char InfoType;
typedef char VertexType;
typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网}
typedef struct ArcCell{
VRType adj;//VRType是顶点关系类型。对无权图，用1和0表示相邻否；对带权图，则为权值类型
InfoType *info;//该弧相关信息的指针
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];//顶点向量
AdjMatrix arcs;//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
GraphKind kind;//图的种类标志
}MGraph;
LocateVex
Status LocateVex(MGraph G, VertexType u){//找出顶点u在顶点数组vexs中的次序
int i=0;
for (i=0; i<G.vexnum; i++){
if (G.vexs[i]==u)
return i;
}
return False;
}
CreateGraph
Status CreateGraph(MGraph *G){//构造无向有权图
int i=0,j=0,k=0,w=0;
printf("请输入图的顶点个数和弧数\n");
fflush(stdin);
scanf("%d",&G->vexnum);
fflush(stdin);
scanf("%d",&G->arcnum);
printf("请输入所有顶点\n");
for(i=0;i<G->vexnum;i++){
fflush(stdin);//清空输入缓存区，否则会将上次输入结束后的回车符当成一个字符存入。下面同理
scanf("%c",&G->vexs[i]);//将所有的顶点读入数组vexs中进行存储
}
for(i=0;i<G->vexnum;i++){//进行初始化，赋初值
for(j=0;j<G->vexnum;j++) {
G->arcs[i][j].adj=INFINITY;
G->arcs[i][j].info=NULL;
}
}
char v1,v2;
printf("请输入弧的两个顶点和权值\n");
for(k=0;k<G->arcnum;k++){//对矩阵进行赋值
fflush(stdin);
scanf("%c%c%d",&v1,&v2,&w);
i=LocateVex(*G,v1);
j=LocateVex(*G,v2);
G->arcs[i][j].adj=w;
//不输入信息，没有.info
G->arcs[j][i].adj=w;//对称
}
G->kind=UDN;
return OK;
}
Display
void Display(MGraph G)//打印矩阵
{
int i=0,j=0;
for (i = 0; i < G.vexnum; ++i)
for (j = 0; j < G.vexnum; ++j)
{
printf("%d ", G.arcs[i][j].adj);
if ((j + 1) % G.vexnum == 0)
printf("\n");
}
}
Destory
Status Destory(MGraph *G){//销毁图
int i=0,j=0;
for(i=0;i<G->vexnum;i++){
for(j=0;j<G->vexnum;j++) {
G->arcs[i][j].adj=INFINITY;
G->arcs[i][j].info=NULL;
}
}
G->vexnum=0;
G->arcnum=0;
}
GetVex
Status GetVex(MGraph G,VertexType v){//返回图中顶点的值
int i=0;
for (i=0; i<G.vexnum; i++){
if (G.vexs[i]==v)
return i;
}
return False;
}
PutVex
Status PutVex(MGraph *G,VertexType v,VertexType value){//将图中的顶点v改为顶点value
int i=0;
for (i=0; i<G->vexnum; i++){
if (G->vexs[i]==v)
G->vexs[i]=value;
return OK;
}
return False;
}
FirstAdjVex
Status FirstAdjVex(MGraph G,VertexType v){//找出v的下一个邻接顶点
int i=0,j=0;
i=LocateVex(G,v);
for(j=0;j<G.vexnum;j++){
if(G.arcs[i][j].adj!=INFINITY){//从头开始在存储顶点的数组寻找下一个v的邻接顶点
return j;
}
}
return Fail;
}
NextAdjVex
Status NextAdjVex(MGraph G,VertexType v,VertexType w){//找出v相对于w的下一个邻接顶点
int i=0,j=0,n=0;
i=LocateVex(G,v);
j=LocateVex(G,w);
for(n=j+1;n<G.vexnum;n++){//从w的位置开始在存储顶点的数组寻找下一个v的邻接顶点
if(G.arcs[i][n].adj!=INFINITY){
return n;
}
}
return Fail;
}
InsertVex
Status InsertVex(MGraph *G,VertexType v){//插入顶点v
int i=0;
G->vexnum++;
//更改存储顶点的数组
G->vexs[G->vexnum-1]=v;
//更改矩阵
for(i=0;i<G->vexnum;i++){//为矩阵最外层行、列的元素赋初始值
G->arcs[G->vexnum-1][i].adj=0;
G->arcs[G->vexnum-1][i].info=NULL;
G->arcs[i][G->vexnum-1].adj=0;
G->arcs[i][G->vexnum-1].info=NULL;
}
return OK;
}
DeleteVex
Status DeleteVex(MGraph *G,VertexType v){//删除顶点v
int i=0,j=0,temp=0;
i=LocateVex(*G,v);
temp=i;
//更改存储顶点的数组
for(temp;temp<G->vexnum;temp++){
G->vexs[temp]=G->vexs[temp+1];//存储顶点的数组中向前移一位，覆盖要删除的顶点
}
G->vexnum--;
//更改矩阵
for(j=0;j<G->vexnum+1;j++){//使矩阵中靠后位置的顶点前移，覆盖被删除的顶点
for(i;i<G->vexnum+1;i++){
G->arcs[j][i]=G->arcs[j][i+1];
G->arcs[i][j]=G->arcs[i+1][j];
}
}
for(i=0;i<G->vexnum;i++){//上一步前移完成后矩阵的最外层的行、列的数据应被清除
G->arcs[G->vexnum][i].adj=0;
G->arcs[G->vexnum][i].info=NULL;
G->arcs[i][G->vexnum].adj=0;
G->arcs[i][G->vexnum].info=NULL;
}
return OK;
}
InsertArc
Status InsertArc(MGraph *G,VertexType v,VertexType w,VRType value){//增加顶点v和w之间的弧，权值为value
int i=0,j=0;
i=LocateVex(*G,v);
j=LocateVex(*G,w);
G->arcs[i][j].adj=value;
G->arcs[i][j].info=NULL;
G->arcs[j][i].adj=value;
G->arcs[j][i].info=NULL;
return OK;
}
DeleteArc
Status DeleteArc(MGraph *G,VertexType v,VertexType w){//增加顶点v和w之间的弧，权值为value
int i=0,j=0;
i=LocateVex(*G,v);
j=LocateVex(*G,w);
G->arcs[i][j].adj=INFINITY;
G->arcs[i][j].info=NULL;
G->arcs[j][i].adj=INFINITY;
G->arcs[j][i].info=NULL;
return OK;
}
定义全局变量
int visited[MAX_VERTEX_NUM];//在DFS和BFS中用到
DFS
void DFS(MGraph G,int n){//从第n个顶点出发深度优先遍历图G
int i;
printf("%c", G.vexs[n]);
visited[n]=True;
for(i=0;i<G.vexnum;i++){
if(G.arcs[n][i].adj!=INFINITY&&visited[i]==False)
DFS(G,i);
}
}
DFSTraverse
void DFSTraverse(MGraph G){//对图G进行深度优先遍历
int i=0,n=0;
for(i=0;i<G.vexnum;i++) visited[i]=False; //初始化标志数组
for(n=0;n<G.vexnum;n++){//因为图可能是非联通图，递归访问下一个顶点时可能会中断，因此需要从每一个顶点开始做深度优先遍历
if(visited[n]==False)//判断是否被访问过,未被访问过时访问
DFS(G,n);
}
}
BFS
void BFS(MGraph G,int n){//从第n个顶点出发广度优先遍历图G
int que[MAX_VERTEX_NUM],front=0,rear=0;
int i=0,w=0;
printf("%c", G.vexs[n]);
visited[n]=True;//访问
rear=(rear+1)%MAX_VERTEX_NUM;//入队
que[rear]=n;
while(front!=rear){//队列不空时
front=(front+1)%MAX_VERTEX_NUM;//出队
i=que[front];
for(w=FirstAdjVex(G,G.vexs[i]);w!=Fail;w=NextAdjVex(G,G.vexs[i],G.vexs[w])){
if(visited[w]==False){
visited[w]=True;
printf("%c", G.vexs[w]);//访问
rear=(rear+1)%MAX_VERTEX_NUM;//入队
que[rear]=w;
}
}
}
}
BFSTraverse
void BFSTraverse(MGraph G){//对图G进行广度优先遍历
int i=0,n=0;
for(i=0;i<G.vexnum;i++) visited[i]=False; //初始化标志数组
for(n=0;n<G.vexnum;n++){//因为图可能是非联通图，递归访问下一个顶点时可能会中断，因此需要从每一个顶点开始做深度优先遍历
if(visited[n]==False)//判断是否被访问过,未被访问过时访问
BFS(G,n);
}
}
输入样例
很多函数被我注释掉了，需要使用的话自行取消注释。
int main(void){
MGraph G;
CreateGraph(&G);
//Destory(&G);
Display(G);
//GetVex(G,'a');
//FirstAdjVex(G,'c');
//NextAdjVex(G,'b','c');
//InsertArc(&G,'d','e',9);
//DeleteArc(&G,'d','e');
//Display(G);
printf("DFS:\n");
DFSTraverse(G);
printf("\nBFS:\n");
BFSTraverse(G);
}
输入：
5
6
a
b
c
d
e
ab1
ad2
bc3
be4
cd5
ce6
输出结果
