图论建图

1.邻接表建图：

        直接开一个N*N的矩阵如果i,j相连则将二维矩阵赋值，否则则为INF。

        虽然简单直观但是遍历效率过低， “并且不能存储重边”。

        遇到点较稀疏的图时空间利用率过低，时间复杂度为O(N*N)

#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 0x3f3f3f3f
using namespace std;
int N,M;
struct node{
  int y,w=maxn;//初始化,没有连接的边默认为maxn
  node(int y1,int w1){y=y1;w=w1;}//构造函数
};
vector<node>G[105];
int main(){
	int i,j,x,y,z;
	cin>>N>>M;   //构图
    while(scanf(\"%d%d%d\",&x,&y,&z)!=EOF){
		G[x].push_back((node){y,z});
	}
	for(int i=1;i<=N;i++)
      for(int j=0;j<G[i].size();j++)
       printf(\"%d %d %d\\n\",i,G[i][j].y,G[i][j].w);
	return 0;
}

            vector + pair ,如果会用pair的话就不用建结构体了,美滋滋..

typedef pair<int,int> pii;
vector<pii>G[maxn];
  //vector<pair<int,int> > G[maxn];
  //加边:
G[u].push_back(make_pair(v,w));
  //遍历从p点出发的边
for(int i=0;i<G[p].size();i++){
    int v=G[p][i].first;
    int w=G[p][i].second;
}

2.链式前向星

    1.结构

          edge存边，edge[i]表示第i条边

          head[i]存以i为起点的第一条边(在edge中的下标)

struct EDGE{
	int next=0;   //下一条边的存储下标(默认0) 
	int to;     //这条边的终点 
	int w;      //权值 
}; 
EDGE edge[500010];

   2.增边        

         若以点i为起点的边新增了一条，在edge中的下标为j.

         那么edge[j].next=head[i];然后head[i]=j.

         即每次新加的边作为第一条边，最后倒序遍历

void Add(int u, int v, int w) {  //起点u, 终点v, 权值w 
	//cnt为边的计数，从1开始计 
	edge[++cnt].next = head[u];
	edge[cnt].w = w;
	edge[cnt].to = v;
	head[u] = cnt;    //第一条边为当前边 
} 

3. 遍历

遍历以st为起点的边

for(int i=head[st]; i!=0; i=edge[i].next)

i开始为第一条边，每次指向下一条(以0为结束标志)  （若下标从0开始，next应初始化-1）

#include <iostream>
using namespace std;
 
#define MAXM 500010
#define MAXN 10010
 
struct EDGE{
	int next;   //下一条边的存储下标 
	int to;     //这条边的终点 
	int w;      //权值 
}; 
EDGE edge[MAXM];
 
int n, m, cnt;
int head[MAXN];  //head[i]表示以i为起点的第一条边 
 
void Add(int u, int v, int w) {  //起点u, 终点v, 权值w 
	edge[++cnt].next = head[u];
	edge[cnt].w = w;
	edge[cnt].to = v;
	head[u] = cnt;    //第一条边为当前边 
} 
 
void Print() {
	int st;
	cout << \"Begin with[Please Input]: \\n\";
	cin >> st;
	for(int i=head[st]; i!=0; i=edge[i].next) {//i开始为第一条边，每次指向下一条(以0为结束标志)若下标从0开始，next应初始化-1 
		cout << \"Start: \" << st << endl;
		cout << \"End: \" << edge[i].to << endl;
		cout << \"W: \" << edge[i].w << endl << endl; 
	}
}
 
int main() {
	int s, t, w;
	cin >> n >> m;
	for(int i=1; i<=m; i++) {
		cin >> s >> t >> w;
		Add(s, t, w);
	}
	Print(); 
	return 0;
}