邻接矩阵表示 深度遍历 广度遍历

邻接矩阵表示法是一种图的表示方法，其中每个顶点都有一个唯一的索引，而每条边则由两个顶点之间的连接确定。深度优先遍历（DFS）和广度优先遍历（BFS）是两种常用的图遍历算法。

1. 深度优先遍历（DFS）：

深度优先遍历从根节点开始，沿着一条路径尽可能深入地访问节点，直到到达叶子节点。然后回溯到上一个节点，继续访问其他未访问过的节点。这个过程一直持续到所有节点都被访问过为止。

在邻接矩阵表示法中，可以使用递归或栈来实现深度优先遍历。以下是使用栈实现的示例代码：

#include <iostream>
#include <stack>
using namespace std;

void dfs(int matrix[][4], int start, bool visited[]) {
? ? stack<int> s;
? ? s.push(start);
? ? visited[start] = true;

? ? while (!s.empty()) {
? ? ? ? int node = s.top();
? ? ? ? s.pop();
? ? ? ? cout << node << " ";

? ? ? ? for (int i = 0; i < 4; i++) {
? ? ? ? ? ? if (matrix[node][i] == 1 && !visited[i]) {
? ? ? ? ? ? ? ? s.push(i);
? ? ? ? ? ? ? ? visited[i] = true;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}

int main() {
? ? int matrix[4][4] = {
? ? ? ? {0, 1, 1, 0},
? ? ? ? {1, 0, 0, 1},
? ? ? ? {1, 0, 0, 1},
? ? ? ? {0, 1, 1, 0}
? ? };
? ? bool visited[4] = {false};

? ? dfs(matrix, 0, visited);

? ? return 0;
}

?

2. 广度优先遍历（BFS）：

广度优先遍历从根节点开始，首先访问所有与根节点直接相连的节点，然后再访问这些节点的邻居节点，以此类推。这个过程一直持续到所有节点都被访问过为止。

在邻接矩阵表示法中，可以使用队列来实现广度优先遍历。以下是使用队列实现的示例代码：

#include <iostream>
#include <queue>
using namespace std;

void bfs(int matrix[][4], int start, bool visited[]) {
? ? queue<int> q;
? ? q.push(start);
? ? visited[start] = true;

? ? while (!q.empty()) {
? ? ? ? int node = q.front();
? ? ? ? q.pop();
? ? ? ? cout << node << " ";

? ? ? ? for (int i = 0; i < 4; i++) {
? ? ? ? ? ? if (matrix[node][i] == 1 && !visited[i]) {
? ? ? ? ? ? ? ? q.push(i);
? ? ? ? ? ? ? ? visited[i] = true;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}

int main() {
? ? int matrix[4][4] = {
? ? ? ? {0, 1, 1, 0},
? ? ? ? {1, 0, 0, 1},
? ? ? ? {1, 0, 0, 1},
? ? ? ? {0, 1, 1, 0}
? ? };
? ? bool visited[4] = {false};

? ? bfs(matrix, 0, visited);

? ? return 0;
}

?

3. 邻接矩阵表示 深度遍历 广度遍历

?代码如下：

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

#define MaxInt  32767
#define MVNum 100

typedef char VerTexType;
typedef int ArcType;
//邻接矩阵
typedef  struct {
    VerTexType  vexs[MVNum];  /*存储顶点元素*/
    ArcType arcs[MVNum][MVNum];
    /*各顶点之间的关系或权值*/
    int  vexnum, arcnum; /*顶点数，边（或弧）的个数*/
}MGraph;
int visited[MVNum];
int visitedBFS[MVNum];
stack<VerTexType> mystack;
queue<VerTexType> myqueue;
//函数声明
void PrintVisited();
int LocateVex(MGraph& G, VerTexType v); //函数定义
void CreateMGraph(MGraph& G);
void DFS(MGraph& G, VerTexType v);
void BFS(MGraph& G, VerTexType v);
void TestDemoGraph();

//函数定义

void  CreateMGraph(MGraph& G) {
    int i = 0, j = 0, k = 0;
    cout << "输入顶点个数：";
    cin >> G.vexnum;
    cout << "输入边的个数：";
    cin >> G.arcnum;
    for (i = 0; i < G.vexnum; i++) {
        cout << "输入第" << i + 1 << "个顶点的名称：";
        cin >> G.vexs[i];
    }

    for (i = 0; i < G.vexnum; ++i)         //初始化邻接矩阵，
        for (j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = 0;

    cout << "输入边依附的顶点 ，如 a b " << endl;
    VerTexType v1, v2;
    for (k = 0; k < G.arcnum; ++k) {							//构造邻接矩阵
        cout << "请输入第" << (k + 1) << "条边依附的顶点及权值：";
        cin >> v1 >> v2;								//输入一条边依附的顶点及权值
        i = LocateVex(G, v1);   //函数调用
        j = LocateVex(G, v2);		//确定v1和v2在G中的位置，即顶点数组的下标
        if (i == -1 || j == -1) {
            cout << "顶点名称错误" << endl;
            k--;
            continue;
        }
        G.arcs[i][j] = 1;								//边<v1, v2>的值为1
        G.arcs[j][i] = G.arcs[i][j];						//置<v1, v2>的对称边<v2, v1>的权值为w
    }//for
}
int LocateVex(MGraph& G, VerTexType v) { //函数定义
    //确定点v在G中的位置
    for (int i = 0; i < G.vexnum; ++i)
        if (G.vexs[i] == v)
            return i;
    return -1;
}//LocateVex

void PrintVexArc(MGraph& G) {
    int i = 0, j = 0;
    cout << "顶点列表：" << endl;
    for (i = 0; i < G.vexnum; i++) {
        cout << "\t" << G.vexs[i];
    }
    cout << endl << "邻接矩阵：" << endl;
    for (i = 0; i < G.vexnum; i++) {
        for (j = 0; j < G.vexnum; j++) {
            cout << "\t" << G.arcs[i][j];
        }
        cout << endl;
    }
}

void PrintVisited() {
    for (int i = 0; i < 6; i++) cout << visited[i] << "\t"; cout << endl;
}
void PrintVisitedBFS() {
    for (int i = 0; i < 6; i++) cout << visitedBFS[i] << "\t"; cout << endl;
}
void DFS(MGraph& G, VerTexType v) {  //从v点开始深度遍历
    int index = LocateVex(G, v);
    if (index == -1) {
        cout << "没有这个结点" << v << endl;
        return;
    }
    if (visited[index] == 1) {  //已经访问过了，就返回。
        return;
    }
    //没有访问过，直接标记访问，操作，没有访问过的邻接点入栈
    visited[index] = 1; //标记当前结点已经访问过了
    cout << v << "\t"; //访问当前结点V，对该结点进行操作，直接输出。
    PrintVisited();
    int j = 0;
    for (j = G.vexnum; j >= 0; j--) {
        if (G.arcs[index][j] == 1 && visited[j] == 0) {
            mystack.push(G.vexs[j]);
        }
    }
    while (!mystack.empty()) {
        VerTexType vex = mystack.top();
        mystack.pop();
        DFS(G, vex);
    }
}

void BFS(MGraph& G, VerTexType v) {   //从v点开始广度遍历
    int index = LocateVex(G, v);
    if (index == -1) {
        cout << "没有这个结点" << v << endl;
        return;
    }
    if (visitedBFS[index] == 1) {
        return;
    }
    //没有被访问过，
    visitedBFS[index] = 1;
    cout << v << "\t";
    PrintVisitedBFS();
    for (int i = 0; i < G.vexnum; i++) {
        if (G.arcs[index][i] == 1 && visitedBFS[i] == 0) {
            //  cout<<"["<<index<<"]["<<i<<"]="<<G.vexs[i]<<endl;
            myqueue.push(G.vexs[i]);
        }
    }
    while (!myqueue.empty()) {
        VerTexType vex = myqueue.front();
        myqueue.pop();
        //cout<<"pop-->"<<vex<<endl;
        BFS(G, vex);

    }
}

void TestDemoGraph() {
    MGraph G;
    CreateMGraph(G);
    PrintVexArc(G);

    cout << "DFS--->" << endl;
    DFS(G, 'b');
    cout << "BFS--->" << endl;
    BFS(G, 'b');
}
int main()
{
    TestDemoGraph();
    return 0;
}
/*
6
8
a
b
c
d
e
f
ab
af
ae
bc
bd
fd
ed
cd



*/

?

?运行结果：

?

加油各位！！