데이터 구조 - 인접 표 가 표시 하 는 그림 의 토폴로지 정렬 알고리즘

29221 단어 데이터 구조

  
    
#include < iostream >
using namespace std;

#include
< stdio.h >
#include
< stdlib.h >

#define OK 1
#define NULL 0
#define MAX_VERTEX_NUM 20 //

typedef
char VertexType;
typedef
int VRType;
typedef
int InforType;
typedef
int indegree[MAX_VERTEX_NUM];

typedef
struct ArcNode
{
int adjvex; //
struct ArcNode * nextarc; //
int weight; //
}ArcNode; //

typedef
struct VNode
{
VertexType data;
// ( )
ArcNode * firstarc; //
}VNode, AdjList[MAX_VERTEX_NUM]; //

typedef
struct ALGraph
{
AdjList vertices;
int vexnum, arcnum; //
}ALGraph;


//
void init_ALGraph(ALGraph & g)
{
g.arcnum
= 0 ;
g.vexnum
= 0 ;
}

// v
int LocateVex(ALGraph & G, char v)
{
int i;
for (i = 0 ; v != G.vertices[i].data && i < G.vexnum; i ++ )
;
if (i >= G.vexnum)
return - 1 ;
return i;
}

//
void add_vex(ALGraph & G)
{
cout
<< " : " << endl;
cin
>> G.vexnum;
// getchar(); //
cout << " : " << endl;
for ( int i = 0 ; i < G.vexnum; i ++ )
{
cin
>> G.vertices[i].data; //
G.vertices[i].firstarc = NULL;
// getchar();
}
}

//
void add_arc(ALGraph & G, indegree indegree)
{
ArcNode
* s;
ArcNode
* p;

for ( int k = 0 ; k < G.vexnum; k ++ )
indegree[k]
= 0 ;

cout
<< " : " << endl;
cin
>> G.arcnum;
char v1, v2;
cout
<< " : " << endl;
for (k = 0 ; k < G.arcnum; k ++ )
{
cin
>> v1 >> v2;
int i = LocateVex(G, v1);
int j = LocateVex(G, v2); // v1 , v2 G
++ indegree[j]; // j 1

s
= (ArcNode * ) malloc ( sizeof (ArcNode));
s
-> adjvex = j; // j
s -> nextarc = NULL;
if ( ! G.vertices[i].firstarc)
{
G.vertices[i].firstarc
= s;
}
else
{
for (p = G.vertices[i].firstarc; p -> nextarc; p = p -> nextarc)
;
p
-> nextarc = s;
}
}
}

//
void CreateUDN(ALGraph & G, indegree indegree)
{
add_vex(G);
//
add_arc(G,indegree); //
}


void PrintAdjList(ALGraph & G)
{
int i;
ArcNode
* p;
cout
<< " " << endl;

for (i = 0 ; i < G.vexnum; i ++ )
{
cout
<< " " << i << " " << G.vertices[i].data << " " ;
for (p = G.vertices[i].firstarc; p; p = p -> nextarc)
cout
<< p -> adjvex << " " ;
cout
<< endl;
}
}

//
int TopologicalSort(ALGraph & g, indegree indegree)
{
// G , 1, 0。
ArcNode * q;
int i,k;
int gettop;

int * stack; // 0
stack = ( int * )malloc( g.vexnum * sizeof ( int ) );
int top = 0 ;

for (i = 0 ; i < g.vexnum; i ++ )
if ( 0 == indegree[i]) // 0
stack[ ++ top] = i;
int count = 0 ;

while (top != 0 )
{
gettop
= stack[top -- ];
cout
<< g.vertices[gettop].data << " --> " ;
count
++ ; // i ,

for (q = g.vertices[gettop].firstarc; q; q = q -> nextarc)
{
k
= q -> adjvex;
if ( ! ( -- indegree[k]) ) // i 1, 1 0,
stack[ ++ top] = k;
}
// for
} // while
cout << endl;
if (count < g.vexnum)
return 1 ;
else
return 0 ;
}


int main()
{
ALGraph G;
indegree indegree;
init_ALGraph(G);
//

CreateUDN(G, indegree);
//
PrintAdjList(G); //

TopologicalSort(G, indegree);
return 0 ;
}

좋은 웹페이지 즐겨찾기