데이터 구조 - 인접 행렬 이 표시 하 는 그림 의 관절 점 구하 기

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 ;
}

좋은 웹페이지 즐겨찾기