【数据结构】无向图创建邻接矩阵、深度优先遍历和广度优先遍历（C语言版）

无向图创建邻接矩阵、深度优先遍历和广度优先遍历

• 一、概念解析：
• • （1）无向图：
  • （2）邻接矩阵：
  • 二、创建邻接矩阵：
  • 三、深度遍历、广度遍历
  • • （1）深度遍历概念：
    • （2）广度遍历概念：
    • 四、实例展示

      一、概念解析：

      （1）无向图：

      假设图G由两个集合V和E组成，记为G={V , E}。其中V是顶点的有限集合，E是连接V中两个不同顶点的边的有限集合。如果E中的顶点对是有序的，即E中的每条边都是有方向的，则称G是有向图。如果顶点对是无序的，则称G是无向图

      （2）邻接矩阵：

      邻接矩阵主要由：二维数组 实现

      如图

      转换成邻接矩阵为：

      二、创建邻接矩阵：

      基本每一步都有注释，详细观看，建议画图理解

      代码如下：

      #define MAXSIZE 100 //邻接矩阵 typedef struct Matrix{int V_Data;//顶点数据域 int E_Data;//边数数据域int Node[MAXSIZE];//存放顶点数据，也就是顶点表 int Weight[MAXSIZE][MAXSIZE]; //存放权重，为矩阵中两点有边的标记符号 }MaTrix,*MATRIX;//邻接矩阵数据结构体 typedef struct Edge{int v1;//用来存放第一个顶点 int v2;//用来存放第二个顶点int weight;//用来存放两点之间的标记符，即为权 }*EDGE;//******************** 邻接矩阵*******************////邻接矩阵、顶点和边初始化 void Init_Matrix(MATRIX S,int Vertex){S->E_Data = 0;//初始化为0条边 S->V_Data = Vertex;//初始化顶点数 int i,j;for(i=0;ifor(j=0;jS-Weight[i][j] = 0;}} }//开始插入边的权重，即为两个顶点之间边的标记符void InSerData(MATRIX S,EDGE E){//将输入的顶点v1、v2之间的边，用权作为标记，在矩阵中表示//这里是无向图，所以边没有方向，需要做标记两次（为v1-v2和v2-v1） S-Weight[E->v1][E->v2] = E->weight; S->Weight[E->v2][E->v1] = E->weight; } //开始插入数据 void InSerEdge_Data(MATRIX S,int edge,int V){int i,j;if(edge>0)//边数大于0的时候才插入数据 {printf("请输入顶点和权重(空格分隔!)\n");for(i=0;iEDGE E;//分配内存，接受顶点v1,v2和权重（标记符）E = (EDGE)malloc(sizeof(struct Edge));scanf("%d %d %d",&(E-v1),&(E->v2),&(E->weight));if(E->v1 ==E->v2){printf("无向图邻接矩阵对角线为0,输入错误,结束运行\n");exit(-1); }InSerData(S,E);}printf("请输入要定义的顶点，填入顶点表中: \n");for(j=0;jscanf("%d",&(S-Node[j]));}}else{printf("输入的边数错误"); } } 

      三、深度遍历、广度遍历

      （1）深度遍历概念：

      定义的结构体、数组可看上面代码

      深度遍历代码解析：

      //*****************深度优先遍历算法—邻接矩阵 *****************//void DFS_Begin(MATRIX P,int k,int V){int i;flag[k] = 1;//标记当前顶点，表示已经遍历过printf("%d ",P->Node[k]);//输出当前顶点 for(i=0;iif(!flag[i] && P-Weight[k][i] != 0)//如果当前顶点的邻近点存在，且没有遍历过 {//则继续递归遍历 DFS_Begin(P,i,V);//递归遍历当前顶点的邻近点 }} }void Init_DFSMatrix(MATRIX P,int V){int i;//初始化标记符数组，全为0 for(i=0;iflag[i] = 0;}for(i=0;iif(!flag[i])//排除遇到已经遍历的顶点DFS_Begin(P,i,V);//开始深度遍历} putchar('\n');}int data[MAXSIZE];//队列大小 int head;//队头 int wei;//队尾 }Queue; //*****************队列 *************************************////队列初始化 void InitQueue(Queue *q){q-head= 0;//初始化队头、队尾 q-wei = 0;} //判断队列是否为空int EmptyQueue(Queue *q){if(q->head == q->wei)return 1;else{return 0;}} //入队void PushQueue(Queue *q,int t){if((q->wei+1)%MAXSIZE == q->head)//说明队列已经满了return;else{q->data[q->wei] = t;q->wei = (q->wei +1)%MAXSIZE;//队尾后移 } } //出队void PopQueue(Queue *q,int *x){if(q->wei == q->head)//出队完毕 return;else{ *x = q->data[q->head];q->head = (q->head + 1)%MAXSIZE; //队头后移}}  //***************** 广度优先搜索算法—邻接矩阵 ****************//void Init_Bfs(MATRIX S,int V){int i,j;int k; Queue Q;for(i=0;iVist[i] = 0;//初始化标记符 }InitQueue(&Q);//队列初始化 for (i = 0; i Weight[i][j] != 0){Vist[j] = 1;//与之连接的顶点作上标记，便于后序顶点跳过相同的遍历 printf("%d ", S->Node[j]);//输出与之相邻连接的顶点 PushQueue(&Q, j);//让与之连接的顶点其位置入队 }}}}}} 

      四、实例展示

      注意：这里存入数据时，坐标点以原点（0,0）为起点开始！

      以这个图为样例展示：

      全部代码：

      #include#include#define MAXSIZE 100 //深度遍历标记符int flag[MAXSIZE]; //邻接矩阵 //广度优先遍历标记符 int Vist[MAXSIZE]; //邻接矩阵//******************** 队列 *****************//typedef struct Queue{int data[MAXSIZE];//队列大小 int head;//队头 int wei;//队尾 }Queue; //邻接矩阵 typedef struct Matrix{int V_Data;//顶点数据域 int E_Data;//边数数据域int Node[MAXSIZE];//存放顶点数据，也就是顶点表 int Weight[MAXSIZE][MAXSIZE]; //存放权重，为矩阵中两点有边的标记符号 }MaTrix,*MATRIX;//邻接矩阵数据结构体 typedef struct Edge{int v1;//用来存放第一个顶点 int v2;//用来存放第二个顶点int weight;//用来存放两点之间的标记符，即为权 }*EDGE;//******************** 邻接矩阵*******************////邻接矩阵、顶点和边初始化 void Init_Matrix(MATRIX S,int Vertex){S->E_Data = 0;//初始化为0条边 S->V_Data = Vertex;//初始化顶点数 int i,j;for(i=0;ifor(j=0;jS-Weight[i][j] = 0;}} }//开始插入边的权重，即为两个顶点之间边的标记符void InSerData(MATRIX S,EDGE E){//将输入的顶点v1、v2之间的边，用权作为标记，在矩阵中表示//这里是无向图，所以边没有方向，需要做标记两次（为v1-v2和v2-v1） S-Weight[E->v1][E->v2] = E->weight; S->Weight[E->v2][E->v1] = E->weight; } //*****************深度优先遍历算法—邻接矩阵 *****************//void DFS_Begin(MATRIX P,int k,int V){int i;flag[k] = 1;//标记当前顶点，表示已经遍历过printf("%d ",P->Node[k]);//输出当前顶点 for(i=0;iif(!flag[i] && P-Weight[k][i] != 0)//如果当前顶点的邻近点存在，且没有遍历过 {//则继续递归遍历 DFS_Begin(P,i,V);//递归遍历当前顶点的邻近点 }} }void Init_DFSMatrix(MATRIX P,int V){int i;//初始化标记符数组，全为0 for(i=0;iflag[i] = 0;}for(i=0;iif(!flag[i])//排除遇到已经遍历的顶点DFS_Begin(P,i,V);//开始深度遍历} putchar('\n');}//*****************队列 *************************************////队列初始化 void InitQueue(Queue *q){q-head= 0;//初始化队头、队尾 q-wei = 0;} //判断队列是否为空int EmptyQueue(Queue *q){if(q->head == q->wei)return 1;else{return 0;}} //入队void PushQueue(Queue *q,int t){if((q->wei+1)%MAXSIZE == q->head)//说明队列已经满了return;else{q->data[q->wei] = t;q->wei = (q->wei +1)%MAXSIZE;//队尾后移 } } //出队void PopQueue(Queue *q,int *x){if(q->wei == q->head)//出队完毕 return;else{ *x = q->data[q->head];q->head = (q->head + 1)%MAXSIZE; //队头后移}}  //***************** 广度优先搜索算法—邻接矩阵 ****************//void Init_Bfs(MATRIX S,int V){int i,j;int k; Queue Q;for(i=0;iVist[i] = 0;//初始化标记符 }InitQueue(&Q);//队列初始化 for (i = 0; i Weight[i][j] != 0){Vist[j] = 1;//与之连接的顶点作上标记，便于后序顶点跳过相同的遍历 printf("%d ", S->Node[j]);//输出与之相邻连接的顶点 PushQueue(&Q, j);//让与之连接的顶点其位置入队 }}}}}} //初始化顶点个数 int Init_Vertex(){int Vertex; printf("请输入顶点个数: ");scanf("%d",&Vertex);return Vertex;}//初始化边的数量 int Init_Edge(){int edge;printf("请输入边的数量: ");scanf("%d",&edge);return edge;} //开始插入数据 void InSerEdge_Data(MATRIX S,int edge,int V){int i,j;if(edge>0)//边数大于0的时候才插入数据 {printf("请输入顶点和权重(空格分隔!)\n");for(i=0;iEDGE E;//分配内存，接受顶点v1,v2和权重（标记符）E = (EDGE)malloc(sizeof(struct Edge));scanf("%d %d %d",&(E-v1),&(E->v2),&(E->weight));if(E->v1 ==E->v2){printf("无向图邻接矩阵对角线为0,输入错误,结束运行\n");exit(-1); }InSerData(S,E);}printf("请输入要定义的顶点，填入顶点表中: \n");for(j=0;jscanf("%d",&(S-Node[j]));}}else{printf("输入的边数错误"); } } //打印无向图邻接矩阵 void Show_Matrix(MATRIX p,int Vertex){int i,j;for(i=0;ifor(j=0;jprintf("%4d",p-Weight[i][j]);//打印邻接矩阵 }putchar('\n');//换行 }}int main(){int val;int Vertex;int edge;MATRIX p;//邻接矩阵头节点指针//创建无向图邻接矩阵 Vertex = Init_Vertex();edge = Init_Edge();p = (MATRIX)malloc(sizeof(MaTrix));//分配内存空间 p-V_Data = Vertex;//记录顶点个数 p->E_Data = edge;//记录边的个数 Init_Matrix(p,Vertex);//初始化邻接矩阵 InSerEdge_Data(p,edge,Vertex);//插入数据 //打印无向图的邻接矩阵 printf("无向图邻接矩阵如下:");printf("\n----------------------------------\n\n");Show_Matrix(p,Vertex);printf("\n----------------------------------\n");//深度优先遍历—邻接矩阵printf("深度遍历—邻接矩阵结果为:\n");Init_DFSMatrix(p,Vertex);//广度优先遍历—邻接矩阵printf("广度优先遍历—邻接矩阵结果为: \n");Init_Bfs(p,Vertex);return 0;} 

      结果图：