从零开始养成算法·篇十五：图的遍历

图的遍历主要就是这两种遍历思想，深度优先使用递归方式，需要栈结构辅助实现。广度优先需要使用队列结构辅助实现。在遍历过程中可以看出，对于连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点，但对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。

一、深度遍历

1 算法思想

深度优先思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

2 算法特点

深度优先是一个递归的过程。首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。若不能继续前进，则回退一步再前进，若回退一步仍然不能前进，则连续回退至可以前进的位置为止。重复此过程，直到所有与选定点相通的所有顶点都被遍历。
深度优先是递归过程，带有回退操作，因此需要使用栈存储访问的路径信息。当访问到的当前顶点没有可以前进的邻接顶点时，需要进行出栈操作，将当前位置回退至出栈元素位置。

3 图解过程
3.1 无向图深度优先搜索
以图中所示无向图说明深度优先搜索遍历过程。


1.jpeg

（1）首先选取顶点A为起始点，输出A顶点信息，且将A入栈，并标记A为已访问顶点。
（2）A的邻接顶点有C、D、F，从中任意选取一个顶点前进。这里我们选取C顶点为前进位置顶点。输出C顶点信息，将C入栈，并标记C为已访问顶点。当前位置指向顶点C。
（3）顶点C的邻接顶点有A、D和B，此时A已经标记为已访问顶点，因此不能继续访问。从B或者D中选取一个顶点前进，这里我们选取B顶点为前进位置顶点。输出B顶点信息，将B入栈，标记B顶点为已访问顶点。当前位置指向顶点B。
（4）顶点B的邻接顶点只有C、E，C已被标记，不能继续访问，因此选取E为前进位置顶点，输出E顶点信息，将E入栈，标记E顶点，当前位置指向E。
（5）顶点E的邻接顶点均已被标记，此时无法继续前进，则需要进行回退。将当前位置回退至顶点B，回退的同时将E出栈。
（6）顶点B的邻接顶点也均被标记，需要继续回退，当前位置回退至C，回退同时将B出栈。
（7）顶点C可以前进的顶点位置为D，则输出D顶点信息，将D入栈，并标记D顶点。当前位置指向顶点D。
（8）顶点D没有前进的顶点位置，因此需要回退操作。将当前位置回退至顶点C，回退同时将D出栈。
（9）顶点C没有前进的顶点位置，继续回退，将当前位置回退至顶点A，回退同时将C出栈。
（10）顶点A前进的顶点位置为F，输出F顶点信息，将F入栈，并标记F。将当前位置指向顶点F。
（11）顶点F的前进顶点位置为G，输出G顶点信息，将G入栈，并标记G。将当前位置指向顶点G。
（12）顶点G没有前进顶点位置，回退至F。当前位置指向F，回退同时将G出栈。
（13）顶点F没有前进顶点位置，回退至A，当前位置指向A，回退同时将F出栈。
（14）顶点A没有前进顶点位置，继续回退，栈为空，则以A为起始的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。
（15）采用深度优先搜索遍历顺序为A->C->B->E->D->F->G。

3.2 有向图深度优先搜索
以图中所示有向图说明深度优先搜索遍历过程。


2.jpeg

（1）以顶点A为起始点，输出A，将A入栈，并标记A。当前位置指向A。
（2）以A为尾的边只有1条，且边的头为顶点B，则前进位置为顶点B，输出B，将B入栈，标记B。当前位置指向B。
（3）顶点B可以前进的位置有C与F，选取F为前进位置，输出F，将F入栈，并标记F。当前位置指向F。
（4）顶点F的前进位置为G，输出G，将G入栈，并标记G。当前位置指向G。
（5）顶点G没有可以前进的位置，则回退至F，将F出栈。当前位置指向F。
（6）顶点F没有可以前进的位置，继续回退至B，将F出栈。当前位置指向B。
（7）顶点B可以前进位置为C和E，选取E，输出E，将E入栈，并标记E。当前位置指向E。
（8）顶点E的前进位置为D，输出D，将D入栈，并标记D。当前位置指向D。
（9）顶点D的前进位置为C，输出C，将C入栈，并标记C。当前位置指向C。
（10）顶点C没有前进位置，进行回退至D，回退同时将C出栈。
（11）继续执行此过程，直至栈为空，以A为起始点的遍历过程结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。

