深度优先 宽度优先 C语言数据结构与算法——深度、广度优先搜索（DFS、BFS）

目录

一、深度优先搜索（Depth-First-Search 简称：DFS）

无向图的深度优先搜索

有向图的深度优先搜索

二、广度优先搜索（Breadth-First-Search 简称：BFS）

无向图的广度优先搜索

有向图的广度优先搜索

深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）是两种常见的图遍历算法，它们在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

#include

#include

#include

#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(i=0; 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 (v<0 || 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 (v<0 || v>(G.vexnum-1) || w<0 || 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

#include

#include

#include

#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(i=0; i

if(g.vexs[i].data==ch)

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(i=0; ivexnum; i++)

{

printf("vertex(%d): ", i);

pG->vexs[i].data = read_char();

pG->vexs[i].first_edge = NULL;

}

// 初始化"邻接表"的边

for(i=0; iedgnum; i++)

{

// 读取边的起始顶点和结束顶点

printf("edge(%d): ", i);

c1 = read_char();

c2 = read_char();

p1 = get_position(*pG, c1);

p2 = get_position(*pG, c2);

// 初始化node1

node1 = (ENode*)malloc(sizeof(ENode));

node1->ivex = p2;

// 将node1链接到"p1所在链表的末尾"

if(pG->vexs[p1].first_edge == NULL)

pG->vexs[p1].first_edge = node1;

else

link_last(pG->vexs[p1].first_edge, node1);

// 初始化node2

node2 = (ENode*)malloc(sizeof(ENode));

node2->ivex = p1;

// 将node2链接到"p2所在链表的末尾"

if(pG->vexs[p2].first_edge == NULL)

pG->vexs[p2].first_edge = node2;

else

link_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(i=0; ivexnum; i++)

{

pG->vexs[i].data = vexs[i];

pG->vexs[i].first_edge = NULL;

}

// 初始化"邻接表"的边

for(i=0; iedgnum; i++)

{

// 读取边的起始顶点和结束顶点

c1 = edges[i][0];

c2 = edges[i][1];

p1 = get_position(*pG, c1);

p2 = get_position(*pG, c2);

// 初始化node1

node1 = (ENode*)malloc(sizeof(ENode));

node1->ivex = p2;

// 将node1链接到"p1所在链表的末尾"

if(pG->vexs[p1].first_edge == NULL)

pG->vexs[p1].first_edge = node1;

else

link_last(pG->vexs[p1].first_edge, node1);

// 初始化node2

node2 = (ENode*)malloc(sizeof(ENode));

node2->ivex = p1;

// 将node2链接到"p2所在链表的末尾"

if(pG->vexs[p2].first_edge == NULL)

pG->vexs[p2].first_edge = node2;

else

link_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

#include

#include

#include

#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(i=0; 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 (v<0 || 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 (v<0 || v>(G.vexnum-1) || w<0 || 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

#include

#include

#include

#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(i=0; i

if(g.vexs[i].data==ch)

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(i=0; ivexnum; i++)

{

printf("vertex(%d): ", i);

pG->vexs[i].data = read_char();

pG->vexs[i].first_edge = NULL;

}

// 初始化"邻接表"的边

for(i=0; iedgnum; i++)

{

// 读取边的起始顶点和结束顶点

printf("edge(%d): ", i);

c1 = read_char();

c2 = read_char();

p1 = get_position(*pG, c1);

p2 = get_position(*pG, c2);

// 初始化node1

node1 = (ENode*)malloc(sizeof(ENode));

node1->ivex = p2;

// 将node1链接到"p1所在链表的末尾"

if(pG->vexs[p1].first_edge == NULL)

pG->vexs[p1].first_edge = node1;

else

link_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(i=0; ivexnum; i++)

{

pG->vexs[i].data = vexs[i];

pG->vexs[i].first_edge = NULL;

}

// 初始化"邻接表"的边

for(i=0; iedgnum; i++)

{

// 读取边的起始顶点和结束顶点

c1 = edges[i][0];

c2 = edges[i][1];

p1 = get_position(*pG, c1);

p2 = get_position(*pG, c2);

// 初始化node1

node1 = (ENode*)malloc(sizeof(ENode));

node1->ivex = p2;

// 将node1链接到"p1所在链表的末尾"

if(pG->vexs[p1].first_edge == NULL)

pG->vexs[p1].first_edge = node1;

else

link_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);

}

参考文章