gpt4 book ai didi

c - 用DFS寻找无向图的连接点

转载 作者:行者123 更新时间:2023-11-30 17:13:36 24 4
gpt4 key购买 nike

我正在尝试实现一个程序,以使用 DFS 查找无向图的接合点。我错过了一个基本的指针解除引用概念来检索给定顶点的邻接顶点。错误的说法还请指正。

#include <stdio.h>
#include <stdlib.h>
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
#define NIL -1

// A structure to represent an adjacency list node
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};

struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}

struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;

// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;

return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the begining
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}

int isArticulationPoint(int,int,struct Graph*);
void APUtil(int, int*, int*, int*, int*, int*,struct Graph*);

主程序,包括示例图。

int main()
{

int V = 9,myNum;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 4);
addEdge(graph, 0, 2);
addEdge(graph, 0, 3);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);
addEdge(graph, 1, 7);
addEdge(graph, 1, 8);
addEdge(graph, 3, 4);
addEdge(graph, 3, 5);
addEdge(graph, 5, 6);

scanf("%d",&myNum);

printf("%s",isArticulationPoint(myNum,V,graph)? "Yes" : "No" );

return 0;
}

void APUtil(int u, int visited[], int disc[],
int low[], int parent[], int ap[],struct Graph* graph)
{
// A static variable is used for simplicity, we can avoid use of static
// variable by passing a pointer.
static int time = 0;

// Count of children in DFS Tree
int children = 0;

// Mark the current node as visited
visited[u] = 1;

// Initialize discovery time and low value
disc[u] = low[u] = ++time;

// Go through all vertices aadjacent to this
struct AdjListNode *i;
for (i = graph->array[u].head; i != NULL; ++i)
{
int v = i->dest; // v is current adjacent of u.Here i'm messed up

// If v is not visited yet, then make it a child of u
// in DFS tree and recur for it
if (!visited[v])
{
children++;
parent[v] = u;
APUtil(v, visited, disc, low, parent, ap,graph);

// Check if the subtree rooted with v has a connection to
// one of the ancestors of u
low[u] = MIN(low[u], low[v]);

// u is an articulation point in following cases

// (1) u is root of DFS tree and has two or more chilren.
if (parent[u] == NIL && children > 1)
ap[u] = 1;

// (2) If u is not root and low value of one of its child is more
// than discovery value of u.
if (parent[u] != NIL && low[v] >= disc[u])
ap[u] = 1;
}

// Update low value of u for parent function calls.
else if (v != parent[u])
low[u] =MIN(low[u], disc[v]);
}
}
int isArticulationPoint(int myNum,int V,struct Graph* graph)
{
// Mark all the vertices as not visited
int *visited = (int *)malloc(V*sizeof(int));
int *disc = (int *)malloc(V*sizeof(int));
int *low = (int *)malloc(V*sizeof(int));
int *parent = (int *)malloc(V*sizeof(int));
int *ap = (int *)malloc(V*sizeof(int)); // To store articulation points

// Initialize parent and visited, and ap(articulation point) arrays
int i;
for ( i = 0; i < V; i++)
{
parent[i] = NIL;
visited[i] = 0;
ap[i] = 0;
}

// Call the recursive helper function to find articulation points
// in DFS tree rooted with vertex 'i'
for ( i = 0; i < V; i++)
if (visited[i] == 0)
APUtil(i, visited, disc, low, parent, ap,graph);

// Now ap[] contains articulation points, return 1 or 0
if (ap[myNum] == 1)
return 1;
else return 0;
}

最佳答案

让你理解并不容易,但是看看我的代码。我希望您能找到您需要的东西。

int min(int a,int b)
{
return(a<b?a:b);
}
struct node
{
int val;
struct node* next;
};
struct graph
{
int v;
struct node** arr;
};
struct graph* createGraph(int v)
{
int i;
struct graph* temp =(struct graph*)malloc(sizeof(struct graph));
temp->v=v;
for(i=0;i<v;i++)
temp->arr=(int**)malloc(sizeof(int*)*v);
for(i=0;i<v;i++)
temp->arr[i]=NULL;
return temp;
}
void addEdge(struct graph* g,int u,int v)
{
struct node* temp =(struct node*)malloc(sizeof(struct node));
temp->val = v;
temp->next = g->arr[u];
g->arr[u] = temp;
}
void apUtil(struct graph * g,int node,int* isVisited,int* des,int* parent,int* low,int* ap)
{
struct node* temp=NULL;
static int time=0;
int children=0;
temp = g->arr[node];
isVisited[node]=1;
time++;
//printf("\nsetting time for %d",node);
des[node]=low[node]=time;

while(temp!=NULL)
{
if(!isVisited[temp->val])
{
children++;
parent[temp->val]=node;
apUtil(g,temp->val,isVisited,des,parent,low,ap);

low[node]= min(low[node],low[temp->val]);

if(parent[node]==-1 && children>1)
ap[node]=1;

if(parent[node]!=-1 && des[node]<=low[temp->val])
ap[node]=1;
}
else if(temp->val!=parent[node])
{
low[node]=min(low[node],des[temp->val]);
}
temp= temp->next;
}
//printf("%d",node);
}
void AP(struct graph* g)
{
int i;
int* des = (int*)malloc(sizeof(int)*g->v);
int* isVisited = (int*)malloc(sizeof(int)*g->v);
int* parent = (int*)malloc(sizeof(int)*g->v);
int* low = (int*)malloc(sizeof(int)*g->v);
int* ap = (int*)malloc(sizeof(int)*g->v);
for(i=0;i<g->v;i++)
{
isVisited[i]=0;
parent[i]=-1;
ap[i]=0;
}
for(i=0;i<g->v;i++)
{
if(isVisited[i]==0)
{
apUtil(g,i,isVisited,des,parent,low,ap);
}
}
printf("\n");
for(i=0;i<g->v;i++)
{
printf(" %d ",ap[i]);
}
}
main()
{
struct graph* g = createGraph(5);
addEdge(g,1,0);
addEdge(g,0,2);
addEdge(g,2,1);
addEdge(g,0,3);
addEdge(g,3,4);
AP(g);
}

关于c - 用DFS寻找无向图的连接点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30695587/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com