데이터 구조 - 인접 행렬 이 표시 하 는 그림 의 관절 점 구하 기
33397 단어 데이터 구조
#include
<
iostream
>
using
namespace
std;
#include
<
stdio.h
>
#include
<
stdlib.h
>
#define
OK 1
#define
NULL 0
#define
MAX_VERTEX_NUM 20
//
//
int
count;
int
visited[MAX_VERTEX_NUM];
//
int
low[MAX_VERTEX_NUM];
typedef
char
VertexType;
typedef
int
VRType;
typedef
int
InforType;
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;
//
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)
{
ArcNode
*
s,
*
t;
ArcNode
*
p;
cout
<<
"
:
"
<<
endl;
cin
>>
G.arcnum;
char
v1, v2;
cout
<<
"
:
"
<<
endl;
for
(
int
k
=
0
; k
<
G.arcnum; k
++
)
{
cin
>>
v1
>>
v2;
int
i
=
LocateVex(G, v1);
int
j
=
LocateVex(G, v2);
//
v1 , v2 G
s
=
(ArcNode
*
) malloc (
sizeof
(ArcNode));
t
=
(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;
}
t
->
adjvex
=
i;
//
j
t
->
nextarc
=
NULL;
if
(
!
G.vertices[j].firstarc)
{
G.vertices[j].firstarc
=
t;
}
else
{
for
(p
=
G.vertices[j].firstarc; p
->
nextarc; p
=
p
->
nextarc)
;
p
->
nextarc
=
t;
}
}
}
//
void
CreateUDN(ALGraph
&
G)
{
add_vex(G);
//
add_arc(G);
//
}
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;
}
}
void
DFSArticul(ALGraph
&
g,
int
v)
{
int
min;
int
w;
ArcNode
*
q;
visited[v]
=
min
=++
count;
//
for
(q
=
g.vertices[v].firstarc; q; q
=
q
->
nextarc)
//
v
{
w
=
q
->
adjvex;
//
w v
if
(
0
==
visited[w])
//
w ， v
{
DFSArticul(g,w);
//
low[w]
if
(low[w]
<
min)
min
=
low[w];
if
(low[w]
>=
visited[v])
cout
<<
g.vertices[v].data
<<
"
"
<<
endl;
//
low[w] >= visited[v] ， v v ，
//
，low[w] visited[i]
//
v ， visited[v]
}
else
if
(visited[w]
<
min)
//
w ， v
{
min
=
visited[w];
}
}
//
for
low[v]
=
min;
}
//
DFSArticul
//
void
FindArticul(ALGraph
&
g)
{
//
count
=
1
;
visited[
0
]
=
1
;
//
0
for
(
int
i
=
1
; i
<
g.vexnum; i
++
)
visited[i]
=
0
;
//
ArcNode
*
p;
p
=
g.vertices[
0
].firstarc;
DFSArticul(g,p
->
adjvex);
//
p
if
(count
<
g.vexnum)
//
，
{
cout
<<
g.vertices[
0
].data
<<
"
"
<<
endl;
while
(p
->
nextarc)
//
{
p
=
p
->
nextarc;
if
(
0
==
visited[p
->
adjvex])
DFSArticul(g,p
->
adjvex);
}
//
while
}
//
if
}
//
FindArticul
int
main()
{
ALGraph G;
CreateUDN(G);
PrintAdjList(G);
//
FindArticul(G);
return
0
;
}
좋은 웹페이지 즐겨찾기
