图的表示一般有邻接列表和邻接矩阵,我学术不精,偏爱邻接列表
邻接表结构的定义
#define MAX_SIZE 1024 typedef struct _EdgeNode //与节点连接的边的定义 { int weight;//可有可无的权重这题不需要但我习惯增加权重 int adjvex; struct _EdgeNode* next; }EdgeNode; typedef struct _VertexNode //顶点节点 { char data; struct _EdgeNode* first; }VertexNode,AdjList; typedef struct _AdjListGraph //图 { AdjList* adjList; int vex; int edge; }AdjListGraph;
邻接表的初始化
void Init(AdjListGraph& G) { G.adjList = new AdjList[MAX_SIZE]; G.edge = 0; G.edge = 0; }
邻接表的创建
/*图的创建*/ void Create(AdjListGraph& G) { cout << "请输入该图的顶点数以及边数" << endl; cin >> G.vex >> G.edge; cout << "请输入相关顶点" << endl; for (int i = 0; i < G.vex; i++) { cin >> G.adjList[i].data; G.adjList[i].first = NULL;//就是这个地方出了问题关键 } char a1, a2;//保存输入的顶点的字符 int i1, i2;//保存顶点在数组中的下标 cout << "请输入相关联边的顶点" << endl; for (int i = 0; i < G.edge; i++) { cin >> a1 >> a2; i1 = Location(G, a1); i2 = Location(G, a2); if (i1 != -1 && i2 != -1)//寻找到位置 { EdgeNode* tmp = new EdgeNode; tmp->adjvex = i2; tmp->next = G.adjList[i1].first; G.adjList[i1].first = tmp; } } }
邻接表的深度遍历
深度优先遍历思想：
首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；
当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直到所有的顶点都被访问过。
使用深度优先搜索来遍历这个图的具体过程是：
- 首先从一个未走到过的顶点作为起始顶点，比如 A 顶点作为起点。
- 沿 A 顶点的边去尝试访问其它未走到过的顶点，首先发现 E 号顶点还没有走到过，于是访问 E 顶点。
- 再以 E 顶点作为出发点继续尝试访问其它未走到过的顶点，接下来访问 D 顶点。
- 再尝试以 D 顶点作为出发点继续尝试访问其它未走到过的顶点。
- 但是，此时沿 D 顶点的边，已经不能访问到其它未走到过的顶点，接下来返回到 E 顶点。
- 返回到 E 顶点后，发现沿 E 顶点的边也不能再访问到其它未走到过的顶点。此时又回到顶点 A（D->E->A），再以 A 顶点作为出发点继续访问其它未走到过的顶点，于是接下来访问 C 顶点。
- 。。。。。。。。。。
- 最终访问的结果是 A -> E -> D -> C -> B(答案不唯一)
/*对图上的顶点进行深度遍历*/ void DFS(AdjListGraph& G, int v) { int next = -1; if (visited[v]) return; cout << G.adjList[v].data << " "; visited[v] = true;//设置为已访问 /*EdgeNode* temp = new EdgeNode; temp = G.adjList[v].first;*/ EdgeNode* temp = G.adjList[v].first; while (temp) { next = temp->adjvex; temp = temp->next; if(visited[next]==false) DFS(G, next); } } /*对所有顶点进行深度遍历*/ void DFS_Main(AdjListGraph& G) { for (int i = 0; i < G.vex; i++) if (visited[i] == false) DFS(G, i); }
邻接表的广度遍历
广度优先遍历思想 :
首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点;
然后对每个相邻的顶点，再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。
/*对图上的顶点进行广度遍历*/ void BFS(AdjListGraph& G, int v) { queue<int> q; int cur; int next; q.push(v); while (!q.empty())//队列非空 { cur = q.front();//取队头元素 if (visited[cur] == false)//当前顶点还没有被访问 { cout << G.adjList[cur].data << " "; visited[cur] = true; } q.pop();//出队列 EdgeNode* tp = G.adjList[cur].first; while (tp!=NULL) { next = tp->adjvex; tp = tp->next; q.push(next);//将第一个邻接点入队 } } } /*对所有顶点进行广度遍历*/ void BFS_Main(AdjListGraph& G) { for (int i = 0; i < G.vex; i++) { if (visited[i] == false) BFS(G, i); } }
且看此完整图
#include<iostream> #include<queue> using namespace std; #define MAX_SIZE 1024 typedef struct _EdgeNode //与节点连接的边的定义 { int weight;//可有可无的权重这题不需要但我习惯增加权重 int adjvex; struct _EdgeNode* next; }EdgeNode; typedef struct _VertexNode //顶点节点 { char data; struct _EdgeNode* first; }VertexNode,AdjList; typedef struct _AdjListGraph //图 { AdjList* adjList; int vex; int edge; }AdjListGraph; bool visited[MAX_SIZE];//全局数组，用来记录节点是否已被访问 void Init(AdjListGraph& G) { G.adjList = new AdjList[MAX_SIZE]; G.edge = 0; G.edge = 0; for (int i = 0; i < MAX_SIZE; i++) { visited[i] = false; } } /*通过顶点对应的字符寻找顶点在图中的邻接点*/ int Location(AdjListGraph& G, char c) { for (int i = 0; i < G.vex; i++) { if (G.adjList[i].data == c) return i; } return -1; } /*图的创建*/ void Create(AdjListGraph& G) { cout << "请输入该图的顶点数以及边数" << endl; cin >> G.vex >> G.edge; cout << "请输入相关顶点" << endl; for (int i = 0; i < G.vex; i++) { cin >> G.adjList[i].data; G.adjList[i].first = NULL;//就是这个地方出了问题关键 } char a1, a2;//保存输入的顶点的字符 int i1, i2;//保存顶点在数组中的下标 cout << "请输入相关联边的顶点" << endl; for (int i = 0; i < G.edge; i++) { cin >> a1 >> a2; i1 = Location(G, a1); i2 = Location(G, a2); if (i1 != -1 && i2 != -1)//寻找到位置 { EdgeNode* tmp = new EdgeNode; tmp->adjvex = i2; tmp->next = G.adjList[i1].first; G.adjList[i1].first = tmp; } } } /*对图上的顶点进行深度遍历*/ void DFS(AdjListGraph& G, int v) { int next = -1; if (visited[v]) return; cout << G.adjList[v].data << " "; visited[v] = true;//设置为已访问 /*EdgeNode* temp = new EdgeNode; temp = G.adjList[v].first;*/ EdgeNode* temp = G.adjList[v].first; while (temp) { next = temp->adjvex; temp = temp->next; if(visited[next]==false) DFS(G, next); } } /*对所有顶点进行深度遍历*/ void DFS_Main(AdjListGraph& G) { for (int i = 0; i < G.vex; i++) if (visited[i] == false) DFS(G, i); } /*对图上的顶点进行广度遍历*/ void BFS(AdjListGraph& G, int v) { queue<int> q; int cur; int next; q.push(v); while (!q.empty())//队列非空 { cur = q.front();//取队头元素 if (visited[cur] == false)//当前顶点还没有被访问 { cout << G.adjList[cur].data << " "; visited[cur] = true; } q.pop();//出队列 EdgeNode* tp = G.adjList[cur].first; while (tp!=NULL) { next = tp->adjvex; tp = tp->next; q.push(next);//将第一个邻接点入队 } } } /*对所有顶点进行广度遍历*/ void BFS_Main(AdjListGraph& G) { for (int i = 0; i < G.vex; i++) { if (visited[i] == false) BFS(G, i); } } int main() { /* AdjList G; initAdjList(G); creatAdjList(G); DFS_main(G); */ AdjListGraph G; //初始化 Init(G); //创建图 Create(G); cout << "深度遍历" << endl; DFS_Main(G); //cout << "广度遍历" << endl; //BFS_Main(G); }
补充
尴尬第一次发表忘记发表结果
