C ++程序查找图形中的所有前缘
在本节中，我们将考虑使用C++程序查找图中的所有前向边。
演算法
对于top功能
Begin
Declare function topo() Declare pointer v, m[][5] and i of the integer datatype.
x = new Node_Inf.
x->n = i.
x->S_Time = c.
Call function Push_Node(x).
v[i] = 1.
for (int j = 0; j < 5; j++)
if (m[i][j] == 0) then
continue;
else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j)) then
if (x->S_Time < srch_Node(j)) then
Print "Forward Edge is between ".
Print the values of forward edges.
continue;
else if (m[i][j] == 1 && v[j] == 0) then
c++;
Print "Forward Edge is between "
Print the values of forward edges.
Call topo(v,m,j) function.
c++.
x = pop() x->L_Time = c.
Call Store_Node(x) function to store values into nodes.
Return.
End.示例
#include<iostream>
#include<conio.h>
using namespace std;
struct Node_Inf {
int n;
int L_Time, S_Time;
}
*x = NULL, *y = NULL;
struct Node_1 {
Node_Inf *ptn;
Node_1 *nxt;
}
*tp = NULL, *p = NULL, *npr = NULL;
struct Node_2 {
Node_2 *lnk;
Node_Inf *ptn1;
}
*hd = NULL, *m = NULL, *n = NULL, *npr1 = NULL;
int c = 0;
void Push_Node(Node_Inf *ptr) {
npr = new Node_1;
npr->ptn = ptr;
npr->nxt = NULL;
if (tp == NULL) {
tp = npr;
} else {
npr->nxt = tp;
tp = npr;
}
}
Node_Inf *pop() {
if (tp == NULL) {
cout<<"underflow\n";
} else {
p = tp;
tp = tp->nxt;
return(p->ptn);
delete(p);
}
}
void Store_Node(Node_Inf *ptr1) {
npr1 = new Node_2;
npr1->ptn1 = ptr1;
npr1->lnk = NULL;
if (c == 0) {
hd = npr1;
m = hd;
m->lnk = NULL;
c++;
} else {
m = hd;
npr1->lnk = m;
hd = npr1;
}
}
int srch_Node(int j) {
Node_2 *t = hd;
while (t != NULL) {
if ((t->ptn1)->n == j)
{
break;
} else {
t = t->lnk;
continue;
}
}
return (t->ptn1)->L_Time;
}
int Exist_in_Stack(int j) {
int flag = 0;
p = tp;
while (p != NULL) {
if ((p->ptn)->n == j) {
flag = 1;
return flag;
}
p = p->nxt;
}
return flag;
}
void topo(int *v, int m[][5], int i) {
x = new Node_Inf;
x->n = i;
x->S_Time = c;
Push_Node(x);
v[i] = 1;
for (int j = 0; j < 5; j++) {
if (m[i][j] == 0)
continue;
else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j)) {
if (x->S_Time < srch_Node(j)) {
cout<<"\nForward Edge is between "<<i<<" and "<<j<<endl;
}
continue;
} else if (m[i][j] == 1 && v[j] == 0) {
c++;
cout<<"\nForward Edge is between "<<i<<" and "<<j<<endl;
topo(v,m,j);
}
}
c++;
x = pop();
x->L_Time = c;
Store_Node(x);
return;
}
int main() {
int v[5],m[5][5];
for (int i = 0; i < 5; i++)
v[i] = 0;
for (int i = 0; i < 5; i++) {
cout<<" Enter the values of matrix::"<<i + 1<<endl;
for(int j = 0; j < 5; j++) {
cin>>m[i][j];
}
}
topo(v,m,0);
getch();
}输出结果
Enter the values of matrix:1 0 1 0 1 0 Enter the values of matrix:2 1 0 0 1 0 Enter the values of matrix:3 1 0 0 0 1 Enter the values of matrix:4 0 1 1 0 0 Enter the values of matrix:5 1 1 0 0 0 Forward Edge is between 0 and 1 Forward Edge is between 1 and 3 Forward Edge is between 3 and 2 Forward Edge is between 2 and 4 Forward Edge is between 0 and 3