二、图的遍历

2.1 深度优先搜索（DFS）

DFS森林

Vertextype GetVex(ALGraph G, int v)
{
    return G.vertices[v].data;
}

void DFSTree(ALGraph G, int v, CSTree& T)
{
    int w, first;
    CSTree p, q=NULL;
    ArcNode* temp;
    visited[v] = TRUE;
    first = 1;
    temp = G.vertices[v].firstarc;
    while (temp != NULL)
    {
        w = temp->adjvex;
        if (visited[w] == 0)
        {
            p = (CSTree)malloc(sizeof(CSNode));
            p->e = GetVex(G, w);  //原"GetVex(G,v)";将v改为w即可
            p->lchild = NULL;
            p->nextsibling = NULL;
            if (first)
            {
                T->lchild = p; first = 0;
            }
            else
                q->nextsibling = p;
            q = p;
            DFSTree(G, w, q);
        }
        temp = temp->nextarc;
    }
}

void DFSForest(ALGraph G, CSTree& T)
{
    int v;
    CSTree p, q=NULL;
    T = NULL;
    for (v = 0; v < G.vexnum; v++)
        visited[v] = FALSE;
    for (v = 0; v < G.vexnum; v++)
    {
        if (!visited[v])
        {
            p = (CSTree)malloc(sizeof(CSNode));
            p->e = GetVex(G, v);
            p->lchild = NULL;
            p->nextsibling = NULL;
            if (!T) T = p;
            else    q->nextsibling = p;
            q = p;
            DFSTree(G, v, p);
        }
    }
}

应用

建立一无向图的邻接表存储结构，并构造其对应的深度优先搜索生成树或森林，按先序遍历该二叉链表，输出得到的序列

#include<stdio.h>
#include<stdlib.h>

#define TRUE 1                /*状态码预定义*/
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define MAX_VERTAX_NUM 20 //最大顶点个数
typedef char Vertextype;
//邻接表类型 
typedef struct ArcNode {
    int adjvex; //邻接点域 
    struct ArcNode* nextarc; //指向下一个邻接点的指针域 
}ArcNode;
//表头结点类型 
typedef struct VNode
{
    Vertextype data; //顶点域 
    ArcNode* firstarc; //边表头指针 
}VNode, AdjList[MAX_VERTAX_NUM];
//图的类型 
typedef struct
{
    AdjList vertices; //邻接表 
    int vexnum, arcnum; //顶点数 边数 
    //int kind;
}ALGraph;
typedef struct CSNode
{
    Vertextype e;
    CSNode* lchild, * nextsibling;
}CSNode, * CSTree;
int visited[MAX_VERTAX_NUM];

int LocateVex(ALGraph G, char e)
{
    int i;
    for (i = 0; i < G.vexnum; i++)
    {
        if (G.vertices[i].data == e)
            return i;
    }
    return -1;
}

void CreateUDG(ALGraph& G)
{
    int i, k, j;
    ArcNode* p, * s;
    char v1, v2;
//    printf("图的种类已默认为无向图\n");
//    G.kind = 1;
    printf("请输入顶点数和边数：（空格区分）");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    getchar();
    printf("开始建立顶点表\n");
    for (i = 0; i < G.vexnum; i++)
    {
        printf("请输入第%d个顶点的信息:", i + 1);
        G.vertices[i].data = getchar();
        getchar();
        G.vertices[i].firstarc = NULL;
    }
    printf("建立边表\n");
    for (k = 0; k < G.arcnum; k++)
    {
        printf("请输入两个顶点（例：ab代表a~b）:");
        scanf("%c%c", &v1, &v2);
        getchar();
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p;
        s = (ArcNode*)malloc(sizeof(ArcNode));
        s->adjvex = i;
        s->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = s;
    }
    printf("边表建立完成\n");
}
//打印邻接表
void DispGraph(ALGraph G)
{
    int i;
    printf("打印邻接表:\n");
    for (i = 0; i < G.vexnum; i++)
    {
        printf("%d->", i);
        while (1)
        {
            if (G.vertices[i].firstarc == NULL)
            {
                printf("^");
                break;
            }
            printf("%d->", G.vertices[i].firstarc->adjvex);
            G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
        }
        printf("\n");
    }
}

Vertextype GetVex(ALGraph G, int v)
{
    return G.vertices[v].data;
}

void DFSTree(ALGraph G, int v, CSTree& T)
{
    int w, first;
    CSTree p, q=NULL;
    ArcNode* temp;
    visited[v] = TRUE;
    first = 1;
    temp = G.vertices[v].firstarc;
    while (temp != NULL)
    {
        w = temp->adjvex;
        if (visited[w] == 0)
        {
            p = (CSTree)malloc(sizeof(CSNode));
            p->e = GetVex(G, w);  //原"GetVex(G,v)";将v改为w即可
            p->lchild = NULL;
            p->nextsibling = NULL;
            if (first)
            {
                T->lchild = p; first = 0;
            }
            else
                q->nextsibling = p;
            q = p;
            DFSTree(G, w, q);
        }
        temp = temp->nextarc;
    }
}

void DFSForest(ALGraph G, CSTree& T)
{
    int v;
    CSTree p, q=NULL;
    T = NULL;
    for (v = 0; v < G.vexnum; v++)
        visited[v] = FALSE;
    for (v = 0; v < G.vexnum; v++)
    {
        if (!visited[v])
        {
            p = (CSTree)malloc(sizeof(CSNode));
            p->e = GetVex(G, v);
            p->lchild = NULL;
            p->nextsibling = NULL;
            if (!T) T = p;
            else    q->nextsibling = p;
            q = p;
            DFSTree(G, v, p);
        }
    }
}

