1982找出图中12处不合理_数据结构和算法

Description
使用图的深度遍历实现的邻接表存储结构和基本操作函数，在此基础上实现图的广度遍历算法并加以测试。注意正确使用队列存储结构。

输入格式
第一行：输入0到3之间整数(有向图:0,有向网:1,无向图:2,无向网:3)；
第二行：输入顶点数和边数；
第三行：输入各个顶点的值（字符型，长度〈3）；(遍历从输入的第一个顶点开始)
第四行：输入每条弧(边)弧尾和弧头(以空格作为间隔),如果是网还要输入权值；

输出格式
输出对图广度遍历的结果

输入样例
0
3 3
a b c
a b
b c
c b

输出样例
a b c

提示
注意题目的邻接表采用头插法，也就是后出现的边节点插入到邻接表的表头。

一、邻接矩阵存储：

#include <cstdio> #include <iostream> using namespace std; int Map[1000][1000] = { 
   0}, v[1000] = { 
   0}; char point[1000] = { 
   0}; int type; int n,m; int findIndex(char ch) { 
    int i; for (i = 1; i <= n; i++) if (ch == point[i]) return i; return -1; } void bfs(int x) { 
    v[x] = 1; int q[] = { 
   0}, f = 0, r = 0; q[r++] = x; int i; while (f!=r) { 
    int cur_index = q[f++]; cout<<point[cur_index]<<' '; for (i = n; i >= 1; i--) if (Map[cur_index][i] > 0 && v[i] == 0) { 
    q[r++] = i; v[i] = 1; } } cout<<endl; } int main() { 
    cin>>type>>n>>m; int i; char c1, c2; int w; //输入图顶点 for (i = 1; i <= n; i++) cin>>point[i]; //输入边信息 for (i = 1; i<= n; i++) { 
    //(有向图:0,有向网:1,无向图:2,无向网:3) if (type == 1 || type == 3) cin>>c1>>c2>>w; else cin>>c1>>c2; int index1 = findIndex(c1), index2 = findIndex(c2); if(type == 0) Map[index1][index2] = 1; else if (type == 1) Map[index1][index2] = w; else if (type == 2) Map[index1][index2] = Map[index2][index1] = 1; else if (type == 3) Map[index1][index2] = Map[index2][index1] = w; } for (i = 1; i <= n; i++) if (v[i] == 0) bfs(i); return 0; } 

二、邻接表存储：

#include <cstdio> #include <iostream> #include <vector> using namespace std; typedef struct edge { 
    int w; int index; } Edge; int n, m, type; char point[1000] = { 
    0 }; int v[1000] = { 
    0 }; vector<Edge> Map[1000];//邻接表 int findIndex(char ch) { 
    int i; for (i = 1; i <= n; i++) if (ch == point[i]) return i; return -1; } void bfs(int x) { 
    v[x] = 1; int q[] = { 
    0 }, f = 0, r = 0; q[r++] = x; int i; while (f != r) { 
    int cur_index = q[f++]; cout << point[cur_index] << ' '; for (i = Map[cur_index].size()-1; i >= 0; i--)//vector的下标是从0开始 if (v[Map[cur_index][i].index] == 0) { 
    q[r++] = Map[cur_index][i].index; v[Map[cur_index][i].index] = 1; } } cout << endl; } int main() { 
    cin >> type >> n >> m; int i; char c1, c2; int w = 0; //输入图顶点 for (i = 1; i <= n; i++) cin >> point[i]; //输入边信息 for (i = 1; i <= n; i++) { 
    //(有向图:0,有向网:1,无向图:2,无向网:3) if (type == 1 || type == 3) cin >> c1 >> c2 >> w; else cin >> c1 >> c2; int index1 = findIndex(c1), index2 = findIndex(c2); Edge temp = { 
   0}; if (type == 0) { 
    temp.w = 1; temp.index = index2; Map[index1].push_back(temp); } else if (type == 1) { 
    temp.w = w; temp.index = index2; Map[index1].push_back(temp); } else if (type == 2) { 
    temp.w = 1; temp.index = index2; Map[index1].push_back(temp); temp.index = index1; Map[index2].push_back(temp); } else if (type == 3) { 
    temp.w = w; temp.index = index2; Map[index1].push_back(temp); temp.index = index1; Map[index2].push_back(temp); } } for (i = 1; i <= n; i++) if (v[i] == 0) bfs(i); return 0; } 

今天的文章
1982找出图中12处不合理_数据结构和算法分享到此就结束了，感谢您的阅读。