4 算法分析

当图采用邻接矩阵存储时，由于矩阵元素个数为n2，因此时间复杂度就是O(n2)。
当图采用邻接表存储时，邻接表中只是存储了边结点(e条边，无向图也只是2e个结点)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)。

5 邻接矩阵的深度优先遍历

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef struct
{
   VertexType vexs[MAXVEX]; /* 顶点表 */
   EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
   int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;

/*4.1 构建一个邻接矩阵*/
void CreateMGraph(MGraph *G)
{
   int i, j;
   
   //1. 确定图的顶点数以及边数
   G->numEdges=15;
   G->numVertexes=9;
   
   /*2.读入顶点信息，建立顶点表 */
   G->vexs[0]='A';
   G->vexs[1]='B';
   G->vexs[2]='C';
   G->vexs[3]='D';
   G->vexs[4]='E';
   G->vexs[5]='F';
   G->vexs[6]='G';
   G->vexs[7]='H';
   G->vexs[8]='I';
   
   /*3. 初始化图中的边表*/
   for (i = 0; i < G->numVertexes; I++)
   {
       for ( j = 0; j < G->numVertexes; j++)
       {
           G->arc[i][j]=0;
       }
   }
   
   /*4.将图中的连接信息输入到边表中*/
   G->arc[0][1]=1;
   G->arc[0][5]=1;
   
   G->arc[1][2]=1;
   G->arc[1][8]=1;
   G->arc[1][6]=1;
   
   G->arc[2][3]=1;
   G->arc[2][8]=1;
   
   G->arc[3][4]=1;
   G->arc[3][7]=1;
   G->arc[3][6]=1;
   G->arc[3][8]=1;
   
   G->arc[4][5]=1;
   G->arc[4][7]=1;
   
   G->arc[5][6]=1;
   
   G->arc[6][7]=1;
   
   /*5.无向图是对称矩阵.构成对称*/
   for(i = 0; i < G->numVertexes; I++)
   {
       for(j = i; j < G->numVertexes; j++)
       {
           G->arc[j][i] =G->arc[i][j];
       }
   }
}

/*4.2 DFS遍历*/
Boolean visited[MAXVEX]; /* 访问标志的数组 */
//1. 标识顶点是否被标记过;
//2. 选择从某一个顶点开始(注意:非连通图的情况)
//3. 进入递归,打印i点信息,标识; 边表
//4. [i][j] 是否等于1,没有变遍历过visted
void DFS(MGraph G,int i){
   //1.
   visited[i] = TRUE;
   printf("%c",G.vexs[I]);
   
   //2.0~numVertexes
   for(int j = 0; j < G.numVertexes;j++){
       if(G.arc[i][j] == 1 && !visited[j])
           DFS(G, j);
   }
}

void DFSTravese(MGraph G){
   //1.初始化
   for(int i=0;i<G.numVertexes;i++){
       visited[i] = FALSE;
   }
   
   //2.某一个顶点
   for(int i = 0;i<G.numVertexes;i++){
       if(!visited[I]){
           DFS(G, i);
       }
   }
}

6 邻接表的深度优先遍历

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

/* 邻接矩阵结构 */
typedef struct
{
   VertexType vexs[MAXVEX]; /* 顶点表 */
   EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵,可看作边表 */
   int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;

/* 邻接表结构****************** */
typedef struct EdgeNode /* 边表结点 */
{
   int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
   int weight;        /* 用于存储权值,对于非网图可以不需要 */
   struct EdgeNode *next; /* 链域,指向下一个邻接点 */
}EdgeNode;

typedef struct VertexNode /* 顶点表结点 */
{
   int in;    /* 顶点入度 */
   char data; /* 顶点域,存储顶点信息 */
   EdgeNode *firstedge;/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];

typedef struct
{
   AdjList adjList;
   int numVertexes,numEdges; /* 图中当前顶点数和边数 */
}graphAdjList,*GraphAdjList;

/*4.1 构建一个邻接矩阵*/
void CreateMGraph(MGraph *G)
{
   int i, j;
   
   //1. 确定图的顶点数以及边数
   G->numEdges=15;
   G->numVertexes=9;
   
   /*2.读入顶点信息，建立顶点表 */
   G->vexs[0]='A';
   G->vexs[1]='B';
   G->vexs[2]='C';
   G->vexs[3]='D';
   G->vexs[4]='E';
   G->vexs[5]='F';
   G->vexs[6]='G';
   G->vexs[7]='H';
   G->vexs[8]='I';
   
   /*3. 初始化图中的边表*/
   for (i = 0; i < G->numVertexes; I++)
   {
       for ( j = 0; j < G->numVertexes; j++)
       {
           G->arc[i][j]=0;
       }
   }
   
   /*4.将图中的连接信息输入到边表中*/
   G->arc[0][1]=1;
   G->arc[0][5]=1;
   
   G->arc[1][2]=1;
   G->arc[1][8]=1;
   G->arc[1][6]=1;
   
   G->arc[2][3]=1;
   G->arc[2][8]=1;
   
   G->arc[3][4]=1;
   G->arc[3][7]=1;
   G->arc[3][6]=1;
   G->arc[3][8]=1;
   
   G->arc[4][5]=1;
   G->arc[4][7]=1;
   
   G->arc[5][6]=1;
   
   G->arc[6][7]=1;
   
   /*5.无向图是对称矩阵.构成对称*/
   for(i = 0; i < G->numVertexes; I++)
   {
       for(j = i; j < G->numVertexes; j++)
       {
           G->arc[j][i] =G->arc[i][j];
       }
   }
}

/*4.2 利用邻接矩阵构建邻接表*/
void CreateALGraph(MGraph G,GraphAdjList *GL){
   
   //1.创建邻接表,并且设计邻接表的顶点数以及弧数
   *GL = (GraphAdjList)malloc(sizeof(graphAdjList));
   (*GL)->numVertexes = G.numVertexes;
   (*GL)->numEdges = G.numEdges;
   
   //2. 从邻接矩阵中将顶点信息输入
   for (int i = 0; i < G.numVertexes; i++) {
       //顶点入度为0
       (*GL)->adjList[i].in = 0;
       //顶点信息
       (*GL)->adjList[i].data = G.vexs[i];
       //顶点边表置空
       (*GL)->adjList[i].firstedge = NULL;
   }
   
   //3. 建立边表
   EdgeNode *e;
   for (int i = 0; i < G.numVertexes; i++) {
       for (int j = 0; j < G.numVertexes; j++) {
           if (G.arc[i][j] == 1) {
            
               //创建边表中的邻近结点 i->j
               e = (EdgeNode *)malloc(sizeof(EdgeNode));
               //邻接序号为j
               e->adjvex = j;
               //将当前结点的指向adjList[i]的顶点边表上
               e->next = (*GL)->adjList[i].firstedge;
               (*GL)->adjList[i].firstedge = e;
               //顶点j 上的入度++;
               (*GL)->adjList[j].in++;
               
//                //创建边表中的邻近结点 j->i
//                e = (EdgeNode *)malloc(sizeof(EdgeNode));
//                //邻接序号为j
//                e->adjvex = I;
//                //将当前结点的指向adjList[i]的顶点边表上
//                e->next = (*GL)->adjList[j].firstedge;
//                (*GL)->adjList[j].firstedge = e;
//                //顶点j 上的入度++;
//                (*GL)->adjList[i].in++;
           }
       }
   }
}


Boolean visited[MAXSIZE]; /* 访问标志的数组 */
/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i)
{
   EdgeNode *p;
   visited[i] = TRUE;
   
   //2.打印顶点 A
   printf("%c ",GL->adjList[i].data);
   
   p = GL->adjList[i].firstedge;
   
   //3.
   while (p) {
       if(!visited[p->adjvex])
           DFS(GL,p->adjvex);
       
       p = p->next;
   }
   
}

/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList GL)
{
   //1. 将访问记录数组默认置为FALSE
   for (int i = 0; i < GL->numVertexes; i++) {
       /*初始化所有顶点状态都是未访问过的状态*/
       visited[i] = FALSE;
   }

   //2. 选择一个顶点开始DFS遍历. 例如A
   for(int i = 0; i < GL->numVertexes; I++)
       //对未访问过的顶点调用DFS, 若是连通图则只会执行一次.
       if(!visited[I])
           DFS(GL, i);
}

