更新記錄
【1】2020.05.20-00:27
1.完善內容
【2】2020.07.23-13:59
1.一點點修改
正文
在學習圖論的時候，你首先要學習的就是圖的存盤
鄰接矩陣占空間太大
前向星效率不是很高
于是乎我們就開始使用鏈式前向星
存盤
鏈式前向星使用結構體陣列存邊
struct edge{
int nextarray;
int nextpoint;
int w;
};
\(edge[i]\)表示所有已存盤的邊中的第i條邊
\(head[i]\)表示以\(i\)為起點的所有邊中的第一條
\(nextarray\)表示下一條邊的陣列下標
\(nextpoint\)表示這條邊的終點
\(w\)表示權值
添加
void add(int from,int to,int w){
edge[++num].nextarray=head[from];
edge[num].nextpoint=to;
edge[num].w=w;
head[from]=num;
}
首先我們要明白，添加邊時為倒序添加
也就是說，按遍歷的順序來看，第一條邊最后才被遍歷到，新加的這條邊反而是第一條要進行遍歷邊
那么我們首先讓\(num\)自增，表示所有邊的條數+1（\(++num\)）
由于是倒序添加，所以原來最先要訪問的邊變成了第二條要訪問的邊
- 我們先讓新添加的邊的下一條邊的陣列下標改為當前最先要訪問的邊的陣列下標
\(（edge[++num].nextarray=head[from]）\) - 然后把最先要訪問的邊的陣列下標改為新添加的邊的陣列下標
\(（head[from]=num）\)
終點與權值不變，原樣復制過去
遍歷
通過觀察發現，第一條邊在添加時\(head[from]\)為0
所以其nextarray為0
這可以用來當作程式終止的條件
所以我們遍歷以i為起點的所有邊就可以這么寫：
for(int o=head[i];o!=0;o=edge[o].nextarray)
或是
for(int o=head[i];o;o=edge[o].nextarray)
o!=0意為只要沒到最后一條邊，就繼續往下遍歷
完整程式
#include<iostream>
using namespace std;
struct Edge{
int nexta;
int nextp;
int w;
}edge[1001];
int num,head[1001],n,f,t,m,w;
inline void add(int from,int to,int w){
edge[++num].nexta=head[from];
edge[num].nextp=to;edge[num].w=w;
head[from]=num;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>f>>t>>w;add(f,t,w);
}
for(int i=1;i<=m;i++)
for(int o=head[i];o!=0;o=edge[o].nexta)
cout<<i<<"->"<<edge[o].nextp<<" "<<edge[o].w<<"\n";
}
注意如果是無向圖時，同一條邊要存盤兩遍，即兩個方向各存一遍
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/49688.html
標籤：其他
上一篇：Linux設定免密登陸