Unweighted and Undirected Graphs - Eishaaya/GMRDataStructuresTest GitHub Wiki

Making an Unweighted and Undirected Graph

In our code example we have two classes for an unweighted graph. We have the Vertex class and the Graph class. The vertex class will contain the value of the vertex and a collection of all its neighbors. The graph class will contain a collection of vertices and the methods that can be performed on the graph.

public class Vertex<T>
{
    public T value { get; set; }
    public List<Vertex<T>> Neighbors { get; set; }    

    public int NeighborCount => Neighbors.Count;

    public Vertex(T value) {...}
}

public class Graph<T>
{
    public List<Vertex<T>> Vertices { get; private set; }

    public int VertexCount => Vertices.Count;

    public Graph() {...}
}

There are many ways to design a graph, it all depends on what problem you are trying to solve. For example, we can also represent a graph as a 2d array which will be an adjacency matrix; we use the adjacency list method. To learn more about adjacency matrix follow this wikipedia link.

Wiki Representations: Graph Representations

Implementation Assistance

Note that this is not the order in which the functions should be implemented

bool AddVertex(Vertex vertex)

Check that the vertex is not null, has no neighbors, and does not already exist in the list. If all of these are true, add it to the list. Return whether the addition occurred.

bool RemoveVertex(Vertex vertex)

If the vertex exists within the graph, remove all edges from that vertex, remove the vertex from the list, and return true. If it does not exist within the graph, return false.

bool AddEdge(Vertex a, Vertex b)

Check that both of the vertices are not null and that they both exist in the list. If both of these are true, add the vertices to each other's neighbor list. Return whether the addition occurred.

bool RemoveEdge(Vertex a, Vertex b)

Check that both of the vertices are not null, they exist in the list, and they are each other's neighbor. If all of these are true, remove them from each other's neighbor list. Return whether the removal occurred.

Vertex Search(T value)

Create an int variable equal to -1. Then loop through all the vertices and check if the value equals to any of the vertices. If so set the int variable to that index and break out of the loop. If the int is -1 then return null else return the vertex at that index.

Assignments to be done with Undirected and Unweighted Graph

Traversals:

Depth-first Traversal (DFS)
- Iterative and Recursive
Breadth-first Traversal (BFS)
Single Source Shortest Path BFS (SSSP)
- Given a start vertex and an end vertex, print out the shortest path between the two vertices.

References

Take a look at our implementation if you are stuck.
- Undirected UnWeighted Graph C#
- Undirected UnWeighted Graph C++

<-- Previous | Next -->