Special minimum spanning tree
-
All algorithms for MST I meet, uses indirect graph and search minimum weight. I need a bit other: my graph is directed, weights are unimportant, all are = 1. Is not necessary find minimal tree, but ANY tree without cycles, although tree with minimal number of edges will be nice. Most important is - graph must be directed.
-
All algorithms for MST I meet, uses indirect graph and search minimum weight. I need a bit other: my graph is directed, weights are unimportant, all are = 1. Is not necessary find minimal tree, but ANY tree without cycles, although tree with minimal number of edges will be nice. Most important is - graph must be directed.
Problem is with directed graph, because is possible many vertex links to one. It is reverse tree. This means,that is impossible leaving spanning tree. Question is another: how detect cycles and remove all cycles?
-
All algorithms for MST I meet, uses indirect graph and search minimum weight. I need a bit other: my graph is directed, weights are unimportant, all are = 1. Is not necessary find minimal tree, but ANY tree without cycles, although tree with minimal number of edges will be nice. Most important is - graph must be directed.
#include
#include
int a,b,u,v,n,i,j,ne=1;
int visited[10]= {
0
}
,min,mincost=0,cost[10][10];
void main() {
clrscr();
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the adjacency matrix:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) {
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
while(ne