关节点算法
看严蔚敏的书太郁闷了,公式对的,代码完全不能用,谁能帮改下下面代码哪里错了?还有当DFS到某个叶子节点n的时候,假如这个叶子节点n没有回边,那么他的low[n]=多少,low[n]=min{visited[n],low[w],low[k]},是n的父节点的值吗,还是等于visited[n]?
#include<iostream>
#include<stdlib.h>
using namespace std;
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef char VertexType;
typedef enum{DG,DN,UDG,UDM} GraphKind;
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,*AdjList;
typedef struct {
AdjList vertices;
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
int LocateVex(ALGraph G,VertexType v)
{
for(int i=0;i<G.vexnum;i++)
if(G.vertices[i].data==v) return i;
return G.vexnum;}
Status CreateUDG(ALGraph &G)
{
G.kind=UDG; //无向图
cin>>G.vexnum>>G.arcnum;
if(!(G.vertices=new VNode[G.vexnum])) exit(OVERFLOW);
for(int i=0;i<G.vexnum;i++) {
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;}
VertexType v1,v2;
ArcNode *p,*q;
int i,j,k=0;
for(;k<G.arcnum;k++) {
do
{
cin>>v1>>v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
}while(i==G.vexnum||j==G.vexnum);
p=new ArcNode;
q=new ArcNode;
if(!p||!q) exit(OVERFLOW);
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
q->adjvex=i;
q->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=q;
}
return OK;
}
void DFSArticul(ALGraph G,int v,int *visited,int &count,int *low){
int min,w;
visited[v]=min=++count;
for(ArcNode *p=G.vertices[v].firstarc;p;p=p->nextarc){
w=p->adjvex;
if(!visited[w]){
DFSArticul(G,w,visited,count,low);
if(low[w]<min) min=low[w];
if(low[w]>=visited[v]) cout<<G.vertices[v].data<<" ";}
else if(((visited[w]-1)!=visited[v])&&(visited[w]<min)) min=visited[w];}
low[v]=min;
}
void FindArticul(ALGraph G){
int i,j,v,count=1,*low,*visited=new int[G.vexnum];
low=new int[G.vexnum];
if(!visited||!low) exit(OVERFLOW);
for(i=0;i<G.vexnum;i++) visited[i]=0;
visited[0]=1;
ArcNode *p=G.vertices[0].firstarc;
if(p){
v=p->adjvex;
DFSArticul(G,v,visited,count,low);
if(count<G.vexnum){
cout<<G.vertices[0].data<<" ";
for(i=0;i<G.vexnum;i++)
if(!visited[i])
DFSArticul(G,i,visited,count,low);}
}
cout<<endl;
// for(i=0;i<G.vexnum;i++) cout<<i<<" "<<visited[i]<<" "<<low[i]<<endl;
}
int main(){
ALGraph G;
CreateUDG(G);
FindArticul(G);
system("pause");
return 0;}