void PreOrderTraverse(CSTree T)
{
    if (T == NULL)   return;
    printf("%c", T->e);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->nextsibling);
}

int main()
{
    ALGraph G;  //图
    CSTree T;   //树
    CreateUDG(G);  //建图
    DispGraph(G);  //画表
    DFSForest(G, T);  //种树
    printf("先序遍历开始\n");
    PreOrderTraverse(T);  //先序遍历
    system("pause");
    return 0;
}

2.2 广度优先搜索（BFS）

基本操作

int FirstAdjVex(MGraph G, int v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.arcs[v][i] == 1)
			return i;
	}
	return -1;
}

int NextAdjVex(MGraph G, int u, int w)
{
	for (int i = w + 1; i < G.vexnum; i++)
	{
		if (G.arcs[u][i] == 1)
			return i;
	}
	return -1;
}
void BFSTraverse(MGraph G)
{
	SqQueue Q;
	int v, u, w, visited[MAX_VERTAX_NUM];
	for (v = 0; v < G.vexnum; ++v)
		visited[v] = FALSE;
	InitQueue(Q);
	for (v = 0; v < G.vexnum; v++)
	{
		if (!visited[v]) //尚未访问
		{
			visited[v] = TRUE; //访问并标记
			cout << G.vexs[v]; //遍历 输出
			EnQueue(Q, v); //v 入队
			while (!QueueEmpty(Q))
			{
				DeQueue(Q, u); //队头元素出队并置为u
				for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) //遍历边
				{
					if (!visited[w])
					{
						visited[w] = TRUE;
						cout << G.vexs[w];
						EnQueue(Q, w);
					}
				}
			}
		}
	}
	cout << "广度优先搜索完成" << endl;
}

应用

#include <iostream>
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 //不可执行

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
#define MAXQSIZE 100 //最大队列长度

typedef int QElemType;
typedef int Status;


#define MAX_VERTAX_NUM 20 //最大顶点个数
#define INFINITYA 99999999

typedef char VertexType;
typedef int VRType;
typedef int InfoType;

typedef int AdjMatrix;
typedef int QElemtype;


/*--------单链队列-队列的顺序存储结构--------*/
/*线性表的单链表的存储结构*/
typedef struct QNode {
	QElemType* base;
	int front;
	int rear;
}SqQueue;


Status InitQueue(SqQueue& Q) {
	Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
	if (!Q.base)
		exit(OVERFLOW);
	Q.front = Q.rear = 0;
	return OK;
}

int QueueLength(SqQueue Q) {
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

/*插入元素e为Q的新的队尾元素*/
Status EnQueue(SqQueue& Q, QElemType e) {
	if ((Q.rear + 1) % MAXQSIZE == Q.front)
		return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK;
}

/*若队列不为空则删除Q的队头元素，用e返回其值，并返回ok；否则返回ERROR*/
Status DeQueue(SqQueue& Q, QElemType& e) {
	if (Q.front == Q.rear)
		return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}
/*判断队列是否为空*/
Status QueueEmpty(SqQueue Q) {
	if (Q.front == Q.rear)
		return TRUE;
	else
		return FALSE;
}


//邻接矩阵
typedef struct
{
	VertexType vexs[MAX_VERTAX_NUM];
	AdjMatrix arcs[MAX_VERTAX_NUM][MAX_VERTAX_NUM];
	int vexnum, arcnum;
}MGraph;

int LocateVex(MGraph G, VertexType e)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.vexs[i] == e)
			return i;
	}
	return -1;
}

Status CreateDG(MGraph& G)
{
	int i, j, k;
	char v1, v2;
	cout << "请输入图的顶点个数（vexnum），边数（arcnum）";
	cin >> G.vexnum >> G.arcnum;
	getchar();
	cout << "请输入顶点（例：abcd）:";
	for (i = 0; i < G.vexnum; i++)
		G.vexs[i] = getchar();
	getchar();

	for (i = 0; i < G.vexnum; i++)
		for (j = 0; j < G.vexnum; j++)
			G.arcs[i][j] = INFINITYA;

	for (k = 0; k < G.arcnum; k++)
	{
		cout << k;
		cout << "请输入两个顶点:";
		cin >> v1 >> v2;
		getchar();
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j] = 1;
	}
	return OK;
}


int FirstAdjVex(MGraph G, int v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.arcs[v][i] == 1)
			return i;
	}
	return -1;
}

int NextAdjVex(MGraph G, int u, int w)
{
	for (int i = w + 1; i < G.vexnum; i++)
	{
		if (G.arcs[u][i] == 1)
			return i;
	}
	return -1;
}
void BFSTraverse(MGraph G)
{
	SqQueue Q;
	int v, u, w, visited[MAX_VERTAX_NUM];
	for (v = 0; v < G.vexnum; ++v)
		visited[v] = FALSE;
	InitQueue(Q);
	for (v = 0; v < G.vexnum; v++)
	{
		if (!visited[v]) //尚未访问
		{
			visited[v] = TRUE; //访问并标记
			cout << G.vexs[v]; //遍历 输出
			EnQueue(Q, v); //v 入队
			while (!QueueEmpty(Q))
			{
				DeQueue(Q, u); //队头元素出队并置为u
				for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) //遍历边
				{
					if (!visited[w])
					{
						visited[w] = TRUE;
						cout << G.vexs[w];
						EnQueue(Q, w);
					}
				}
			}
		}
	}
	cout << "广度优先搜索完成" << endl;
}



int main() {
	MGraph G;
	CreateDG(G);
	BFSTraverse(G);   

	return 0;
}

···