-
#include
#include
#include
#define
INFINITY
32767
#define
MAX_VERTEX_NUM
20
typedef
enum{
FALSE,TRUE
}
visited_hc;
typedef
enum{
DG
,DN,UDG
,UDN
}
graphkind_hc;
typedef
struct
arccell_hc
{int
adj;
int
*
info;
}
arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERT EX_NUM];
typedef
struct
{char
vexs[MAX_VERTEX_NUM];
adjmatrix_hc
arcs;
int
vexnum,arcnum;
graphkind_hc kind;
}
mgraph_hc;
typedef
struct
arcnode_hc
{int
adjvex;
struct
arcnode_hc
*
nextarc;
int
*
info;
}
arcnode_hc;
typedef
struct
vnode_hc
{char
data;
arcnode_hc
*
firstarc;
}
vnode_hc,adjlist_hc[MAX_VERTEX_NUM];
typedef
struct
{
adjlist_hc vertices;
int
vexnum,arcnum;
graphkind_hc kind;
}
algraph_hc;
int
locatevex_hc(mgraph_hc
*
g,
char
v)
{int
i,k
=
0;
for
(i
=
0;i
<
g
->
vexnum;i
+
+
)
if
(g
->
vexs[i]
==
v)
{
k
=
i;i
=
g
->
vexnu
m;
}
return
(k);
}
mgraph_hc
*
createudg_hc()
{
mgraph_
hc
*
g;
char
v1,v2;
int
i,j,incinfo;
g
=
(mgraph_hc
*
)malloc(
sizeof
(mgraph
_hc));
g
->
kind
=
UDG;
printf(
请输入图顶点数、边数及该边相关信息
:
);
scanf(
,
&
g
->
vexn
um,
&
g
->
arcnum,
&
incinfo);
printf(
请输入顶点信息
:
);flushall();
for
(i
=
0;i
<
g
->
vexnum;
++
i)scanf(
,
&
g
->
vexs[i]);
for
(i
=
0;i<
/p>
<
g
->
vex
num;
++
i)
for
(j
=
0;j
<
g
->
vexnum;
++
j)
g
->
arcs[i][j]
.
adj
=
0;
printf(
输入一条边依附的顶点
:n
);
flushall();scanf(
,
< br>&
v1,
&
v2);
while
(v1
!=
'#'
&&
v2
!=
< br>'#'
)
{
i
=
locatevex_hc(g,v1);j
=
locatevex_hc(g,v2);
g
->
arcs[i][j]
.
ad
j
=
1;
if
(incinfo)g
->
arcs[i][j]
.
info
=&
inci
nfo;
g
->
arcs[j][i
]
.
adj
=
g
->
arcs[i][j]
.
adj;
g
->
a
rcs[j][i]
.
info
=
g
->
arcs[i][j]
.
info;
flushall();scanf
(
,
&
v1,
&
v2);
}
return
(g);
}
visited_hc
vis[MAX_VERTEX_NUM];
int
firstadjvex_hc(mgraph_hc
*
g,
int
v)
{int
i,k
=-
1;
for
(i
=
0;i
<
g
->
vexnum;i
++
)
if
(g
->
arcs[v][i]
.
ad
j
==
1)
{
k
=
i;i
=
g
->
vexnum;
}
return
(k);
}
int
nextadjvex_h
c(mgraph_hc
*
g,
int
v,
int
w)
{int
i,k
=-
1;
for
(i
=
0;i
<
g
->
vexnum;i
++
)
if
(g
->
arcs[v][i]
.
ad
j
==
1
&&
i
>
w)
{
k
=
i;i
=
g
->
vexnum;
}
return
(k);
}
void
dfs_hc(mgra
ph_hc
*
g,
int
v)
{int
w;
vis[v]
=
TRUE; prin
tf(
,g
->
vexs[v]);
for
(w
=
firstadjvex_hc(g,v);w
>=
0;w
=
nextadjvex_hc(g,v,
w))
if
(
!
vis[w])dfs_hc(g,w);
}