二、广度遍历

1 算法思想

广度优先思想：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

2 算法特点

广度优先类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先时需要使用队列存储顶点信息。

3 图解过程
3.1 无向图的广度优先搜索


1.jpeg

（1）选取A为起始点，输出A，A入队列，标记A，当前位置指向A。
（2）队列头为A，A出队列。A的邻接顶点有B、E，输出B和E，将B和E入队，并标记B、E。当前位置指向A。
（3）队列头为B，B出队列。B的邻接顶点有C、D，输出C、D，将C、D入队列，并标记C、D。当前位置指向B。
（4）队列头为E，E出队列。E的邻接顶点有D、F，但是D已经被标记，因此输出F，将F入队列，并标记F。当前位置指向E。
（5）队列头为C，C出队列。C的邻接顶点有B、D，但B、D均被标记。无元素入队列。当前位置指向C。
（6）队列头为D，D出队列。D的邻接顶点有B、C、E，但是B、C、E均被标记，无元素入队列。当前位置指向D。
（7）队列头为F，F出队列。F的邻接顶点有G、H，输出G、H，将G、H入队列，并标记G、H。当前位置指向F。
（8）队列头为G，G出队列。G的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向G。
（9）队列头为H，H出队列。H的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向H。
（10）队列空，则以A为起始点的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。

