데이터 구조 - 인접 표 가 표시 하 는 그림 의 토폴로지 정렬 알고리즘
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
;
}
좋은 웹페이지 즐겨찾기
