邻接矩阵表示法是一种图的表示方法，其中每个顶点都有一个唯一的索引，而每条边则由两个顶点之间的连接确定。深度优先遍历（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 */
运行结果：
加油各位！！
