数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚设计
法律研究C++ 程序，用于查找图中所有前向边
在本部分中，我们将考虑一个 C++ 程序，用于查找图中所有前向边。
算法
用于 topo 函数的算法
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
更新于： 2019 年 7 月 30 日
238 次浏览
广告