有好看图片的软件网站模板下载,网络营销的含义和特点,回合制网页游戏大全,关于网站开发的文章目录
一、深度优先搜索#xff08;Depth-First-Search 简称#xff1a;DFS#xff09;
无向图的深度优先搜索
有向图的深度优先搜索
二、广度优先搜索#xff08;Breadth-First-Search 简称#xff1a;BFS#xff09;
无向图的广度优先搜索
有向图的广度优先搜索 深…目录
一、深度优先搜索Depth-First-Search 简称DFS
无向图的深度优先搜索
有向图的深度优先搜索
二、广度优先搜索Breadth-First-Search 简称BFS
无向图的广度优先搜索
有向图的广度优先搜索 深度优先搜索Depth-First SearchDFS和广度优先搜索Breadth-First SearchBFS是两种常见的图遍历算法它们在C语言中被广泛应用于解决各种数据结构和算法问题。这两种搜索算法都用于遍历图或树中的节点以便查找特定的目标或执行其他相关任务。 一、深度优先搜索Depth-First-Search 简称DFS 图的深度优先搜索(Depth First Search)和树的先序遍历比较类似。 它的思想假设初始状态是图中所有顶点均未被访问则从某个顶点v出发首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到则另选一个未被访问的顶点作起始点重复上述过程直至图中所有顶点都被访问到为止。 显然深度优先搜索是一个递归的过程。
无向图的深度优先搜索
1.1 遍历过程 1从图中某个顶点v出发访问v。 2找出刚才第一个被顶点访问的邻接点。访问该顶点。以这个顶点为新的顶点重复此步骤直到访问过的顶点没有未被访问过的顶点为止。 3返回到步骤2中的被顶点v访问的且还没被访问的邻接点找出该点的下一个未被访问的邻接点访问该顶点。 4重复2 3 直到每个点都被访问过遍历结束。
例无权图
第1步访问A。
第2步访问A的邻接点B。 在第1步访问A之后接下来应该访问的是A的邻接点即B、F、E中的一个。但在本文的实现中顶点ABCDEFG是按照顺序存储B在D、F和E的前面因此先访问B。
第3步访问B的邻接点C。在第2步访问B之后接下来应该访问B的邻接点即F、D、C中一个(A已经被访问过就不算在内)。而由于C在D、F之前先访问C。
第4步访问C的邻接点D。在第3步访问C之后接下来应该访问C的邻接点即D。(B已经被访问过就不算在内)。
第5步访问D的邻接点E。
第6步访问E的邻接点F。
故遍历结果为 A-B-C-D-E-F 有向图的深度优先搜索 第1步访问A。
第2步访问B。在访问A之后接下来访问A的出边的另一个顶点即顶点B。
第3步访问C。 在访问了B之后接下来应该访问的是B的出边的另一个顶点即顶点C,E,F。在本文实现的图中顶点ABCDEFG按照顺序存储因此先访问C。
第4步访问E。接下来访问C的出边的另一个顶点即顶点E。
第5步访问D。接下来访问E的出边的另一个顶点即顶点B,D。顶点B已经被访问过因此访问顶点D。
第6步访问F。接下应该回溯访问A的出边的另一个顶点F。
第7步访问G。
故遍历结果为A-b-c-E-D-F-G
二、广度优先搜索Breadth-First-Search 简称BFS
广度优先搜索算法(Breadth First Search)又称为宽度优先搜索或横向优先搜索简称BFS。 它的思想是从图中某顶点v出发在访问了v之后依次访问v的各个未曾访问过的邻接点然后分别从这些邻接点出发依次访问它们的邻接点并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问则需要另选一个未曾被访问过的顶点作为新的起始点重复上述过程直至图中所有顶点都被访问到为止。 换句话说广度优先搜索遍历图的过程是以v为起点由近至远依次访问和v有路径相通且路径长度为1,2...的顶点。
无向图的广度优先搜索 第1步访问A。第2步依次访问B,E,F。 在访问了A之后接下来访问A的邻接点。顶点ABCDEFG按照顺序存储B在E和F的前面因此先访问B。再访问完B之后再依次访问E,F。第3步依次访问C,D。 在第2步访问完B,E,F之后再依次访问它们的邻接点。首先访问B的邻接点C再访问E的邻接点D。
因此访问顺序是:A-B-E-F-C-D
有向图的广度优先搜索 第1步访问A。第2步访问B。第3步依次访问C,E,F。 在访问了B之后接下来访问B的出边的另一个顶点即C,E,F。顶点ABCDEFG按照顺序存储因此会先访问C再依次访问E,F。第4步依次访问D,G。 在访问完C,E,F之后再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问C的已经全部访问过了那么就只剩下E,F先访问E的邻接点D再访问F的邻接点G。
因此访问顺序是A-B-C-E-F-D-G 邻接矩阵图表示的无向图
/*** C: 邻接矩阵图表示的无向图(Matrix Undirected Graph)** author skywang* date 2014/04/18*/#include stdio.h
#include stdlib.h
#include malloc.h
#include string.h#define MAX 100
#define isLetter(a) ((((a)a)((a)z)) || (((a)A)((a)Z)))
#define LENGTH(a) (sizeof(a)/sizeof(a[0]))// 邻接矩阵
typedef struct _graph
{char vexs[MAX]; // 顶点集合int vexnum; // 顶点数int edgnum; // 边数int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;/** 返回ch在matrix矩阵中的位置*/
static int get_position(Graph g, char ch)
{int i;for(i0; ig.vexnum; i)if(g.vexs[i]ch)return i;return -1;
}/** 读取一个输入字符*/
static char read_char()
{char ch;do {ch getchar();} while(!isLetter(ch));return ch;
}/** 创建图(自己输入)*/
Graph* create_graph()
{char c1, c2;int v, e;int i, p1, p2;Graph* pG;// 输入顶点数和边数printf(input vertex number: );scanf(%d, v);printf(input edge number: );scanf(%d, e);if ( v 1 || e 1 || (e (v * (v-1)))){printf(input error: invalid parameters!\n);return NULL;}if ((pG(Graph*)malloc(sizeof(Graph))) NULL )return NULL;memset(pG, 0, sizeof(Graph));// 初始化顶点数和边数pG-vexnum v;pG-edgnum e;// 初始化顶点for (i 0; i pG-vexnum; i){printf(vertex(%d): , i);pG-vexs[i] read_char();}// 初始化边for (i 0; i pG-edgnum; i){// 读取边的起始顶点和结束顶点printf(edge(%d):, i);c1 read_char();c2 read_char();p1 get_position(*pG, c1);p2 get_position(*pG, c2);if (p1-1 || p2-1){printf(input error: invalid edge!\n);free(pG);return NULL;}pG-matrix[p1][p2] 1;pG-matrix[p2][p1] 1;}return pG;
}/** 创建图(用已提供的矩阵)*/
Graph* create_example_graph()
{char vexs[] {A, B, C, D, E, F, G};char edges[][2] {{A, C}, {A, D}, {A, F}, {B, C}, {C, D}, {E, G}, {F, G}}; int vlen LENGTH(vexs);int elen LENGTH(edges);int i, p1, p2;Graph* pG;// 输入顶点数和边数if ((pG(Graph*)malloc(sizeof(Graph))) NULL )return NULL;memset(pG, 0, sizeof(Graph));// 初始化顶点数和边数pG-vexnum vlen;pG-edgnum elen;// 初始化顶点for (i 0; i pG-vexnum; i){pG-vexs[i] vexs[i];}// 初始化边for (i 0; i pG-edgnum; i){// 读取边的起始顶点和结束顶点p1 get_position(*pG, edges[i][0]);p2 get_position(*pG, edges[i][1]);pG-matrix[p1][p2] 1;pG-matrix[p2][p1] 1;}return pG;
}/** 返回顶点v的第一个邻接顶点的索引失败则返回-1*/
static int first_vertex(Graph G, int v)
{int i;if (v0 || v(G.vexnum-1))return -1;for (i 0; i G.vexnum; i)if (G.matrix[v][i] 1)return i;return -1;
}/** 返回顶点v相对于w的下一个邻接顶点的索引失败则返回-1*/
static int next_vertix(Graph G, int v, int w)
{int i;if (v0 || v(G.vexnum-1) || w0 || w(G.vexnum-1))return -1;for (i w 1; i G.vexnum; i)if (G.matrix[v][i] 1)return i;return -1;
}/** 深度优先搜索遍历图的递归实现*/
static void DFS(Graph G, int i, int *visited)
{ int w; visited[i] 1;printf(%c , G.vexs[i]);// 遍历该顶点的所有邻接顶点。若是没有访问过那么继续往下走for (w first_vertex(G, i); w 0; w next_vertix(G, i, w)){if (!visited[w])DFS(G, w, visited);}}/** 深度优先搜索遍历图*/
void DFSTraverse(Graph G)
{int i;int visited[MAX]; // 顶点访问标记// 初始化所有顶点都没有被访问for (i 0; i G.vexnum; i)visited[i] 0;printf(DFS: );for (i 0; i G.vexnum; i){//printf(\n LOOP(%d)\n, i);if (!visited[i])DFS(G, i, visited);}printf(\n);
}/** 广度优先搜索类似于树的层次遍历*/
void BFS(Graph G)
{int head 0;int rear 0;int queue[MAX]; // 辅组队列int visited[MAX]; // 顶点访问标记int i, j, k;for (i 0; i G.vexnum; i)visited[i] 0;printf(BFS: );for (i 0; i G.vexnum; i){if (!visited[i]){visited[i] 1;printf(%c , G.vexs[i]);queue[rear] i; // 入队列}while (head ! rear) {j queue[head]; // 出队列for (k first_vertex(G, j); k 0; k next_vertix(G, j, k)) //k是为访问的邻接顶点{if (!visited[k]){visited[k] 1;printf(%c , G.vexs[k]);queue[rear] k;}}}}printf(\n);
}/** 打印矩阵队列图*/
void print_graph(Graph G)
{int i,j;printf(Martix Graph:\n);for (i 0; i G.vexnum; i){for (j 0; j G.vexnum; j)printf(%d , G.matrix[i][j]);printf(\n);}
}void main()
{Graph* pG;// 自定义图(输入矩阵队列)//pG create_graph();// 采用已有的图pG create_example_graph();print_graph(*pG); // 打印图DFSTraverse(*pG); // 深度优先遍历BFS(*pG); // 广度优先遍历
}
邻接表表示的无向图
/*** C: 邻接表表示的无向图(List Undirected Graph)** author skywang* date 2014/04/18*/#include stdio.h
#include stdlib.h
#include malloc.h
#include string.h#define MAX 100
#define isLetter(a) ((((a)a)((a)z)) || (((a)A)((a)Z)))
#define LENGTH(a) (sizeof(a)/sizeof(a[0]))// 邻接表中表对应的链表的顶点
typedef struct _ENode
{int ivex; // 该边所指向的顶点的位置struct _ENode *next_edge; // 指向下一条弧的指针
}ENode, *PENode;// 邻接表中表的顶点
typedef struct _VNode
{char data; // 顶点信息ENode *first_edge; // 指向第一条依附该顶点的弧
}VNode;// 邻接表
typedef struct _LGraph
{int vexnum; // 图的顶点的数目int edgnum; // 图的边的数目VNode vexs[MAX];
}LGraph;/** 返回ch在matrix矩阵中的位置*/
static int get_position(LGraph g, char ch)
{int i;for(i0; ig.vexnum; i)if(g.vexs[i].datach)return i;return -1;
}/** 读取一个输入字符*/
static char read_char()
{char ch;do {ch getchar();} while(!isLetter(ch));return ch;
}/** 将node链接到list的末尾*/
static void link_last(ENode *list, ENode *node)
{ENode *p list;while(p-next_edge)p p-next_edge;p-next_edge node;
}/** 创建邻接表对应的图(自己输入)*/
LGraph* create_lgraph()
{char c1, c2;int v, e;int i, p1, p2;ENode *node1, *node2;LGraph* pG;// 输入顶点数和边数printf(input vertex number: );scanf(%d, v);printf(input edge number: );scanf(%d, e);if ( v 1 || e 1 || (e (v * (v-1)))){printf(input error: invalid parameters!\n);return NULL;}if ((pG(LGraph*)malloc(sizeof(LGraph))) NULL )return NULL;memset(pG, 0, sizeof(LGraph));// 初始化顶点数和边数pG-vexnum v;pG-edgnum e;// 初始化邻接表的顶点for(i0; ipG-vexnum; i){printf(vertex(%d): , i);pG-vexs[i].data read_char();pG-vexs[i].first_edge NULL;}// 初始化邻接表的边for(i0; ipG-edgnum; i){// 读取边的起始顶点和结束顶点printf(edge(%d): , i);c1 read_char();c2 read_char();p1 get_position(*pG, c1);p2 get_position(*pG, c2);// 初始化node1node1 (ENode*)malloc(sizeof(ENode));node1-ivex p2;// 将node1链接到p1所在链表的末尾if(pG-vexs[p1].first_edge NULL)pG-vexs[p1].first_edge node1;elselink_last(pG-vexs[p1].first_edge, node1);// 初始化node2node2 (ENode*)malloc(sizeof(ENode));node2-ivex p1;// 将node2链接到p2所在链表的末尾if(pG-vexs[p2].first_edge NULL)pG-vexs[p2].first_edge node2;elselink_last(pG-vexs[p2].first_edge, node2);}return pG;
}/** 创建邻接表对应的图(用已提供的数据)*/
LGraph* create_example_lgraph()
{char c1, c2;char vexs[] {A, B, C, D, E, F, G};char edges[][2] {{A, C}, {A, D}, {A, F}, {B, C}, {C, D}, {E, G}, {F, G}}; int vlen LENGTH(vexs);int elen LENGTH(edges);int i, p1, p2;ENode *node1, *node2;LGraph* pG;if ((pG(LGraph*)malloc(sizeof(LGraph))) NULL )return NULL;memset(pG, 0, sizeof(LGraph));// 初始化顶点数和边数pG-vexnum vlen;pG-edgnum elen;// 初始化邻接表的顶点for(i0; ipG-vexnum; i){pG-vexs[i].data vexs[i];pG-vexs[i].first_edge NULL;}// 初始化邻接表的边for(i0; ipG-edgnum; i){// 读取边的起始顶点和结束顶点c1 edges[i][0];c2 edges[i][1];p1 get_position(*pG, c1);p2 get_position(*pG, c2);// 初始化node1node1 (ENode*)malloc(sizeof(ENode));node1-ivex p2;// 将node1链接到p1所在链表的末尾if(pG-vexs[p1].first_edge NULL)pG-vexs[p1].first_edge node1;elselink_last(pG-vexs[p1].first_edge, node1);// 初始化node2node2 (ENode*)malloc(sizeof(ENode));node2-ivex p1;// 将node2链接到p2所在链表的末尾if(pG-vexs[p2].first_edge NULL)pG-vexs[p2].first_edge node2;elselink_last(pG-vexs[p2].first_edge, node2);}return pG;
}/** 深度优先搜索遍历图的递归实现*/
static void DFS(LGraph G, int i, int *visited)
{int w;ENode *node;visited[i] 1;printf(%c , G.vexs[i].data);node G.vexs[i].first_edge;while (node ! NULL){if (!visited[node-ivex])DFS(G, node-ivex, visited);node node-next_edge;}
}/** 深度优先搜索遍历图*/
void DFSTraverse(LGraph G)
{int i;int visited[MAX]; // 顶点访问标记// 初始化所有顶点都没有被访问for (i 0; i G.vexnum; i)visited[i] 0;printf(DFS: );for (i 0; i G.vexnum; i){if (!visited[i])DFS(G, i, visited);}printf(\n);
}/** 广度优先搜索类似于树的层次遍历*/
void BFS(LGraph G)
{int head 0;int rear 0;int queue[MAX]; // 辅组队列int visited[MAX]; // 顶点访问标记int i, j, k;ENode *node;for (i 0; i G.vexnum; i)visited[i] 0;printf(BFS: );for (i 0; i G.vexnum; i){if (!visited[i]){visited[i] 1;printf(%c , G.vexs[i].data);queue[rear] i; // 入队列}while (head ! rear) {j queue[head]; // 出队列node G.vexs[j].first_edge;while (node ! NULL){k node-ivex;if (!visited[k]){visited[k] 1;printf(%c , G.vexs[k].data);queue[rear] k;}node node-next_edge;}}}printf(\n);
}/** 打印邻接表图*/
void print_lgraph(LGraph G)
{int i,j;ENode *node;printf(List Graph:\n);for (i 0; i G.vexnum; i){printf(%d(%c): , i, G.vexs[i].data);node G.vexs[i].first_edge;while (node ! NULL){printf(%d(%c) , node-ivex, G.vexs[node-ivex].data);node node-next_edge;}printf(\n);}
}void main()
{LGraph* pG;// 自定义图(自己输入数据)//pG create_lgraph();// 采用已有的图pG create_example_lgraph();// 打印图print_lgraph(*pG);DFSTraverse(*pG);BFS(*pG);
}
邻接矩阵表示的有向图
/*** C: 邻接矩阵表示的有向图(Matrix Directed Graph)** author skywang* date 2014/04/18*/#include stdio.h
#include stdlib.h
#include malloc.h
#include string.h#define MAX 100
#define isLetter(a) ((((a)a)((a)z)) || (((a)A)((a)Z)))
#define LENGTH(a) (sizeof(a)/sizeof(a[0]))// 邻接矩阵
typedef struct _graph
{char vexs[MAX]; // 顶点集合int vexnum; // 顶点数int edgnum; // 边数int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;/** 返回ch在matrix矩阵中的位置*/
static int get_position(Graph g, char ch)
{int i;for(i0; ig.vexnum; i)if(g.vexs[i]ch)return i;return -1;
}/** 读取一个输入字符*/
static char read_char()
{char ch;do {ch getchar();} while(!isLetter(ch));return ch;
}/** 创建图(自己输入)*/
Graph* create_graph()
{char c1, c2;int v, e;int i, p1, p2;Graph* pG;// 输入顶点数和边数printf(input vertex number: );scanf(%d, v);printf(input edge number: );scanf(%d, e);if ( v 1 || e 1 || (e (v * (v-1)))){printf(input error: invalid parameters!\n);return NULL;}if ((pG(Graph*)malloc(sizeof(Graph))) NULL )return NULL;memset(pG, 0, sizeof(Graph));// 初始化顶点数和边数pG-vexnum v;pG-edgnum e;// 初始化顶点for (i 0; i pG-vexnum; i){printf(vertex(%d): , i);pG-vexs[i] read_char();}// 初始化边for (i 0; i pG-edgnum; i){// 读取边的起始顶点和结束顶点printf(edge(%d):, i);c1 read_char();c2 read_char();p1 get_position(*pG, c1);p2 get_position(*pG, c2);if (p1-1 || p2-1){printf(input error: invalid edge!\n);free(pG);return NULL;}pG-matrix[p1][p2] 1;}return pG;
}/** 创建图(用已提供的矩阵)*/
Graph* create_example_graph()
{char vexs[] {A, B, C, D, E, F, G};char edges[][2] {{A, B}, {B, C}, {B, E}, {B, F}, {C, E}, {D, C}, {E, B}, {E, D}, {F, G}}; int vlen LENGTH(vexs);int elen LENGTH(edges);int i, p1, p2;Graph* pG;// 输入顶点数和边数if ((pG(Graph*)malloc(sizeof(Graph))) NULL )return NULL;memset(pG, 0, sizeof(Graph));// 初始化顶点数和边数pG-vexnum vlen;pG-edgnum elen;// 初始化顶点for (i 0; i pG-vexnum; i){pG-vexs[i] vexs[i];}// 初始化边for (i 0; i pG-edgnum; i){// 读取边的起始顶点和结束顶点p1 get_position(*pG, edges[i][0]);p2 get_position(*pG, edges[i][1]);pG-matrix[p1][p2] 1;}return pG;
}/** 返回顶点v的第一个邻接顶点的索引失败则返回-1*/
static int first_vertex(Graph G, int v)
{int i;if (v0 || v(G.vexnum-1))return -1;for (i 0; i G.vexnum; i)if (G.matrix[v][i] 1)return i;return -1;
}/** 返回顶点v相对于w的下一个邻接顶点的索引失败则返回-1*/
static int next_vertix(Graph G, int v, int w)
{int i;if (v0 || v(G.vexnum-1) || w0 || w(G.vexnum-1))return -1;for (i w 1; i G.vexnum; i)if (G.matrix[v][i] 1)return i;return -1;
}/** 深度优先搜索遍历图的递归实现*/
static void DFS(Graph G, int i, int *visited)
{ int w; visited[i] 1;printf(%c , G.vexs[i]);// 遍历该顶点的所有邻接顶点。若是没有访问过那么继续往下走for (w first_vertex(G, i); w 0; w next_vertix(G, i, w)){if (!visited[w])DFS(G, w, visited);}}/** 深度优先搜索遍历图*/
void DFSTraverse(Graph G)
{int i;int visited[MAX]; // 顶点访问标记// 初始化所有顶点都没有被访问for (i 0; i G.vexnum; i)visited[i] 0;printf(DFS: );for (i 0; i G.vexnum; i){//printf(\n LOOP(%d)\n, i);if (!visited[i])DFS(G, i, visited);}printf(\n);
}/** 广度优先搜索类似于树的层次遍历*/
void BFS(Graph G)
{int head 0;int rear 0;int queue[MAX]; // 辅组队列int visited[MAX]; // 顶点访问标记int i, j, k;for (i 0; i G.vexnum; i)visited[i] 0;printf(BFS: );for (i 0; i G.vexnum; i){if (!visited[i]){visited[i] 1;printf(%c , G.vexs[i]);queue[rear] i; // 入队列}while (head ! rear) {j queue[head]; // 出队列for (k first_vertex(G, j); k 0; k next_vertix(G, j, k)) //k是为访问的邻接顶点{if (!visited[k]){visited[k] 1;printf(%c , G.vexs[k]);queue[rear] k;}}}}printf(\n);
}/** 打印矩阵队列图*/
void print_graph(Graph G)
{int i,j;printf(Martix Graph:\n);for (i 0; i G.vexnum; i){for (j 0; j G.vexnum; j)printf(%d , G.matrix[i][j]);printf(\n);}
}void main()
{Graph* pG;// 自定义图(输入矩阵队列)//pG create_graph();// 采用已有的图pG create_example_graph();print_graph(*pG); // 打印图DFSTraverse(*pG); // 深度优先遍历BFS(*pG); // 广度优先遍历
}
邻接表表示的有向图
/*** C: 邻接表表示的有向图(List Directed Graph)** author skywang* date 2014/04/18*/#include stdio.h
#include stdlib.h
#include malloc.h
#include string.h#define MAX 100
#define isLetter(a) ((((a)a)((a)z)) || (((a)A)((a)Z)))
#define LENGTH(a) (sizeof(a)/sizeof(a[0]))// 邻接表中表对应的链表的顶点
typedef struct _ENode
{int ivex; // 该边所指向的顶点的位置struct _ENode *next_edge; // 指向下一条弧的指针
}ENode, *PENode;// 邻接表中表的顶点
typedef struct _VNode
{char data; // 顶点信息ENode *first_edge; // 指向第一条依附该顶点的弧
}VNode;// 邻接表
typedef struct _LGraph
{int vexnum; // 图的顶点的数目int edgnum; // 图的边的数目VNode vexs[MAX];
}LGraph;/** 返回ch在matrix矩阵中的位置*/
static int get_position(LGraph g, char ch)
{int i;for(i0; ig.vexnum; i)if(g.vexs[i].datach)return i;return -1;
}/** 读取一个输入字符*/
static char read_char()
{char ch;do {ch getchar();} while(!isLetter(ch));return ch;
}/** 将node链接到list的末尾*/
static void link_last(ENode *list, ENode *node)
{ENode *p list;while(p-next_edge)p p-next_edge;p-next_edge node;
}/** 创建邻接表对应的图(自己输入)*/
LGraph* create_lgraph()
{char c1, c2;int v, e;int i, p1, p2;ENode *node1, *node2;LGraph* pG;// 输入顶点数和边数printf(input vertex number: );scanf(%d, v);printf(input edge number: );scanf(%d, e);if ( v 1 || e 1 || (e (v * (v-1)))){printf(input error: invalid parameters!\n);return NULL;}if ((pG(LGraph*)malloc(sizeof(LGraph))) NULL )return NULL;memset(pG, 0, sizeof(LGraph));// 初始化顶点数和边数pG-vexnum v;pG-edgnum e;// 初始化邻接表的顶点for(i0; ipG-vexnum; i){printf(vertex(%d): , i);pG-vexs[i].data read_char();pG-vexs[i].first_edge NULL;}// 初始化邻接表的边for(i0; ipG-edgnum; i){// 读取边的起始顶点和结束顶点printf(edge(%d): , i);c1 read_char();c2 read_char();p1 get_position(*pG, c1);p2 get_position(*pG, c2);// 初始化node1node1 (ENode*)malloc(sizeof(ENode));node1-ivex p2;// 将node1链接到p1所在链表的末尾if(pG-vexs[p1].first_edge NULL)pG-vexs[p1].first_edge node1;elselink_last(pG-vexs[p1].first_edge, node1);}return pG;
}/** 创建邻接表对应的图(用已提供的数据)*/
LGraph* create_example_lgraph()
{char c1, c2;char vexs[] {A, B, C, D, E, F, G};char edges[][2] {{A, B}, {B, C}, {B, E}, {B, F}, {C, E}, {D, C}, {E, B}, {E, D}, {F, G}}; int vlen LENGTH(vexs);int elen LENGTH(edges);int i, p1, p2;ENode *node1, *node2;LGraph* pG;if ((pG(LGraph*)malloc(sizeof(LGraph))) NULL )return NULL;memset(pG, 0, sizeof(LGraph));// 初始化顶点数和边数pG-vexnum vlen;pG-edgnum elen;// 初始化邻接表的顶点for(i0; ipG-vexnum; i){pG-vexs[i].data vexs[i];pG-vexs[i].first_edge NULL;}// 初始化邻接表的边for(i0; ipG-edgnum; i){// 读取边的起始顶点和结束顶点c1 edges[i][0];c2 edges[i][1];p1 get_position(*pG, c1);p2 get_position(*pG, c2);// 初始化node1node1 (ENode*)malloc(sizeof(ENode));node1-ivex p2;// 将node1链接到p1所在链表的末尾if(pG-vexs[p1].first_edge NULL)pG-vexs[p1].first_edge node1;elselink_last(pG-vexs[p1].first_edge, node1);}return pG;
}/** 深度优先搜索遍历图的递归实现*/
static void DFS(LGraph G, int i, int *visited)
{int w;ENode *node;visited[i] 1;printf(%c , G.vexs[i].data);node G.vexs[i].first_edge;while (node ! NULL){if (!visited[node-ivex])DFS(G, node-ivex, visited);node node-next_edge;}
}/** 深度优先搜索遍历图*/
void DFSTraverse(LGraph G)
{int i;int visited[MAX]; // 顶点访问标记// 初始化所有顶点都没有被访问for (i 0; i G.vexnum; i)visited[i] 0;printf(DFS: );for (i 0; i G.vexnum; i){if (!visited[i])DFS(G, i, visited);}printf(\n);
}/** 广度优先搜索类似于树的层次遍历*/
void BFS(LGraph G)
{int head 0;int rear 0;int queue[MAX]; // 辅组队列int visited[MAX]; // 顶点访问标记int i, j, k;ENode *node;for (i 0; i G.vexnum; i)visited[i] 0;printf(BFS: );for (i 0; i G.vexnum; i){if (!visited[i]){visited[i] 1;printf(%c , G.vexs[i].data);queue[rear] i; // 入队列}while (head ! rear) {j queue[head]; // 出队列node G.vexs[j].first_edge;while (node ! NULL){k node-ivex;if (!visited[k]){visited[k] 1;printf(%c , G.vexs[k].data);queue[rear] k;}node node-next_edge;}}}printf(\n);
}/** 打印邻接表图*/
void print_lgraph(LGraph G)
{int i,j;ENode *node;printf(List Graph:\n);for (i 0; i G.vexnum; i){printf(%d(%c): , i, G.vexs[i].data);node G.vexs[i].first_edge;while (node ! NULL){printf(%d(%c) , node-ivex, G.vexs[node-ivex].data);node node-next_edge;}printf(\n);}
}void main()
{LGraph* pG;// 自定义图(自己输入数据)//pG create_lgraph();// 采用已有的图pG create_example_lgraph();// 打印图print_lgraph(*pG);DFSTraverse(*pG);BFS(*pG);
}
