无向图中的桥

Question

桥只能存在于两个铰接点之间或一个铰接点和度数为1的节点之间。这只是一种观察，因为如果顶点是铰接点，那么简单地从该节点断开连接将只给我们提供桥。

请告诉我这是真是假。

Answer 1

/*A sample file should contain edges as follow
1,2
2,3
4,5
5,3
Output will give the set of bridge nodes
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
typedef struct graph
{
  int node;
  struct graph *next;
}graph;
void init(int group[],int index[],graph *g[]);
void create_graph(graph *g[],int node1,int node2,int group[],int index[],int max_nodes);
int max(int a,int b);
int min(int a,int b);
void display(graph *g[],int group[],int max_nodes);
int query(graph *g[],int group[],int max_nodes,int first,int second);
void delete_node(graph *g[],int node1,int node2,int group[],int index[],int max_nodes);
int team=0;
int main()
{
  char filename[50],ch;
  int nodes[MAX][2],temp=0,node1,node2,group[MAX],index[MAX],max_nodes=0,i;
  FILE *fp;
  graph *g[MAX],*p;
  init(group,index,g);
  printf("Enter the filename - ");
  scanf("%s",filename);
  fp=fopen(filename,"r");
  if(fp==NULL)
  {
    printf("File does not exist");
    exit(1);
  }
  while(1)
  {
    ch=fgetc(fp);
    if(isdigit(ch))
    temp=temp*10+(ch-48);
    else
    {
      if(ch!=','&&ch!='\n'&&ch!=EOF)
      exit(1);
      if(ch==',')
      node1=temp;
      else
      {
        node2=temp;
        if(node1>max_nodes)
        max_nodes=node1;
        if(node2>max_nodes)
        max_nodes=node2;
        if(node1!=node2&&node1>0&&node2>0)
        create_graph(g,node1,node2,group,index,max_nodes);
      }
      temp=0;
    }
    if(ch==EOF)
    {
      break;
    }
  }
  display(g,group,max_nodes);
  temp=0;
  fclose(fp);
  fp=fopen(filename,"r");
  printf("Set of bridges existing - \n\n");
  while(1)
  {
    ch=fgetc(fp);
    if(isdigit(ch))
    temp=temp*10+(ch-48);
    else
    {
      if(ch!=','&&ch!='\n'&&ch!=EOF)
      exit(1);
      if(ch==',')
      node1=temp;
      else
      {
        node2=temp;
        if(node1>max_nodes)
        max_nodes=node1;
        if(node2>max_nodes)
        max_nodes=node2;
        if(node1!=node2&&node1>0&&node2>0)
        delete_node(g,node1,node2,group,index,max_nodes);
      }
      temp=0;
    }
    if(ch==EOF)
    {
      break;
    }
  }
  return 0;
}
void init(int group[],int index[],graph *g[])
{
  int i;
  graph *p=NULL;
  for(i=0;i<MAX;i++)
  {
    group[i]=index[i]=0;
    g[i]=(graph *)malloc(sizeof(graph));
    g[i]->node=0;
    g[i]->next=NULL;
  }
}
void create_graph(graph *g[],int node1,int node2,int group[],int index[],int max_nodes)
{
  int temp_index,other_index,i,minimum;
  int stack[MAX],stack_index=0;
  graph *p;
  p=g[node1];
  if(p->next)
  {
    p=p->next;
    while(p)
    {
      if(p->node==node2)
      return;
      p=p->next;
    }
  }
  if(g[node1]->node<g[node2]->node)
  {
    temp_index=node1;
    other_index=node2;
  }
  else
  {
    temp_index=node2;
    other_index=node1;
  }
  p=g[temp_index];
  p->node=p->node+1;
  while(p->next!=NULL)
  p=p->next;
  p->next=(graph *)malloc(sizeof(graph));
  p=p->next;
  p->node=other_index;
  p->next=NULL;
  p=g[other_index];
  p->node=p->node+1;
  while(p->next)
  p=p->next;
  p->next=(graph *)malloc(sizeof(graph));
  p=p->next;
  p->node=temp_index;
  p->next=NULL;
  if(group[temp_index]==group[other_index]&&group[temp_index]==0)
  {
    {
      team++;
      group[temp_index]=group[other_index]=team;
    }
  }
  else
  {
    if(group[temp_index]==0)
    {
      group[temp_index]=group[other_index];
    }
    {
      minimum=min(group[temp_index],group[other_index]);
      group[temp_index]=max(group[temp_index],group[other_index]);
      for(i=1;i<=max_nodes;i++)
      {
        if(group[i]==minimum)
        group[i]=max(group[temp_index],group[other_index]);
      }
    }
  }
}
int max(int a,int b)
{
  if(a>b)
  return a;
  return b;
}
int min(int a,int b)
{
  if(a<b)
  return a;
  return b;
}
void display(graph *g[],int group[],int max_nodes)
{
  int i;
  graph *p;
  printf("Graph\n");
  printf("Id\tGrp\tNodes\n");
  for(i=1;i<=max_nodes;i++)
  {
    printf("%d\t%d\t%d",i,group[i],g[i]->node);
    p=g[i]->next;
    while(p)
    {
      printf(" %d",p->node);
      p=p->next;
    }
    printf("\n");
  }
  printf("\n\n");
}
int query(graph *g[],int group[],int max_nodes,int first,int second)
{
  if(group[first]==group[second])
  return 1;
  else
  return 0;
}
void delete_node(graph *g[],int node1,int node2,int group[],int index[],int max_nodes)
{
  graph *p=NULL;
  int i,temp,stack_index=0,stack[MAX];
  p=g[node1];
  while(p->next->node!=node2&&p->next)
  p=p->next;
  if(p->next)
  {
    p->next=p->next->next;
    g[node1]->node=g[node1]->node-1;
  }
  p=g[node2];
  while(p->next->node!=node1&&p->next)
  p=p->next;
  if(p->next)
  {
    p->next=p->next->next;
    g[node2]->node=g[node2]->node-1;
  }
  team++;
  group[node2]=team;
  stack_index=0;
  temp=node2;
  p=g[temp]->next;
  while(p)
  {
    stack[stack_index++]=p->node;
    p=p->next;
  }
  for(i=0;i<stack_index;i++)
  {
    if(group[stack[i]]!=team)
    {
      group[stack[i]]=team;
      p=g[stack[i]]->next;
      while(p)
      {
        stack[stack_index++]=p->node;
        p=p->next;
      }
    }
  }
  if(query(g,group,max_nodes,node1,node2)==0)
  printf("%d %d\n",node1,node2);
  create_graph(g,node1,node2,group,index,max_nodes);
}

Answer 2

在无向图中，桥只能存在于两个铰接点之间。这直接从定义中说出来：

• 桥是一条边，因此从图中删除它会增加连接组件的数量。
• 如果您删除它的任何端点，则也会增加连接组件的数量，这正是铰接点的定义。

我不确定你所说的零件或者关节点和节点之间的出度为0是什么意思。在无向图中，出度意味着什么？

Here是关于Tarjan算法的很好的幻灯片，包括它在检测图形中的桥和连接点方面的用法。

Answer 3

关键问题是确定可达性关系如何影响顶点v是否为关节顶点。有三种情况：·Root cut-nodes -如果DFS树的根有两个或更多的子节点，它必须是一个关节顶点。第二个子节点的子树的任何边都不可能连接到第一个子节点的子树。·Bridge cut-nodes -如果v的最早可达顶点是v，则删除单边(parentv，v)会断开图的连接。很明显，parentv必须是一个连接顶点，因为它从图中删除了v。顶点v也是关节顶点，除非它是DFS树的叶子。对于任何树叶来说，当你剪掉它的时候都不会掉下来。·Parent cut-nodes -如果v中最早可达的顶点是v的父节点，那么删除父节点必须从树中切断v，除非父节点是根。