3.2 有向图的广度优先搜索


2.jpeg

（1）选取A为起始点，输出A，将A入队列，标记A。
（2）队列头为A，A出队列。以A为尾的边有两条，对应的头分别为B、C，则A的邻接顶点有B、C。输出B、C，将B、C入队列，并标记B、C。
（3）队列头为B，B出队列。B的邻接顶点为C，C已经被标记，因此无新元素入队列。
（4）队列头为C，C出队列。C的邻接顶点有E、F。输出E、F，将E、F入队列，并标记E、F。
（5）队列头为E，E出队列。E的邻接顶点有G、H。输出G、H，将G、H入队列，并标记G、H。
（6）队列头为F，F出队列。F无邻接顶点。
（7）队列头为G，G出队列。G无邻接顶点。
（8）队列头为H，H出队列。H邻接顶点为E，但是E已被标记，无新元素入队列。
（9）队列为空，以A为起始点的遍历过程结束，此时图中仍有D未被访问，则以D为起始点继续遍历。选取D为起始点，输出D，将D入队列，标记D。
（10）队列头为D，D出队列，D的邻接顶点为B，B已被标记，无新元素入队列。
（11）队列为空，且所有元素均被访问，广度优先搜索遍历过程结束。广度优先搜索的输出序列为：A->B->E->C->D->F->G->H。

3.4 算法分析

假设图有V个顶点，E条边，广度优先搜索算法需要搜索V个节点，时间消耗是O(V)，在搜索过程中，又需要根据边来增加队列的长度，于是这里需要消耗O(E)，总得来说，效率大约是O(V+E)。

