图
邻接矩阵与邻接表（两者皆可用来表示有向图和无向图）
创建一个基类graph
#pragma once
#include<iostream>
#include<vector>
#include <map>
#include <string>
#include <functional>
#include<algorithm>
#include<queue>
using namespace std;
class graph
{
public:
graph(bool dir = false)
{
directed = dir;
this->nv = 0;
}
graph(vector<string>v, bool dir = false)
{
directed = dir;
nv = v.size();
vertices = v;
for (int i = 0; i < nv; i++)
{
iov[vertices[i]] = i;
}
}
graph(int n, bool dir = false)
{
directed = dir;
nv = n;
vertices.resize(nv);
for (int i = 0; i < nv; i++)
{
vertices[i] = to_string(i);
//vertices.push_back(to_string(i));
iov[vertices[i]] = i;
}
}
virtual void prin() = 0;
virtual void insertv()
{
insertv(to_string(nv));
}
virtual bool insertv(string v)
{
if (iov.find(v) != iov.end())
{
return false;
}
vertices.push_back(v);
iov[v] = nv;
nv++;
return true;
}
virtual bool insertE(string src, string dst, int weight = 1)
{
insertv(src);
insertv(dst);
return insertE(iov[src], iov[dst], weight);
}
virtual bool insertE(int src, int dst, int weight = 1) = 0;
virtual bool removeE(string src, string dst)
{
if (iov.find(src) == iov.end() || iov.find(dst) == iov.end())
{
return false;
}
return removeE(iov[src], iov[dst]);
}
virtual bool removeE(int src, int dst) = 0;
virtual void dfs(string v)
{
if (iov.find(v) == iov.end())
{
return;
}
visited.resize(nv);
for (int i = 0; i < nv; i++)
{
visited[i] = false;
}
dfs(iov[v]);
}
protected:
virtual void dfs(int v) = 0;
int nv;
bool directed;
vector<string>vertices;
map<string, int>iov;
vector<bool>visited;
private:
};
1.首先先看看用邻接矩阵怎么去表示一个图
//在.h中设置
//bool dir判断是否为有向图,默认false为无向图，
vector<vector<int>>adjm;//动态创建邻接矩阵
mgraph(bool dir = false) :graph(dir)
{
}
mgraph(vector<string>v, bool dir = false) :graph(v, dir)
{
setadjm();
}
mgraph(int n, bool dir = false) :graph(n, dir)// n为顶点个数
{
setadjm();
}
//在.cpp文件中设置
void mgraph:: setadjm()
{
adjm.resize(nv);
for (int i = 0; i < nv; i++)
{
adjm[i].resize(nv);
for (int j = 0; j < nv; j++)
{
adjm[i][j] = INT_MAX;
}
}
}
打印生成的邻接矩阵
void mgraph::prin()
{
cout << '\t';
for (int i = 0; i < nv; i++)
{
cout << vertices[i] << '\t';
}
cout << endl;
for (int i = 0; i < nv; i++)
{
cout << vertices[i] << ":\t";
for (int j = 0; j < nv; j++)
{
if (adjm[i][j] == INT_MAX)
{
cout << "-\t";
}
else cout << adjm[i][j] << '\t';
}
cout << endl;
}cout << endl;
}
2.生成邻接表
vector<map<int, int>>adjl;//邻接表
lgraph(bool dir = false) :graph(dir){}
lgraph(vector<string> v, bool dir = false) :graph(v, dir){ setadjl(); }
lgraph(int n, bool dir = false) :graph(n, dir){ setadjl(); }
void lgraph::setadjl()
{
adjl.resize(nv);
for (auto x : adjl)
{
x.clear();
}
}
打印生成邻接表
void lgraph::prin()
{
for (int i = 0; i < nv; i++)
{
cout << vertices[i] << "[" << i << "]" << "-->";
for (auto x : adjl[i])
{
cout << vertices[x.first] << "(" << x.second << ") ";
}cout << endl;
}
}
对邻接矩阵进行插入顶点使用insertV()函数，两点间插入边使用insertE()函数操作，同时对图进行DFS深度优先及BFS广度优先遍历，最后学习Dijkstra最短路径算法和Prim最小生成树算法
这边就不一一举例了直接上代码
首先是.h文件
#pragma once
#include "graph.h"
class mgraph :public graph
{
protected:
vector<vector<int>>adjm;
void setadjm();
public:
mgraph(bool dir = false) :graph(dir)
{
}
mgraph(vector<string>v, bool dir = false) :graph(v, dir)
{
setadjm();
}
mgraph(int n, bool dir = false) :graph(n, dir)
{
setadjm();
}
void prin();
void insertv();
bool insertv(string v);
bool insertE(string src, string dst, int weight = 1);
bool insertE(int src, int dst, int weight = 1);
bool removeE(string src, string dst);
bool removeE(int src, int dst);
void dfs(string v);
void dfs(int v);
void bfs(string v);
void dijkstra(string src);
void prim(string src);
};
.cpp文件
#include "mgraph.h"
void mgraph:: setadjm()
{
adjm.resize(nv);
for (int i = 0; i < nv; i++)
{
adjm[i].resize(nv);
for (int j = 0; j < nv; j++)
{
adjm[i][j] = INT_MAX;
}
}
}
void mgraph::prin()
{
cout << '\t';
for (int i = 0; i < nv; i++)
{
cout << vertices[i] << '\t';
}
cout << endl;
for (int i = 0; i < nv; i++)
{
cout << vertices[i] << ":\t";
for (int j = 0; j < nv; j++)
{
if (adjm[i][j] == INT_MAX)
{
cout << "-\t";
}
else cout << adjm[i][j] << '\t';
}
cout << endl;
}cout << endl;
}
void mgraph::insertv()
{
insertv(to_string(nv));
}
bool mgraph::insertv(string v)
{
bool r = graph::insertv(v);
if (!r)
{
return false;
}
for (int i = 0; i < nv - 1; i++)
{
adjm[i].push_back(INT_MAX);
}
adjm.push_back(vector<int>(nv, INT_MAX));
return true;
}
bool mgraph::insertE(string src, string dst, int weight )
{
return graph::insertE(src, dst, weight);
}
bool mgraph::insertE(int src, int dst, int weight )
{
if (src < 0 || dst < 0 || src >= nv || dst >= nv)
return false;
if (adjm[src][dst] != INT_MAX)
{
return false;
}
if (!directed)
{
adjm[dst][src] = weight;
}
adjm[src][dst] = weight;
}
bool mgraph::removeE(string src, string dst)
{
return graph::removeE(src, dst);
}
bool mgraph::removeE(int src, int dst)
{
if (src < 0 || dst < 0 || src >= nv || dst >= nv)
return false;
if (adjm[src][dst] == INT_MAX)
{
return false;
}
adjm[src][dst] = INT_MAX;
if (!directed)
{
adjm[dst][dst] = INT_MAX;
}
return true;
}
void mgraph::dfs(string v)
{
graph::dfs(v);
}
void mgraph::dfs(int v)
{
cout << vertices[v] << " ";
visited[v] = true;
for (int i = 0; i < nv; i++)
{
if (!visited[i] && adjm[v][i] != INT_MAX)
{
dfs(i);
}
}
}
void mgraph::bfs(string v)
{
if (iov.find(v) == iov.end())
{
return;
}
visited.resize(nv);
for (int i = 0; i < nv; i++)
{
visited[i] = false;
}
queue<int>q;
cout << v << " ";
int iv = iov[v];
visited[iv] = true;
q.push(iv);
int w;
while (!q.empty())
{
w = q.front();
q.pop();
for (int i = 0; i < nv; i++)
{
if (!visited[i] && adjm[w][i] != INT_MAX)
{
cout << vertices[i] << " ";
visited[i] = true;
q.push(i);
}
}
}
}
void mgraph::dijkstra(string src)
{
if (iov.find(src) == iov.end())
{
return;
}
vector<int>d(nv, INT_MAX);
vector<int>from(nv, -1);
vector<bool>known(nv, false);
d[iov[src]] = 0;
int mindis, v;
for (int t = 0; t < nv; t++)
{
mindis = INT_MAX;
v = -1;
for (int i = 0; i < nv; i++)
{
if (known[i] == false && d[i] < mindis){
mindis = d[i];
v = i;
}
}
if (v == -1)
{
break;
}
known[v] = true;
for (int w = 0; w < nv; w++)
{
if (adjm[v][w] != INT_MAX&&!known[w] && d[v] + adjm[v][w] < d[w])
{
d[w] = d[v] + adjm[v][w];
from[w] = v;
}
}
}
for (int i = 0; i < nv; i++)
{
cout << i << '\t';
}
cout << endl;
for (int i = 0; i < nv; i++)
{
cout << vertices[i] << '\t';
}
cout << endl;
for (int i = 0; i < nv; i++)
{
cout << d[i] << '\t';
}
cout << endl;
for (int i = 0; i < nv; i++)
{
cout << (from[i] >= 0 ? vertices[from[i]] : "-") << '\t';
}
cout << endl;
}
void mgraph::prim(string src){
if (iov.find(src) == iov.end())
{
return;
}
vector<int>d(nv, INT_MAX);
vector<int>from(nv, -1);
vector<bool>known(nv, false);
d[iov[src]] = 0;
int mindis, v;
for (int t = 0; t < nv; t++)
{
mindis = INT_MAX;
v = -1;
for (int i = 0; i < nv; i++)
{
if (known[i] == false && d[i] < mindis){
mindis = d[i];
v = i;
}
}
if (v == -1)
{
break;
}
known[v] = true;
for (int w = 0; w < nv; w++)
{
if (adjm[v][w] != INT_MAX&&!known[w] && adjm[v][w] < d[w])
{
d[w] = adjm[v][w];
from[w] = v;
}
}
}
for (int i = 0; i < nv; i++)
{
cout << i << '\t';
}
cout << endl;
for (int i = 0; i < nv; i++)
{
cout << vertices[i] << '\t';
}
cout << endl;
for (int i = 0; i < nv; i++)
{
cout << d[i] << '\t';
}
cout << endl;
for (int i = 0; i < nv; i++)
{
cout << (from[i] >= 0 ? vertices[from[i]] : "-") << '\t';
}
cout << endl;
}
同样对邻接表进行一系列操作
邻接表.h文件
#pragma once
#include "graph.h"
class lgraph :public graph
{
protected:
vector<map<int, int>>adjl;
void setadjl();
public:
lgraph(bool dir = false) :graph(dir){}
lgraph(vector<string> v, bool dir = false) :graph(v, dir){ setadjl(); }
lgraph(int n, bool dir = false) :graph(n, dir){ setadjl(); }
void prin();
void insertv();
bool insertv(string v);
bool insertE(string src, string dst, int weight = 1);
bool insertE(int src, int dst, int weight = 1);
bool removeE(string src, string dst);
bool removeE(int src, int dst);
void dfs(string v);
void dfs(int v);
virtual void bfs(string v);
void shortest(string src);
};
邻接表.cpp文件
#include "lgraph.h"
void lgraph::setadjl()
{
adjl.resize(nv);
for (auto x : adjl)
{
x.clear();
}
}
void lgraph::prin()
{
for (int i = 0; i < nv; i++)
{
cout << vertices[i] << "[" << i << "]" << "-->";
for (auto x : adjl[i])
{
cout << vertices[x.first] << "(" << x.second << ") ";
}cout << endl;
}
}
void lgraph::insertv()
{
insertv(to_string(nv));
}
bool lgraph::insertv(string v)
{
bool r = graph::insertv(v);
if (!r)
{
return false;
}
adjl.push_back(map<int, int>());
return true;
}
bool lgraph::insertE(string src, string dst, int weight )
{
return graph::insertE(src, dst, weight);
}
bool lgraph::insertE(int src, int dst, int weight )
{
if (src < 0 || dst < 0 || src >= nv || dst >= nv)
return false;
if (adjl[src].find(dst) != adjl[src].end())
{
return false;
}
adjl[src].insert(pair<int, int>(dst, weight));
if (!directed)
{
adjl[dst].insert(pair<int, int>(src, weight));
}
return true;
}
bool lgraph::removeE(string src, string dst)
{
return graph::removeE(src, dst);
}
bool lgraph::removeE(int src, int dst)
{
if (src < 0 || dst < 0 || src >= nv || dst >= nv)
return false;
if (adjl[src].find(dst) == adjl[src].end())
{
return false;
}
adjl[src].erase(dst);
if (!directed)
{
adjl[dst].erase(src);
}
return true;
}
void lgraph::dfs(string v)
{
graph::dfs(v);
}
void lgraph::dfs(int v)
{
cout << vertices[v] << " ";
visited[v] = true;
for (auto x : adjl[v])
{
if (!visited[x.first])
{
dfs(x.first);
}
}
}
void lgraph::bfs(string v)
{
if (iov.find(v) == iov.end())
{
return;
}
visited.resize(nv);
for (int i = 0; i < nv; i++)
{
visited[i] = false;
}
queue<int>q;
cout << v << " ";
int iv = iov[v];
visited[iv] = true;
q.push(iv);
int w;
while (!q.empty())
{
w = q.front();
q.pop();
for (auto x : adjl[w])
{
if (!visited[x.first])
{
cout << vertices[x.first] << " ";
visited[x.first] = true;
q.push(x.first);
}
}
}
}
void lgraph::shortest(string src)
{
if (iov.find(src) == iov.end())
{
return;
}
vector<int>d(nv, INT_MAX);
vector<int> from(nv, -1);
d[iov[src]] = 0;
queue <int>q;
q.push(iov[src]);
int v;
while (!q.empty())
{
v = q.front();
q.pop();
for (auto w : adjl[v])
{
if (d[w.first] == INT_MAX)
{
d[w.first] = d[v] + 1;
from[w.first] = v;
q.push(w.first);
}
}
}
for (int i = 0; i < nv; i++)
{
cout << vertices[i] << "(" << d[i] << "," << (from[i] >= 0 ? vertices[from[i]] : "-") << ") ";
}
cout << endl;
}
main()函数测试，自行理解后调整
void main()
{
// vector<string>v = { "aa", "bb", "cc", "dd" };
// lgraph p(true);
// string n1, n2;
// int m;
// cin >> m;
// for (int i = 0; i < m; i++)
// {
// cin >> n1 >> n2;
// p.insertE(n1, n2);
// }
// //p.insertv("x");
// // p.insertE("aa", "cc");
// // p.insertE(1, 3);
// // p.insertE("dd", "ee", 6);
// // p.insertE("x", "ee");
// // p.insertE("p", "q");
// // p.removeE("p", "q");
// p.shortest("c");
// //p.prin();
// // p.dfs("aa");
// //
// // p.bfs("aa");
mgraph g(true);
string n1, n2;
int weight;
int m;
cin >> m;
for (int i = 0; i < m;i++)
{
cin >> n1 >> n2 >> weight;
g.insertE(n1, n2, weight);
}
//g.prin();
//g.dijkstra("a");
g.prim("a");
system("pause");
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
