# Finding bridges in an Undirected Graph implementation in C#

I am implementing fundamental data structures in C# while trying to learn techniques in the language to make my code cleaner, more concise while using good programming practices.

I have implemented both algorithms, DFS and BFS, to find the bridges in a graph. The code is properly working (as far as I've tested).

Important notes:

• I've tried a simpler and more intuitive approach of the solution, I know the computational complexity of my solution is $$\O(E*(V+E))\$$, while others methods resolve this exercise with $$\O(V+E)\$$ complexity.

• The method consists of:

1. For every edge (u, v), do the following:
1. Remove (u, v) from graph
2. See if the graph remains connected (We can either use BFS or DFS)
• The solution is designed to fit this function call:

List<Tuple<int, int>> FindBridges(int numOfNodes, int numOfEdges, List<Tuple<int, int>> edges)
{
//function body
}

• I've used string type for Node's id to be able to name them with any kind of data type and then convert them to string (ints,strings,chars...)

I'd appreciate feedback of any kind: ways to improve implementations (using this method), coding style, any refactor suggestions.

class UndirectedGraph
{
public class Node
{
public string Id { get; }
public List<string> Adjs { get; set; }
public Node(string nodeId)
{
Id = nodeId;
}
public Node(Node node)
{
Id = node.Id;
}

public override string ToString()
{
string value = string.Format("Node id:{0} -> (", Id);
{
value = value + adj + ",";
}
value += ")";
return value;
}
}
public int NumOfNodes { get; private set; }
public Node[] AdjacencyList { get; }

private List<Tuple<string, string>> Edges = new List<Tuple<string, string>>();

public UndirectedGraph(int numOfNodes)
{
NumOfNodes = numOfNodes;
for (int i = 0; i < numOfNodes; i++)
{
}
}
public UndirectedGraph(UndirectedGraph originalGraph)
{
NumOfNodes = originalGraph.NumOfNodes;
Edges = originalGraph.Edges.ConvertAll(x => Tuple.Create(x.Item1,x.Item2));
}

public int FindNodeIndex(string nodeId)
{
for (int i = 0; i < AdjacencyList.Length; i++)
{
return i;
}
return -1;
}

public Node FindNode(string nodeId)
{
for (int i = 0; i < AdjacencyList.Length; i++)
{
}
return null;
}

public void AddEdge(string a, string b)
{
Tuple<string, string> edge = Tuple.Create(a, b);
Node aNode = FindNode(edge.Item1);
Node bNode = FindNode(edge.Item2);
// Avoid trying to create edges on non existing nodes
throw new Exception("The edge couldn't be created because one of the nodes is not part of the graph");

// To avoid paralel connections
if (Edges.Contains(edge) || Edges.Contains(Tuple.Create(b, a)))
return;

}
{
Node aNode = FindNode(edge.Item1);
Node bNode = FindNode(edge.Item2);
// Avoid trying to create edges on non existing nodes
throw new Exception("The edge couldn't be created because one of the nodes is not part of the graph");

// To avoid paralel connections
if (Edges.Contains(edge) || Edges.Contains(Tuple.Create(edge.Item2, edge.Item1)))
return;

}

public void DeleteEdge(Tuple<string, string> edge)
{
if (!Edges.Contains(edge))
return;

Node aNode = FindNode(edge.Item1);
Node bNode = FindNode(edge.Item2);
Edges.Remove(edge);
}

public override string ToString()
{
List<string> nodesString = new List<string>();
{
}
string message = string.Join('\n', nodesString);
message += '\n';
return message;
}

public List<string> DFS(string startingNode_id = null)
{
// Set up starting node
Node currentNode;
if (startingNode_id == null)
else
currentNode = FindNode(startingNode_id);
// --------------------

// Initialize for first iteration
Stack<string> stack = new Stack<string>(NumOfNodes);
List<string> nodesVisited = new List<string>();
// --------------------

// Iteration of DFS
while (nodesVisited.Count < NumOfNodes)
{
if (toNode_index >= 0)
{
stack.Push(currentNode.Id);
}
else if (stack.Count > 0)
{
currentNode = FindNode(stack.Pop());
}
else
{
break;
}

if (!nodesVisited.Contains(currentNode.Id))
}
return nodesVisited;
}

public List<string> BFS(string startingNode_id = null)
{
// Set up starting node
Node currentNode;
if (startingNode_id == null)
else
currentNode = FindNode(startingNode_id);
// --------------------

// Initialize for first iteration
List<string> nodesVisited = new List<string>();
List<string> queue = new List<string>();
// --------------------

// Iterations of BFS
while (nodesVisited.Count < NumOfNodes && queue.Count > 0)
{
currentNode = FindNode(queue[0]);
queue.RemoveAt(0);
for (int i = 0; i < currentNode.Adjs.Count; i++)
{
if (!nodesVisited.Contains(nodeVisited))
{
}
}
}
return nodesVisited;
}

private int IndexOfFirstNotVisited(List<string> adjs, List<string> nodesVisited)
{
for (int i = 0; i < adjs.Count; i++)
{
{
return i;
}
}
return -1;
}
}


And the main used for testing purposes and initialization of the graph:

    class Program
{
static void Main(string[] args)
{
List<Tuple<int, int>> edges1 = new List<Tuple<int, int>>() {
Tuple.Create(1,2),
Tuple.Create(1,3),
Tuple.Create(2,3),
Tuple.Create(4,3),
Tuple.Create(4,5),
Tuple.Create(4,6),
Tuple.Create(5,6),
Tuple.Create(5,7),
Tuple.Create(6,7),
Tuple.Create(8,7),
Tuple.Create(8,9),
Tuple.Create(8,10),
Tuple.Create(9,10),
};
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
List<Tuple<int, int>> bridges = FindBridges(10, edges1.Count, edges1);
bridges.ForEach(Console.WriteLine);
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);
}

private static List<Tuple<int, int>> FindBridges(int numOfNodes, int numOfEdges, List<Tuple<int, int>> edges)
{
UndirectedGraph graph = new UndirectedGraph(numOfNodes);
List<Tuple<int, int>> bridges = new List<Tuple<int, int>>();
foreach (var edge in edges)
{
}

foreach (var edge in edges)
{
UndirectedGraph newGraph = new UndirectedGraph(graph);
newGraph.DeleteEdge(Tuple.Create(edge.Item1.ToString(), edge.Item2.ToString()));
if (newGraph.BFS().Count < numOfNodes)
}
return bridges;
}
}


The code is understandable, perhaps the naming used in some fields is quite hard to recognize for others who are seeing this code for first time.

Example Adjs (AdjacentVertices) is not intuitive, you are used to see this code and understand why you'd put everything on its place but other person who comes will spend more time getting familiar with it. Another example is Node (I think you mean Vertex) perhaps it is due the difference I perceive between Node (for trees) and Vertex (for general graphs, naturally including trees), technical vocabulary is also relevant.

Your UndirectedGraph class is an UndirectedAdjacencyList i think it is important to mention due the different Graph models that there are.

### With the code.

You will want to dynamically add edges and vertices in your graph. An alternative would be:

    public List<Node> AdjacencyList { get; } //where Node is means Vertex


In addition, I think it would be better to handle Edges as a list rather than an array.

    //instead of
//private List<Tuple<string, string>> Edges = new List<Tuple<string, string>>();
private List<Edge> Edges = new List<Edge>();


At last I propose you the following Idea which may make easier to manage both Vertices and Edges

    private SortedDictionary<Vertex, List<Edge>> AdjacencyList;


So that there will not be any repeated Vertex in your graph.