图的遍历 - 邻接矩阵 - 深搜与广搜

深搜与广搜图论的遍历基础。而且今天讨论的是最简单的邻接矩阵。
下图是邻接矩阵的大致概念。

在C语言中邻接矩阵的定义方式如下：

//-----图的邻接矩阵存储表示-----
#define MaxInt 32767//表示极大值
#define MVNum 100//最大顶点数
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
typedef struct
{
    VerTexType vexs[MVNum];//顶点表
    //注：一般我们做题很少用到vexs[]这个记录顶点名字的数组。
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum,arcnum;//图的当前点数和边数
}AMGraph;

---

算法以实践为重，开始我们的实验！
实验都以下面的无向图为基础：

题目描述
读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。
输入
输入的第一行包含一个正整数n，表示图*有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。
输出
只有一行，包含n个整数，表示按照题目描述中的深度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。

---

深度优先搜索

深搜算法概述：深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。其过程为：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。
实验样例测试如下图

代码

#include <iostream>

using namespace std;
#define MVNum 55
#define MaxInt 32767
typedef char VerTexType;
typedef int ArcType;
typedef struct
{
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//临接矩阵
    int vexnum,arcnum;//图当前点数和边数
}AMGraph;
//vertex顶点arc弧
void CreateUDN(AMGraph &G)
{
    cin>>G.vexnum;
    int i,j,k;
    for(i=0;i<G.vexnum;++i)
        for(j=0;j<G.vexnum;++j){

            cin>>k;
            G.arcs[i][j]=k;
            G.arcs[j][i]=G.arcs[i][j];
        }
}
bool visited[MVNum];
//Status (* VisitFunc)(int v);
void DFS_AM(AMGraph G,int v)
{
    cout<<v<<" ";visited[v]=true;
    for(int w=0;w<G.vexnum;w++)
        if((G.arcs[v][w]!=0)&&(!visited[w])) DFS_AM(G,w);
}
void DFSTraverse(AMGraph G)
{
    int v;
    for(v=0;v<G.vexnum;++v)
        visited[v]=false;
    for(v=0;v<G.vexnum;++v) if(!visited[v]) DFS_AM(G,v);
}
int main()
{
    AMGraph G;
    CreateUDN(G);
    cout<<"深搜结果：";
    DFSTraverse(G);
    cout<<endl;
    return 0;
}

---

广度优先搜索

广搜算法概述：广度优先搜索遍历类似于树的按层次遍历的过程。其过程为：假设从图中的某顶点v出发，在访问了v之后依次访问v的各个未曾被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点。重复上述过程，直至图中所有顶点都被访问到为止。
实验样例测试如下图

代码

#include <iostream>

using namespace std;
#define MVNum 55
#define MaxInt 32767
typedef char VerTexType;
typedef int ArcType;
typedef struct
{
    int base[100];
    int fron=0;
    int rear=0;
}SqQueue;

void EnQueue(SqQueue &Q,int e)
{
    if((Q.rear+1)%100==Q.fron)
        return ;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%100;
}
void DeQueue(SqQueue &Q,int &e)
{
    if(Q.fron==Q.rear) return ;
    e=Q.base[Q.fron];
    Q.fron=(Q.fron+1)%100;
}
bool QueueEmpty(SqQueue Q)
{
    if(Q.rear==Q.fron)
        return true;
    else
        return false;
}

typedef struct
{
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//临接矩阵
    int vexnum,arcnum;//图当前点数和边数
}AMGraph;
//vertex顶点arc弧
void CreateUDN(AMGraph &G)
{
    cin>>G.vexnum;
    int i,j,k;
    for(i=0;i<G.vexnum;++i)
        for(j=0;j<G.vexnum;++j){

            cin>>k;
            G.arcs[i][j]=k;
            G.arcs[j][i]=G.arcs[i][j];
        }
}

bool visited[MVNum];

int FirstAdjVex(AMGraph G,int u)
{
    for(int i=0;i<G.vexnum;i++)
    {
        if(G.arcs[u][i]==1)
            return i;
    }
    return -1;
}
int NextAdjVex(AMGraph 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(AMGraph G)
{
    int v,w;
    SqQueue Q;
    int u;
    for(v=0;v<G.vexnum;v++)
    if(!visited[v]){
        visited[v]=true;
        cout<<v<<" ";
        EnQueue(Q,v);
        while(!QueueEmpty(Q)){
            DeQueue(Q,u);
            for(int w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
            {
                if(!visited[w]){
                    visited[w]=true;
                    cout<<w<<" ";
                    EnQueue(Q,w);
                }
            }
        }
    }
}
int main()
{
    AMGraph G;
    CreateUDN(G);
    cout<<"广搜结果：";
    BFSTraverse(G);
    cout<<endl;
    return 0;
}

写得仓促，日后补充，如有更好的建议请联系我Q:1070065962.