토폴로지 정렬 및 관건 경로
46162 단어 데이터 구조
보조 배열:
프로 세 스
#include
#include
using namespace std;
struct Node
{
int from;
int to;
Node * head_same;
Node * tail_same;
};
struct First_Node
{
string name;
Node * in_node;
Node * out_node;
};
struct Graph
{
int Vex_num, Edge_num;
First_Node * Arr;
};
int Get_Location(Graph T, string name)
{
for(int i = 1; i <= T.Vex_num; i++)
{
if(T.Arr[i].name == name)
return i;
}
return -1;
}
void Create_Graph(Graph & T)
{
cin>>T.Vex_num>>T.Edge_num;
T.Arr = new First_Node[T.Vex_num + 1];
for(int i = 1; i <= T.Vex_num; i++)
{
cin>>T.Arr[i].name;
T.Arr[i].in_node = nullptr;
T.Arr[i].out_node = nullptr;
}
int x, y; string n1, n2;
for(int i = 1; i <= T.Edge_num; i++)
{
cin>>n1>>n2;
x = Get_Location(T,n1);
y = Get_Location(T,n2);
Node * s = new Node;
s->from = x;s->to = y;
s->head_same = T.Arr[y].in_node;
T.Arr[y].in_node = s;
s->tail_same = T.Arr[x].out_node;
T.Arr[x].out_node = s;
}
}
void Find_Indegree(Graph T,int Indegree[])
{
for(int i = 1; i <= T.Vex_num; i++)
{
int num = 0;
Node * s = T.Arr[i].in_node;
while(s != nullptr)
{
num++;
s = s->head_same;
}
Indegree[i] = num;
}
}
void Topo_Sort(Graph T)
{
int Indegree[10];
Find_Indegree(T,Indegree);
stack<int> S;
for(int i = 1; i <= T.Vex_num; i++)
{
if(Indegree[i] == 0)
S.push(i);
}
int m = 1, tops[10];
while(!S.empty())
{
int k = S.top();S.pop();
tops[m] = k;
m++;
Node * s = T.Arr[k].out_node;
while(s != nullptr)
{
k = s->to;
Indegree[k]--;
if(Indegree[k] == 0)
S.push(k);
s = s->tail_same;
}
}
if(m - 1 == T.Vex_num)
{
for(int i = 1; i <= T.Vex_num; i++)
cout<<tops[i]<<"\t";
}else{
cout<<0;
}
}
int main()
{
Graph T;
Create_Graph(T);
Topo_Sort(T);
}
/*
6 8
v1 v2 v3 v4 v5 v6
v1 v6
v1 v5
v1 v3
v2 v3
v3 v4
v4 v6
v5 v6
v5 v4
*/
중요 경로
#include
#include
#include
using namespace std;
struct Node
{
int from;
int to;
Node * head_same;
Node * tail_same;
int time;
};
struct First_Node
{
string name;
Node * in_node;
Node * out_node;
};
struct Graph
{
int Vex_num, Edge_num;
First_Node * Arr;
};
int Get_Location(Graph T, string name)
{
for(int i = 1; i <= T.Vex_num; i++)
{
if(T.Arr[i].name == name)
return i;
}
return -1;
}
void Create_Graph(Graph & T)
{
cin>>T.Vex_num>>T.Edge_num;
T.Arr = new First_Node[T.Vex_num + 1];
for(int i = 1; i <= T.Vex_num; i++)
{
cin>>T.Arr[i].name;
T.Arr[i].in_node = nullptr;
T.Arr[i].out_node = nullptr;
}
int x, y, time; string n1, n2;
for(int i = 1; i <= T.Edge_num; i++)
{
cin>>n1>>n2>>time;
x = Get_Location(T,n1);
y = Get_Location(T,n2);
Node * s = new Node;
s->from = x;s->to = y;
s->head_same = T.Arr[y].in_node;
T.Arr[y].in_node = s;
s->tail_same = T.Arr[x].out_node;
T.Arr[x].out_node = s;
s->time = time;
}
}
bool Topo_Sort(Graph T,int topo[])
{
int Indegree[10];
for(int i = 1; i <= T.Vex_num; i++)
{
int num = 0;
Node * s = T.Arr[i].in_node;
while(s != nullptr)
{
num++;
s = s->head_same;
}
Indegree[i] = num;
}
int m = 1;stack<int> S;
for(int i = 1; i <= T.Vex_num; i++)
if(Indegree[i] == 0) S.push(i);
while(!S.empty())
{
int k = S.top();S.pop();
topo[m] = k;m++;
Node * s = T.Arr[k].out_node;
while(s != nullptr)
{
int j = s->to;
Indegree[j]--;
if(Indegree[j] == 0)
S.push(j);
s = s->tail_same;
}
}
if(m - 1 != T.Vex_num)
return 0;
else
return 1;
}
void CriticalPath(Graph T)
{
int topo[10];
if(!Topo_Sort(T,topo))
return;
int ve[10],vl[10];
memset(ve,0,sizeof(ve));
for(int i = 1; i <= T.Vex_num; i++)
{
Node * s = T.Arr[topo[i]].out_node;
while(s != nullptr)
{
if(ve[topo[i]] + s->time > ve[s->to])
ve[s->to] = ve[topo[i]] + s->time;
s = s->tail_same;
}
}
for(int i = 1; i <= T.Vex_num; i++)
vl[i] = ve[T.Vex_num];
for(int i = T.Vex_num; i >= 1; i--)
{
Node * s = T.Arr[topo[i]].in_node;
while(s != nullptr)
{
if(vl[s->from] > vl[s->to] - s->time)
vl[s->from] = vl[s->to] - s->time;
s = s->head_same;
}
}
for(int i = 1; i <= T.Vex_num; i++)
{
Node * s = T.Arr[i].out_node;
int e, l;
while(s != nullptr)
{
e = ve[i];
l = vl[s->to] - s->time;
if(e == l)
cout<<T.Arr[i].name<<"\t"<<T.Arr[s->to].name<<endl;
s = s->tail_same;
}
}
}
int main()
{
Graph T;
Create_Graph(T);
CriticalPath(T);
}
/*
9 11
v1 v2 v3 v4 v5 v6 v7 v8 v9
v1 v2 6
v1 v3 4
v1 v4 5
v2 v5 1
v3 v5 1
v5 v7 9
v5 v8 7
v7 v9 2
v8 v9 4
v4 v6 2
v6 v8 4
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.