5 邻接矩阵的广度优先遍历

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef struct
{
   VertexType vexs[MAXVEX]; /* 顶点表 */
   EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
   int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;

/*4.1 构建一个邻接矩阵*/
void CreateMGraph(MGraph *G)
{
   int i, j;
   
   //1. 确定图的顶点数以及边数
   G->numEdges=15;
   G->numVertexes=9;
   
   /*2.读入顶点信息，建立顶点表 */
   G->vexs[0]='A';
   G->vexs[1]='B';
   G->vexs[2]='C';
   G->vexs[3]='D';
   G->vexs[4]='E';
   G->vexs[5]='F';
   G->vexs[6]='G';
   G->vexs[7]='H';
   G->vexs[8]='I';
   
   /*3. 初始化图中的边表*/
   for (i = 0; i < G->numVertexes; i++)
   {
       for ( j = 0; j < G->numVertexes; j++)
       {
           G->arc[i][j]=0;
       }
   }
   
   /*4.将图中的连接信息输入到边表中*/
   G->arc[0][1]=1;
   G->arc[0][5]=1;
   
   G->arc[1][2]=1;
   G->arc[1][8]=1;
   G->arc[1][6]=1;
   
   G->arc[2][3]=1;
   G->arc[2][8]=1;
   
   G->arc[3][4]=1;
   G->arc[3][7]=1;
   G->arc[3][6]=1;
   G->arc[3][8]=1;
   
   G->arc[4][5]=1;
   G->arc[4][7]=1;
   
   G->arc[5][6]=1;
   
   G->arc[6][7]=1;
   
   /*5.无向图是对称矩阵.构成对称*/
   for(i = 0; i < G->numVertexes; i++)
   {
       for(j = i; j < G->numVertexes; j++)
       {
           G->arc[j][i] =G->arc[i][j];
       }
   }
}

/*
4.2 ***需要用到的队列结构与相关功能函数***
*/

/* 循环队列的顺序存储结构 */
typedef struct
{
   int data[MAXSIZE];
   int front;        /* 头指针 */
   int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}Queue;

/* 初始化一个空队列Q */
Status InitQueue(Queue *Q)
{
   Q->front=0;
   Q->rear=0;
   return  OK;
}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(Queue Q)
{
   if(Q.front==Q.rear) /* 队列空的标志 */
   return TRUE;
   else
   return FALSE;
}

/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(Queue *Q,int e)
{
   if ((Q->rear+1)%MAXSIZE == Q->front)    /* 队列满的判断 */
   return ERROR;
   Q->data[Q->rear]=e;            /* 将元素e赋值给队尾 */
   Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， */
   /* 若到最后则转到数组头部 */
   return  OK;
}

/* 若队列不空，则删除Q中队头元素，用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{
   if (Q->front == Q->rear)            /* 队列空的判断 */
   return ERROR;
   *e=Q->data[Q->front];                /* 将队头元素赋值给e */
   Q->front=(Q->front+1)%MAXSIZE;    /* front指针向后移一位置， */
   /* 若到最后则转到数组头部 */
   return  OK;
}
/******** Queue End **************/

/*4.3 邻接矩阵广度优先遍历-代码实现*/
Boolean visited[MAXVEX]; /* 访问标志的数组 */
void BFSTraverse(MGraph G){
   
   int temp = 0;
   
   //1.
   Queue Q;
   InitQueue(&Q);
   
   //2.将访问标志数组全部置为"未访问状态FALSE"
   for (int i = 0 ; i < G.numVertexes; i++) {
       visited[i] = FALSE;
   }
   
   //3.对遍历邻接表中的每一个顶点(对于连通图只会执行1次,这个循环是针对非连通图)
   for (int i = 0 ; i < G.numVertexes; i++) {
       
       if(!visited[i]){
           visited[i] = TRUE;
           printf("%c  ",G.vexs[i]);
           
           //4. 入队
           EnQueue(&Q, i);
           while (!QueueEmpty(Q)) {
               //出队
               DeQueue(&Q, &i);
               for (int j = 0; j < G.numVertexes; j++) {
                   if(G.arc[i][j] == 1 && !visited[j])
                   {    visited[j] = TRUE;
                       printf("%c   ",G.vexs[j]);
                       EnQueue(&Q, j);
                   }
               }
           }
       }
       
   }
   
   
}

