图的建立有两种,邻接矩阵和邻接表。
邻接矩阵适用于图较为密集,(稀疏图太浪费存储空间了),图如果较为稀疏,则使用邻接表为宜,dijkstra算法就是以邻接表为基础的。
有向无权图
#include<iostream> #include <vector> #include <algorithm> #include <queue> #include <stack> using namespace std; #define N 100000+5 vector<int >p[N]; int main() { int n,m; cin>>n>>m; int start,to; for (int i=0;i<m;i++) { cin>>start>>to; p[start].push_back(to); } for (int i=1;i<=n;i++) { for (int j=0;j<p[i].size();j++) { cout<<p[i][j]<<" "; }cout<<endl; }cout<<endl; }
无向无权图的建立:
#include<iostream> #include <vector> #include <algorithm> #include <queue> #include <stack> #include <set> #include <cstdio> #include <iterator> #include <cstring> using namespace std; #define N 100000+5 vector<int >p[N]; int main() { int n,m; cin>>n>>m; int start,to; for (int i=0;i<m;i++) { cin>>start>>to; p[start].push_back(to); p[to].push_back(start); } for (int i=1;i<=n;i++) { for (int j=0;j<p[i].size();j++) { cout<<p[i][j]<<" "; }cout<<endl; }cout<<endl; }
有向有权图的建立:
#include<iostream> #include <vector> #include <algorithm> #include <queue> #include <stack> #include <set> #include <cstdio> #include <iterator> #include <sstream> #include <cmath> #include <list> #include <deque> #include <cstring> using namespace std; #define N 100000+5 struct node { int to,cost; }; vector<node >p[N]; int main() { int n,m; cin>>n>>m; int start,to; for (int i=0;i<m;i++) { node c; cin>>start>>c.to>>c.cost; p[start].push_back(c); } cout<<endl; for (int i=1;i<=n;i++) { for (int j=0;j<p[i].size();j++) { cout<<i<<" "<<p[i][j].to<<" "<<p[i][j].cost<<" "<<endl; } }cout<<endl; }标签:存储,int,back,start,vector,邻接,push,include From: https://www.cnblogs.com/ljq2022/p/17237068.html