原创,未经允许不得转载。
图的建立有两种,邻接矩阵和邻接表。
邻接矩阵适用于图较为密集,(稀疏图太浪费存储空间了),图如果较为稀疏,则使用邻接表为宜,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=;i<m;i++)
{
cin>>start>>to;
p[start].push_back(to);
}
for (int i=1;i<=n;i++)
{
for (int j=;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=;i<m;i++)
{
cin>>start>>to;
p[start].push_back(to);
p[to].push_back(start);
}
for (int i=;i<=n;i++)
{
for (int j=;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=;i<m;i++)
{
node c;
cin>>start>>c.to>>c.cost;
p[start].push_back(c);
}
cout<<endl;
for (int i=;i<=n;i++)
{
for (int j=;j<p[i].size();j++)
{
cout<<i<<" "<<p[i][j].to<<" "<<p[i][j].cost<<" "<<endl;
}
}cout<<endl;
}
无向有权图的建立: