Interface
AddVertex(T data)
AddEdge(int from, int to)
DFS
BFS
MST
TopSort
PrintGraph
using System;
using System.Collections.Generic;
using System.Linq;
namespace TestCase1.TestCase.GraphMatrix
{
public class Vertex<T>
{
public T Data
{
get;
set;
}
public bool Visited
{
get;
set;
}
public Vertex(T data)
{
this.Data =
data;
this.Visited =
false;
}
}
public class GraphMatrix<T>
{
private int GraphSize =
0;
private List<Vertex<T>>
Vertices
{
get;
set;
}
private int[,] adjMatrix
{
get;
set;
}
private int Capacity
{
get;
set;
}
public GraphMatrix(
int capacity)
{
this.Vertices =
new List<Vertex<T>>
();
this.Capacity =
capacity;
this.adjMatrix =
new int[capacity, capacity];
for (
int i =
0; i < capacity; i++
)
{
for (
int j =
0; j < capacity; j++
)
{
this.adjMatrix[i, j] =
0;
}
}
}
public void AddVertex(T data)
{
// ? need check
var result =
this.Vertices.Where(t =>
t.Data.Equals(data));
if (result ==
null || !
result.Any())
{
this.Vertices.Add(
new Vertex<T>
(data));
this.GraphSize++
;
}
}
public void AddEdge(
int from,
int to)
{
if (
from >=
this.GraphSize || to >=
this.GraphSize)
{
throw new ArgumentException(
"index is out of graph size!");
}
this.adjMatrix[
from, to] =
1;
this.adjMatrix[to,
from] =
1;
}
public void AddDirectedEdge(
int from,
int to)
{
if (
from >=
this.GraphSize || to >=
this.GraphSize)
{
throw new ArgumentException(
"index is out of graph size!");
}
this.adjMatrix[
from, to] =
1;
}
public void ShowVertex(Vertex<T>
ver)
{
Console.WriteLine("Show vertext = {0}", ver.Data);
}
public void InitVisit()
{
foreach (
var v
in this.Vertices)
{
v.Visited =
false;
}
}
public void PrintGraph()
{
for (
int i =
0; i <
this.GraphSize; i++
)
{
Console.WriteLine();
Console.Write("Vertex is {0}: ",
this.Vertices[i].Data);
for (
int j =
0; j <
this.GraphSize; j++
)
{
if (
this.adjMatrix[i, j] ==
1)
{
Console.Write(this.Vertices[j].Data);
Console.Write(" ");
}
}
}
}
public int FindVertexWithoutSuccssor()
{
for (
int i =
0; i <
this.GraphSize; i++
)
{
bool hasSuccessor =
false;
for (
int j =
0; j <
this.GraphSize; j++
)
{
if (
this.adjMatrix[i, j] ==
1)
{
hasSuccessor =
true;
break;
}
}
if (!
hasSuccessor)
{
return i;
}
}
return -
1;
}
public void MoveColumn(
int column)
{
for (
int row =
0; row <
this.GraphSize; row++
)
{
for (
int j = column +
1; j <
this.GraphSize; j++
)
{
this.adjMatrix[row, j -
1] =
this.adjMatrix[row, j];
}
}
}
public void MoveRow(
int row)
{
for (
int column =
0; column <
this.GraphSize; column++
)
{
for (
int j = row +
1; j <
this.GraphSize; j++
)
{
this.adjMatrix[j -
1, column] =
this.adjMatrix[j, column];
}
}
}
public void RemoveVertex(
int index)
{
this.Vertices.RemoveAt(index);
this.GraphSize--;
// important here.
}
public void TopSort()
{
Stack<Vertex<T>> stack =
new Stack<Vertex<T>>
();
while (
this.GraphSize >
0)
{
int vertex =
FindVertexWithoutSuccssor();
if (vertex == -
1)
{
throw new Exception(
"The graph has cycle!");
}
stack.Push(this.Vertices[vertex]);
this.MoveRow(vertex);
this.MoveColumn(vertex);
this.RemoveVertex(vertex);
}
while (stack.Count !=
0)
{
var ret =
stack.Pop();
Console.WriteLine(ret.Data);
}
}
public void DFS()
{
Stack<
int> stack =
new Stack<
int>
();
// validation
if (
this.GraphSize ==
0)
{
Console.WriteLine("graph is empty, no op!");
return;
}
stack.Push(0);
this.Vertices[
0].Visited =
true;
ShowVertex(this.Vertices[
0]);
while (stack.Count !=
0)
{
int index =
stack.Peek();
// find next un-visited edge
int v =
this.GetNextUnVisitedAdjancentNode(index);
if (v == -
1)
{
stack.Pop();
}
else
{
this.ShowVertex(
this.Vertices[v]);
this.Vertices[v].Visited =
true;
stack.Push(v);
}
}
// reset ALL VISIT flags
this.InitVisit();
}
public void BFS()
{
Queue<
int> queue =
new Queue<
int>
();
// validation
if (
this.GraphSize ==
0)
{
return;
}
// logic
queue.Enqueue(
0);
ShowVertex(this.Vertices[
0]);
this.Vertices[
0].Visited =
true;
while (queue.Count >
0)
{
int result =
queue.Dequeue();
// find adjacent nodes and enqueue them
for (
int j =
0; j <
this.GraphSize; j++
)
{
if (adjMatrix[result, j] ==
1 &&
this.Vertices[j].Visited ==
false)
{
// print all adjacent nodes
ShowVertex(
this.Vertices[j]);
this.Vertices[j].Visited =
true;
queue.Enqueue(j);
}
}
}
// reset
this.InitVisit();
}
public void MST()
{
// validation
if (
this.GraphSize ==
0)
{
return;
}
// init
Stack<
int> stack =
new Stack<
int>
();
stack.Push(0);
int currentVertex =
0;
int vertex =
0;
this.Vertices[
0].Visited =
true;
while (stack.Count >
0)
{
currentVertex =
stack.Peek();
vertex =
this.GetNextUnVisitedAdjancentNode(currentVertex);
if (vertex == -
1)
{
stack.Pop();
}
else
{
this.Vertices[vertex].Visited =
true;
// print
Console.Write(
this.Vertices[currentVertex].Data.ToString() +
this.Vertices[vertex].Data.ToString());
Console.Write("-> ");
stack.Push(vertex);
}
}
// clean up
this.InitVisit();
}
private int GetNextUnVisitedAdjancentNode(
int v)
{
// validation
if (v >=
this.GraphSize)
{
throw new Exception(
"v is out of graph size!");
}
for (
int i =
0; i <
this.GraphSize; i++
)
{
if (adjMatrix[v, i] ==
1 && !
this.Vertices[i].Visited)
{
return i;
}
}
return -
1;
}
public void DepthFirstSearch()
{
DFSUtil(0);
this.InitVisit();
}
private void DFSUtil(
int vertex)
{
// validation
if (vertex >=
this.GraphSize)
{
throw new ArgumentException(
"out of graph size!");
}
int ver =
this.GetNextUnVisitedAdjancentNode(vertex);
if (ver == -
1)
{
return;
}
else
{
// print current node
ShowVertex(
this.Vertices[ver]);
this.Vertices[ver].Visited =
true;
DFSUtil(ver);
}
}
}
}
转载于:https://www.cnblogs.com/xuyanran/p/8543209.html
