怎样根据邻接矩阵写出深度优先遍历,无向图的广度优先遍历序列
有向图制作邻接矩阵、深度优先遍历、广度优先遍历(1，概念分析)无向图) 2、邻接矩阵) 2、邻接矩阵的制作) 3、深度遍历、广度遍历) 1、深度遍历的概念) 2、广度遍历
一、概念解析： (1)无向图：
图g由两个集合v和e组成，表示为G={V，E}。 在这里，v是顶点的有限集合，e是连接v的不同的2个顶点的边的有限集合。 如果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； /******/*邻接矩阵* * * * * * * * * * * * * * * * *//邻接矩阵、顶点和边的初始化voidinit_matrix () mattrix //0 //初始化顶点数int i，j； for(I=0； iVertex； I ) for(j=0； jVertex； j({s-Weight[I][j]=0； }//开始插入边的权重是用权重标记作为两个顶点之间的边的标记的voidinserdata(matrixs，EDGE E )//输入的顶点v1，v2之间的边，用矩阵(//这里是无向图S-Weight[E-v2][E-v1]=E-weight； //数据voidinseredge_data(matrixs，int edge，int V ) {int i，j； 仅当if(edge0)//边数大于0时插入数据({printf )输入顶点和权重(以空格分隔！ (n )； for(I=0； iedge； I ) {EDGE E； //分配内存，顶点v1，v2和权重(令牌) e=) edge ) malloc ) sizeof ) structedge )； scanf () %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； jV； j ) Scanf('%d '，) S-Node[j] )； }}else{printf ('输入的边数错误')； (三、导线测量、导线测量)1)导线测量概念：
定义的结构体、数组可以看到上面的代码。
深度遍历代码解析：
/*******/voidDFS_begin(matrixp，int k，int V )相邻矩阵(******/voidDFS_begin ) matrixp，int k，int v flant v //标记当前顶点，表示已遍历printf('%d”，P-Node[k] )。 //输出当前顶点for (I=0； ； I ) if (！ flag[i] P-Weight[k][i]！=0//存在当前顶点的附近点，且没有遍历{//时，继续递归遍历DFS_begin(p，I，v )。 //递归遍历当前顶点附近}}voidinit_DFSmatrix(matrixp，int V ) intI； //初始化标志数组，全部为0for(I=0； ； I ) {flag[i]=0； (for ) I=0； ； 检查是否遍历到I(//每个顶点) if )！ flag[i] )//除非遇到扫描的顶点DFS_begin(p，I，v )； //开始深度遍历putchar (((n )； () )
2）广度遍历概念：
这里使用到了链队列（也可以使用数组队列，看个人想法），可以看我之前的博文有讲：
//******************** 队列 *****************//typedef struct Queue{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;i<V;i++){Vist[i] = 0;//初始化标记符 }InitQueue(&Q);//队列初始化 for (i = 0; i < V; i++){if (!Vist[i])//判断以这个顶点为基准，有连接的其他顶点 {Vist[i] = 1;//标记遍历的这个顶点 printf("%d ", S->Node[i]);PushQueue(&Q, i);//入队 while (!EmptyQueue(&Q))//队列中还有数据，说明这个顶点连接的其他顶点还没有遍历完 {PopQueue(&Q,&i);//出队 for (j = 0; j < V; j++){//以这个顶点为基准，遍历其他连接的顶点 if (!Vist[j] && S->Weight[i][j] != 0){Vist[j] = 1;//与之连接的顶点作上标记，便于后序顶点跳过相同的遍历 printf("%d ", S->Node[j]);//输出与之相邻连接的顶点 PushQueue(&Q, j);//让与之连接的顶点其位置入队 }}}}}} 四、实例展示
注意：这里存入数据时，坐标点以原点（0,0）为起点开始！
以这个图为样例展示：
全部代码：
#include<stdio.h>#include<stdlib.h>#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;i<Vertex;i++){for(j=0;j<Vertex;j++){S->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;i<V;i++){if(!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;i<V;i++){flag[i] = 0;}for(i=0;i<V;i++)//每个顶点都要检查是否遍历到 {if(!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;i<V;i++){Vist[i] = 0;//初始化标记符 }InitQueue(&Q);//队列初始化 for (i = 0; i < V; i++){if (!Vist[i])//判断以这个顶点为基准，有连接的其他顶点 {Vist[i] = 1;//标记遍历的这个顶点 printf("%d ", S->Node[i]);PushQueue(&Q, i);//入队 while (!EmptyQueue(&Q))//队列中还有数据，说明这个顶点连接的其他顶点还没有遍历完 {PopQueue(&Q,&i);//出队 for (j = 0; j < V; j++){//以这个顶点为基准，遍历其他连接的顶点 if (!Vist[j] && S->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;i<edge;i++){EDGE 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;j<V;j++){scanf("%d",&(S->Node[j]));}}else{printf("输入的边数错误"); } } //打印无向图邻接矩阵 void Show_Matrix(MATRIX p,int Vertex){int i,j;for(i=0;i<Vertex;i++){for(j=0;j<Vertex;j++){printf("%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;}
结果图：