6 邻接表的广度优先遍历

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

/* 邻接矩阵结构 */
typedef struct
{
   VertexType vexs[MAXVEX]; /* 顶点表 */
   EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵,可看作边表 */
   int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;

/* 邻接表结构****************** */
typedef struct EdgeNode /* 边表结点 */
{
   int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
   int weight;        /* 用于存储权值,对于非网图可以不需要 */
   struct EdgeNode *next; /* 链域,指向下一个邻接点 */
}EdgeNode;

typedef struct VertexNode /* 顶点表结点 */
{
   int in;    /* 顶点入度 */
   char data; /* 顶点域,存储顶点信息 */
   EdgeNode *firstedge;/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];

typedef struct
{
   AdjList adjList;
   int numVertexes,numEdges; /* 图中当前顶点数和边数 */
}graphAdjList,*GraphAdjList;

/*4.1 构建一个邻接矩阵*/
void CreateMGraph(MGraph *G)
{
   int i, j;
   
   //1. 确定图的顶点数以及边数
   G->numEdges=15;
   G->numVertexes=9;
   
   /*2.读入顶点信息，建立顶点表 */
   G->vexs[0]='A';
   G->vexs[1]='B';
   G->vexs[2]='C';
   G->vexs[3]='D';
   G->vexs[4]='E';
   G->vexs[5]='F';
   G->vexs[6]='G';
   G->vexs[7]='H';
   G->vexs[8]='I';
   
   /*3. 初始化图中的边表*/
   for (i = 0; i < G->numVertexes; i++)
   {
       for ( j = 0; j < G->numVertexes; j++)
       {
           G->arc[i][j]=0;
       }
   }
   
   /*4.将图中的连接信息输入到边表中*/
   G->arc[0][1]=1;
   G->arc[0][5]=1;
   
   G->arc[1][2]=1;
   G->arc[1][8]=1;
   G->arc[1][6]=1;
   
   G->arc[2][3]=1;
   G->arc[2][8]=1;
   
   G->arc[3][4]=1;
   G->arc[3][7]=1;
   G->arc[3][6]=1;
   G->arc[3][8]=1;
   
   G->arc[4][5]=1;
   G->arc[4][7]=1;
   
   G->arc[5][6]=1;
   
   G->arc[6][7]=1;
   
   /*5.无向图是对称矩阵.构成对称*/
   for(i = 0; i < G->numVertexes; i++)
   {
       for(j = i; j < G->numVertexes; j++)
       {
           G->arc[j][i] =G->arc[i][j];
       }
   }
}

/*4.2 利用邻接矩阵构建邻接表*/
void CreateALGraph(MGraph G,GraphAdjList *GL){
   
   //1.创建邻接表,并且设计邻接表的顶点数以及弧数
   *GL = (GraphAdjList)malloc(sizeof(graphAdjList));
   (*GL)->numVertexes = G.numVertexes;
   (*GL)->numEdges = G.numEdges;
   
   //2. 从邻接矩阵中将顶点信息输入
   for (int i = 0; i < G.numVertexes; i++) {
       //顶点入度为0
       (*GL)->adjList[i].in = 0;
       //顶点信息
       (*GL)->adjList[i].data = G.vexs[i];
       //顶点边表置空
       (*GL)->adjList[i].firstedge = NULL;
   }
   
   //3. 建立边表
   EdgeNode *e;
   for (int i = 0; i < G.numVertexes; i++) {
       for (int j = 0; j < G.numVertexes; j++) {
           if (G.arc[i][j] == 1) {
               
               //创建边表中的邻近结点 i->j
               e = (EdgeNode *)malloc(sizeof(EdgeNode));
               //邻接序号为j
               e->adjvex = j;
               //将当前结点的指向adjList[i]的顶点边表上
               e->next = (*GL)->adjList[i].firstedge;
               (*GL)->adjList[i].firstedge = e;
               //顶点j 上的入度++;
               (*GL)->adjList[j].in++;
               
               //                //创建边表中的邻近结点 j->i
               //                e = (EdgeNode *)malloc(sizeof(EdgeNode));
               //                //邻接序号为j
               //                e->adjvex = i;
               //                //将当前结点的指向adjList[i]的顶点边表上
               //                e->next = (*GL)->adjList[j].firstedge;
               //                (*GL)->adjList[j].firstedge = e;
               //                //顶点j 上的入度++;
               //                (*GL)->adjList[i].in++;
           }
       }
   }
   
   
}

/*
5.2 ***需要用到的队列结构与相关功能函数***
*/
/* 循环队列的顺序存储结构 */
typedef struct
{
   int data[MAXSIZE];
   int front;        /* 头指针 */
   int rear;        /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
}Queue;

/* 初始化一个空队列Q */
Status InitQueue(Queue *Q)
{
   Q->front=0;
   Q->rear=0;
   return  OK;
}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(Queue Q)
{
   if(Q.front==Q.rear) /* 队列空的标志 */
   return TRUE;
   else
   return FALSE;
}

/* 若队列未满,则插入元素e为Q新的队尾元素 */
Status EnQueue(Queue *Q,int e)
{
   if ((Q->rear+1)%MAXSIZE == Q->front)    /* 队列满的判断 */
   return ERROR;
   Q->data[Q->rear]=e;            /* 将元素e赋值给队尾 */
   Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置, */
   /* 若到最后则转到数组头部 */
   return  OK;
}

/* 若队列不空,则删除Q中队头元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{
   if (Q->front == Q->rear)            /* 队列空的判断 */
   return ERROR;
   *e=Q->data[Q->front];                /* 将队头元素赋值给e */
   Q->front=(Q->front+1)%MAXSIZE;    /* front指针向后移一位置, */
   /* 若到最后则转到数组头部 */
   return  OK;
}
/* *********************** Queue End ******************************* */
/*5.3 邻接表广度优先遍历*/
Boolean visited[MAXSIZE]; /* 访问标志的数组 */
void BFSTraverse(GraphAdjList GL){
   
   //1.创建结点
   EdgeNode *p;
   
   Queue Q;
   InitQueue(&Q);
   

   //2.将访问标志数组全部置为"未访问状态FALSE"
   for(int i = 0; i < GL->numVertexes; i++)
       visited[i] = FALSE;
   
   //3.对遍历邻接表中的每一个顶点(对于连通图只会执行1次,这个循环是针对非连通图)
   for(int i = 0 ;i < GL->numVertexes;i++){
       //4.判断当前结点是否被访问过.
       if(!visited[i]){
           visited[i] = TRUE;
           //打印顶点
           printf("%c ",GL->adjList[i].data);
           
           EnQueue(&Q, i);
           while (!QueueEmpty(Q)) {
               DeQueue(&Q, &i);
               p = GL->adjList[i].firstedge;
               while (p) {
                   //判断
                   if(!visited[p->adjvex]){
                       visited[p->adjvex] = TRUE;
                        printf("%c ",GL->adjList[p->adjvex].data);
                       EnQueue(&Q, p->adjvex);
                   }
                   p = p->next;
               }
           }
           
       }
   }
   
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 218,036评论 6赞 506
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,046评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,411评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,622评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,661评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,521评论 1赞 304
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,288评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,200评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,644评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,837评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,953评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,673评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,281评论 3赞 329
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,889评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,011评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,119评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,901评论 2赞 355